#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
vector<pair<int,int>>edge;
for(int q=0;q<M;q++){
edge.push_back({A[q],B[q]});
}
for(int q=0;q<10;q++){
for(int w=0;w<N;w++){
if((w>>q)&1){
edge.push_back({N+q,w});
}
}
if(q<9)edge.push_back({N+q,N+q+1});
}
for(int q=0;q<N;q++)edge.push_back({q,N+10});
edge.push_back({N+10,N+11});
InitG(N+12,edge.size());
int cnt=0;
for(auto [a,b] : edge){
MakeG(cnt,a,b); cnt++;
}
// InitG( 3, 2 );
// MakeG( 1, 2 );
// MakeG( 1, 3 );
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
vector<int>adj[V+1];
bool ada[V+1][V+1]; memset(ada,false,sizeof ada);
int conv[V+1]; memset(conv,0,sizeof conv);
for(int q=0;q<U;q++){
adj[C[q]].push_back(D[q]);
adj[D[q]].push_back(C[q]);
ada[C[q]][D[q]]=ada[D[q]][C[q]]=true;
//cout<<C[q]<<" k "<<D[q]<<endl;
}
vector<pair<int,int>>edge;
// cari N+10
int nd=-1;
for(int q=0;q<V;q++){
if(adj[q].size()==1 && adj[adj[q][0]].size()==V-11){
nd=adj[q][0]; break;
}
}
// cari N+9
int idx=-1;
for(int q=0;q<V;q++){
if(q!=nd && !ada[q][nd]){
if(idx==-1 || adj[idx].size()>adj[q].size())idx=q;
}
}
bool vis[V+1]; memset(vis,false,sizeof vis);
for(int bit=9;bit>=0;bit--){
vis[idx]=true;
int nxt=-1;
for(auto x : adj[idx]){
if(ada[x][nd]){
conv[x]+=(1<<bit);
}
if(!vis[x] && !ada[x][nd] && x!=nd){
nxt=x;
}
}
idx=nxt;
}
for(int q=0;q<U;q++){
if(ada[C[q]][nd] && ada[D[q]][nd]){
edge.push_back({conv[C[q]],conv[D[q]]});
}
}
//cout<<edge.size()<<endl;
InitMap(V-12,edge.size());
for(auto [a,b] :edge)MakeMap(a,b);
// InitMap( 3, 2 );
// MakeMap( 1, 2 );
// MakeMap( 1, 3 );
}
