#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
//#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
//InitG(v,u)
//MakeG(0,a,b)
//Alice
void Alice(int n, int m, int a[], int b[]){
vector<pii>edge;
for(int x=0;x<m;x++){
edge.push_back({a[x],b[x]});
}
int ptr=n;
vector<int>line;
line.push_back(ptr);
ptr++;
for(int x=0;x<9;x++){
edge.push_back({ptr,ptr-1});
line.push_back(ptr);
ptr++;
}
for(int x=0;x<n;x++){
for(int y=0;y<10;y++){
if(x&(1<<y)){
edge.push_back({line[y],x});
}
}
}
for(int x=0;x<n+10;x++){
edge.push_back({n+10,x});
if(x<n) edge.push_back({n+11,x});
}
InitG(n+12,edge.size());
int cur=0;
for(auto it:edge){
MakeG(cur,it.first,it.second);
cur++;
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
//#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
//InitMap(N,M)
//MakeMap(a,b)
//Bob
void Bob(int v, int u, int c[], int d[]){
pii rt={-1,-1};
vector<int>adj[v+5];
for(int x=0;x<u;x++){
adj[c[x]].push_back(d[x]);
adj[d[x]].push_back(c[x]);
}
for(int x=0;x<v;x++){
rt=max(rt,{adj[x].size(),x});
}
int done[v];
memset(done,0,sizeof(done));
for(auto it:adj[rt.second]) done[it]=true;
int take;
for(int x=0;x<v;x++){
if(!done[x]) take=x;
}
memset(done,0,sizeof(done));
for(auto it:adj[take]) done[it]=true;
done[rt.second]=true;
done[take]=true;
vector<int>adj2[v+5];
for(int x=0;x<u;x++){
if(!done[c[x]]&&!done[d[x]]){
adj2[c[x]].push_back(d[x]);
adj2[d[x]].push_back(c[x]);
}
}
vector<int>line;
bool bit[v+5];
memset(bit,0,sizeof(bit));
for(int x=0;x<v;x++){
if(adj2[x].size()==1){
int cur=x;
while(1){
done[cur]=true;
line.push_back(cur);
bit[cur]=true;
bool nxt=false;
for(auto it:adj2[cur]){
if(done[it]) continue;
nxt=true;
cur=it;
}
if(!nxt) break;
}
}
}
if(adj[line[0]].size()<adj[line[9]].size()) reverse(line.begin(),line.end());
int arr[v+5];
memset(arr,0,sizeof(arr));
for(int x=0;x<10;x++){
for(auto it:adj[line[x]]){
if(bit[it]) continue;
arr[it]+=(1<<x);
}
}
vector<pii>edge;
for(int x=0;x<u;x++){
int temp=d[x];
int temp2=c[x];
if(temp==rt.second||temp==take||temp2==rt.second||temp2==take) continue;
if(bit[temp]||bit[temp2]) continue;
edge.push_back({arr[temp],arr[temp2]});
}
InitMap(rt.first-10,edge.size());
for(auto it:edge){
MakeMap(it.first,it.second);
}
}
