#include "Alicelib.h"
#include <cassert>
#include <cstdio>
using namespace std;
#define REP1(i,n) for(int i=1;i<=n;i++)
#define REP(i,n) for(int i=0;i<n;i++)
void Alice( int N, int M, int A[], int B[] ){
int V = N + 12; // N~N+9 ,N+10~N+11;
int U = M;
REP (i,N) {
U += __builtin_popcount(i);
}
U += 9, U += 2*N;
InitG(V,U);
int idx = 0;
REP (i,M) {
MakeG(idx++,A[i],B[i]);
}
for (int i=N;i<N+9;i++) MakeG(idx++,i,i+1);
REP (i,N) {
MakeG(idx++,i,N+10), MakeG(idx++,i,N+11);
int tmp = i;
int bit = 0;
while (tmp) {
if (tmp&1) MakeG(idx++,i,N+bit);
tmp >>= 1;
bit++;
}
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define REP1(i,n) for(int i=1;i<=n;i++)
#define REP(i,n) for(int i=0;i<n;i++)
#define SZ(a) (int)a.size()
const int MAXn=1e3+20;
bitset<MAXn> bs[MAXn];
int bit[MAXn];
int deg[MAXn];
int id[MAXn];
vector<int> e[MAXn];
int p[MAXn];
void dfs(int x,int par,int b){
// cout << "dfs " << x << endl;
bit[x] = (1<<b);
for (auto i:e[x]) {
if (i == par || id[i] != 2) continue;
dfs(i,x,b+1);
}
}
void Bob( int V, int U, int C[], int D[] ){
int N = V-12;
REP (i,U) {
bs[C[i]][D[i]] = 1;
bs[D[i]][C[i]] = 1;
e[C[i]].emplace_back(D[i]);
e[D[i]].emplace_back(C[i]);
}
// REP (i,U) {
// cout << i << ": ";
// for (auto it:e[i]) {
// cout << it << ' ';
// }
// cout << endl;
// }
int S = -1, T = -1;
REP (i,V) {
if (int(bs[i].count()) != N) continue;
for (int j=i+1;j<V;j++) {
if (int(bs[j].count()) != N) continue;
if (int((bs[i] & bs[j]).count()) == N) {
S = i, T = j;
id[S] = 1, id[T] = 1;
}
}
}
// cout << S << ' ' << T << endl;
vector<int> tmp;
REP (i,V) {
if (bs[S][i] == 0 && i != S && i != T) {
tmp.emplace_back(i);
id[i] = 2;
}
}
int X = -1;
REP (i,SZ(tmp)) {
int cur = tmp[i];
int cnt = 0;
for (auto it:e[cur]) {
if (id[it] == 2) cnt++;
}
// cout << "cnt " << cnt << endl;
if (cnt == 1) {
// cout << "HI" << endl;
if (X == -1) X = cur;
else if (SZ(e[cur]) > SZ(e[X])) X = cur;
}
}
dfs(X,X,0);
// REP (i,V) cout << i << ' ' << bit[i] << endl;
int M = 0;
REP (i,V) {
if (id[i] == 0) {
for (auto it:e[i]) {
if (id[it] == 0) M++;
if (id[it] == 2) {
p[i] += bit[it];
}
}
}
}
// REP (i,V) cout << "p: " << p[i] << endl;
// REP (i,V) cout << "id: " << id[i] << endl;
M /= 2;
InitMap(N,M);
REP (i,U) {
if (id[C[i]] == 0 && id[D[i]] == 0) {
MakeMap(p[C[i]],p[D[i]]);
}
}
}
