#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
void Alice( int n, int m, int A[], int B[] ){
vector<pair<int,int>> edge;
edge.clear();
for (int i=0;i<=n+9;i++) edge.push_back({i, n+10});
for (int i=n;i<=n+9;i++) edge.push_back({i, n+11});
for (int i=0;i<m;i++) edge.push_back({A[i], B[i]});
for (int i=n;i<n+9;i++) edge.push_back({i, i+1});
for (int i=0;i<n;i++) {
for (int j=0;j<10;j++) if (i & (1<<j)) edge.push_back({i, j+n});
}
int sz = edge.size();
// cout << n + 12 << " " << sz << endl;
// for (auto [u, v]:edge) cout << u << " " << v << endl;
InitG(n + 12, sz);
for (int i=0;i<sz;i++) MakeG(i, edge[i].first, edge[i].second);
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1020;
int deg[maxn];
bool is[maxn][maxn];
vector<int> adj[maxn];
bool rl[maxn];
int id[maxn];
int decode[maxn], bit[10];
void Bob( int V, int M, int C[], int D[] ){
vector<pair<int,int>> edge;
for (int i=0;i<V;i++) deg[i] = 0, rl[i] = true, adj[i].clear();
for (int i=0;i<V;i++) for (int j=0;j<V;j++) is[i][j] = false;
// cout << V << " " << M << endl;
// for (int i=0;i<M;i++) cout << C[i] << " " << D[i] << endl;
int n = V - 12;
for (int i=0;i<V;i++) deg[i] = 0;
for (int i=0;i<M;i++) {
adj[C[i]].push_back(D[i]);
adj[D[i]].push_back(C[i]);
deg[C[i]]++, deg[D[i]]++;
is[C[i]][D[i]] = is[D[i]][C[i]] = true;
}
int hub;
for (int i=0;i<V;i++) if (deg[i] == V-2) hub = i;
int key;
for (int i=0;i<V;i++) if (i != hub && !is[hub][i]) key = i;
// cout << hub << " " << key << endl;
rl[hub] = rl[key] = false;
vector<int> funny;
for (int i=0;i<V;i++) if (is[key][i]) {
funny.push_back(i);
rl[i] = false;
}
for (int i=0;i<V;i++) deg[i] = 0;
for (int i=0;i<10;i++) for (int j=0;j<10;j++) {
deg[funny[i]] += is[funny[i]][funny[j]];
}
// for (int i:funny) cout << i << " "; cout << endl;
for (int i:funny) if (deg[i] == 1) bit[0] = i;
for (int i=1;i<=9;i++) {
for (int j:funny) if (is[j][bit[i-1]] && (i-2 < 0 || j != bit[i-2])) bit[i] = j;
}
// for (int i=0;i<10;i++) cout << bit[i] << " "; cout << endl;
// for (int i=0;i<V;i++) cout << rl[i] << " "; cout << endl;
bool redo = false;
for (int i=0;i<n;i++) decode[i] = -1;
for (int i=0;i<V;i++) id[i] = -1;
for (int i=0;i<V;i++) if (rl[i]) {
id[i] = 0;
for (int j=0;j<10;j++) if (is[i][bit[j]]) id[i] += (1<<j);
if (id[i] >= n) {
redo = true;
// cout << i << " " << id[i] << endl;
break;
}
decode[id[i]] = i;
}
// cout << redo << endl;
for (int i=0;i<n;i++) if (decode[i] == -1) redo = true;
// for (int i=0;i<V;i++) cout << id[i] << " "; cout << endl;
// for (int i=0;i<10;i++) cout << bit[i] << " "; cout << endl;
// for (int i=0;i<10;i++) cout << deg[bit[i]] << " "; cout << endl;
if (redo) {
reverse(bit, bit+10);
for (int i=0;i<V;i++) if (rl[i]) {
id[i] = 0;
for (int j=0;j<10;j++) if (is[i][bit[j]]) id[i] += (1<<j);
// cout << id[i] << " ";
}
// cout << endl;
}
// for (int i=0;i<10;i++) cout << bit[i] << " "; cout << endl;
// for (int i:funny) cout << i << " "; cout << endl;
// for (int i=0;i<10;i++) cout << bit[i] << " "; cout << endl;
for (int i=0;i<M;i++) {
int u = C[i], v = D[i];
if (rl[u] && rl[v]) {
edge.push_back({id[u], id[v]});
// cout << u << " " << v << " " << id[u] << " " << id[v] << endl;
}
}
// for (int i=0;i<V;i++) cout << id[i] << " "; cout << endl;
int sz = edge.size();
InitMap(n, sz);
for (auto [u, v]:edge) MakeMap(u, v);
}
