#include "Alicelib.h"
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A firsts
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;
void Alice(int n, int m, int a[], int b[]){
//construct first
vector<int> adj[n+13];
FOR(i,m) adj[a[i]+1].push_back(b[i]+1);
FR(i,1,n+1){
adj[i].push_back(n+11);
FOR(j,10){
if (i&(1<<j)) adj[i].push_back(n+1+j);
}
}
adj[n+11].push_back(n+12);
FR(i,n+1,n+10) adj[i].push_back(i+1);
int u=0;
FR(i,1,n+13) u+=SZ(adj[i]);
InitG(n+12,u);
int cnt=0;
FR(i,1,n+13){
for (LL v:adj[i]){
MakeG(cnt,i-1,v-1);
cnt++;
}
}
}
#include "Boblib.h"
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;
static set<int> bit;
static vector<int> adj[1020];
static map<int,int> val;
static int id[1020];
static void dfs(int i, int par){
for (int x:adj[i]){
if (x==par || !bit.count(x)) continue;
val[x]=2*val[i];
dfs(x,i);
}
}
void Bob(int v, int u, int c[], int d[]){
int n=v-12;
FOR(i,u){
adj[c[i]].push_back(d[i]);
adj[d[i]].push_back(c[i]);
}
int fat=-1, fat2=-1;
FOR(i,v){
if (SZ(adj[i])==1 && SZ(adj[adj[i][0]])==n+1){
fat2=i;
fat=adj[i][0];
break;
}
}
//cout<<"FAT: "<<fat<<" "<<fat2<<"\n";
bool used[v];
memset(used,false,sizeof(used));
for (int x:adj[fat]) used[x]=true;
FOR(i,v) if (!used[i] && i!=fat) bit.insert(i);
//for (LL x:bit) cout<<x<<" ";
//cout<<"\n";
vector<int> ends;
for (int x:bit){
int cnt=0;
for (int z:adj[x]) if (bit.count(z)) cnt++;
if (cnt==1) ends.push_back(x);
//cout<<cnt<<"\n";
}
if (SZ(ends)==1){
val[ends[0]]=1;
dfs(ends[0],-1);
}
else{
int e1=ends[0], e2=ends[1];
if (SZ(adj[e1])>SZ(adj[e2])){
val[e1]=1;
dfs(e1,-1);
}
else{
val[e2]=1;
dfs(e2,-1);
}
}
memset(id,-1,sizeof(id));
FOR(i,v){
if (bit.count(i) || i==fat || i==fat2) continue;
for (int x:adj[i]){
if (bit.count(x)) id[i]+=val[x];
}
}
set<PII> edges;
FOR(i,v){
if (bit.count(i) || i==fat || i==fat2) continue;
int cur=id[i];
for (int x:adj[i]){
if (id[x]!=-1){
int a=min(cur,id[x]), b=max(cur,id[x]);
edges.insert(mp(a,b));
}
}
}
InitMap(n,SZ(edges));
for (PII e:edges){
//cout<<e.A<<" "<<e.B<<"\n";
MakeMap(e.A,e.B);
}
}
