#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
void Alice(int N, int M, int A[], int B[]) {
vector<pair<int, int> > edge;
for (int i = 0; i < M; ++i) edge.emplace_back(A[i], B[i]);
for (int i = 0; i < 10; ++i) {
for (int u = 0; u < N; ++u) if ( (u >> i) & 1) edge.emplace_back(u, N + i);
edge.emplace_back(N + i, N + 11);
if (i + 1 < 10) edge.emplace_back(N + i, N + i + 1);
}
for (int u = 0; u < N; ++u) {
edge.emplace_back(u, N + 10);
edge.emplace_back(u, N + 11);
}
InitG(N + 12, sz(edge) );
for (int i = 0; i < sz(edge); ++i) MakeG(i, edge[i].first, edge[i].second);
}
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
void Bob(int V, int U, int C[], int D[]){
int N = V - 12;
vector<vector<int> > gr(V);
for (int i = 0; i < U; ++i) {
gr[ C[i] ].emplace_back(D[i]);
gr[ D[i] ].emplace_back(C[i]);
}
vector<int> extra(12);
vector<int> deg(V);
for (int i = 0; i < U; ++i) ++deg[ C[i] ], ++deg[ D[i] ];
extra.back() = (int)(max_element(all(deg) ) - deg.begin() );
vector<bool> vis(V); vis[extra.back()] = true;
for (int u : gr[extra.back()]) vis[u] = true;
extra.rbegin()[1] = (int)(find(all(vis), false) - vis.begin() );
vis.assign(V, false); vis[extra.back()] = vis[extra.rbegin()[1] ] = true;
for (int u : gr[ extra.rbegin()[1] ]) vis[u] = true;
int tmp = (int)(find(all(vis), false) - vis.begin() );
vector<int> bitNode{ tmp }; vis[tmp] = true;
for (int u : gr[tmp]) if (!vis[u]) {
reverse(all(bitNode) );
for (int cur = u; cur != -1; ) {
bitNode.emplace_back(cur); vis[cur] = true;
int nxt = -1;
for (int v : gr[cur]) if (!vis[v]) nxt = v;
cur = nxt;
}
}
if (N <= (1 << 9) ) {
if (deg[ bitNode[0] ] == 2) reverse(all(bitNode) );
}
else {
if (deg[ bitNode[0] ] - 2 != N / 2) reverse(all(bitNode) );
}
for (int i = 0; i < sz(bitNode); ++i) extra[i] = bitNode[i];
vis.assign(V, false);
for (int u : extra) vis[u] = true;
vector<int> lable(V, 0);
for (int i = 0; i < 10; ++i) {
for (int u : gr[ extra[i] ]) if (!vis[u]) lable[u] |= 1 << i;
}
vector<pair<int, int> > edge;
for (int i = 0; i < U; ++i) if (!vis[ C[i] ] && !vis[ D[i] ]) edge.emplace_back(lable[ C[i] ], lable[ D[i] ]);
InitMap(N, sz(edge) );
for (auto _ : edge) MakeMap(_.first, _.second);
}
