#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
int V = N + 12;
int U = M + 9 + N + N + 10;
for(int i = 0 ; i < N ; ++i){
U += __builtin_popcount(i);
}
InitG(V , U);
int nTime = 0;
for(int i = 0 ; i < M ; ++i){
MakeG(nTime++,A[i],B[i]);
}
for(int i = 0 ; i < N ; ++i){
for(int j = 0 ; j < 10 ; ++j){
if((i & (1 << j))){
MakeG(nTime++,i,N+j);
}
}
}
for(int i = N ; i + 1 <= N + 9 ; ++i){
MakeG(nTime++,i,i+1);
}
for(int i = 0 ; i < N ; ++i){
MakeG(nTime++,N+10,i);
}
for(int i = 0 ; i < N + 10 ; ++i){
MakeG(nTime++,N+11,i);
}
}
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 20;
bitset<maxn> adj[maxn];
void Bob( int V, int U, int CC[], int DD[] ){
int N = V - 12;
int M = U - 9 - 2 * N - 10;
for(int i = 0 ; i < N ; ++i){
M -= __builtin_popcount(i);
}
InitMap(N,M);
if(N <= 2){
if(M > 0)MakeMap(0,1);
return;
}
for(int i = 0 ; i < U ; ++i){
adj[CC[i]][DD[i]] = 1;
adj[DD[i]][CC[i]] = 1;
}
int A = 0 , B = 0 , C = 0;
for(int i = 0 ; i < V ; ++i){
if(adj[i].count() == N + 10){
for(int j = 0 ; j < V ; ++j){
if(i != j && adj[i][j] == 0 && adj[j].count() == N){
A = i , B = j;break;
}
}
}
}
assert(A != B);
vector<int> added(V , 0);
for(int i = 0 ; i < V ; ++i){
if(i != A && i != B && adj[B][i] == 0){
added[i] = 1;
C = i;
}
}
vector<int> path;
auto dfs = [&](int u , int par){
while(true){
bool ok = 0;
path.push_back(u);
for(int i = 0 ; i < V ; ++i){
if(added[i] && par != i && adj[u][i]){
par = u,u = i;
ok = 1;
break;
}
}
if(ok == 0)break;
}
};
for(int i = 0 ; i < V ; ++i){
if(adj[C][i] && added[i]){
if(path.size() == 0){
dfs(i , C);
reverse(path.begin(),path.end());
path.push_back(C);
}else{
dfs(i , C);
}
}
}
// for(auto c : path)cout << c << " ";
assert(path.size() == 10);
if(adj[path[0]].count() < adj[path.back()].count())reverse(path.begin(),path.end());
vector<int> p(V , 0);
for(int i = 0 ; i < 10 ; ++i){
for(int j = 0 ; j < V ; ++j){
if(j != A && added[j] == 0 && adj[path[i]][j]){
p[j] |= (1 << i);
}
}
}
for(int i = 0 ; i < U ; ++i){
auto valid = [&](int u){
if(added[u] || u == A || u == B)return 0;
return 1;
};
if(valid(CC[i]) && valid(DD[i])){
// assert(p[CC[i]] == p[DD[i]]);
MakeMap(p[CC[i]],p[DD[i]]);
}
}
}
