#include <bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
#define sz(x) (int)x.size()
#define fi first
#define se second
typedef long long lli;
typedef pair<int, int> pii;
void Alice(int N, int M, int A[], int B[])
{
const int logn = 10;
if(N < 3)
{
InitG(N, M);
if(M == 1)
MakeG(0, 0, 1);
return;
}
vector<pii> edges;
for(int i = 0; i < M; ++i)
{
++A[i]; ++B[i];
edges.push_back(pii(A[i], B[i]));
}
for(int i = 1; i <= N; ++i)
{
edges.push_back(pii(i, N + logn + 1));
for(int j = 0; j < logn; ++j)
if(i >> j & 1) edges.push_back(pii(i, N + j + 1));
}
for(int j = 1; j < logn; ++j)
edges.push_back(pii(N + j, N + j + 1));
edges.push_back(pii(N + logn + 1, N + logn + 2));
InitG(N + logn + 2, sz(edges));
for(int i = 0; i < sz(edges); ++i)
MakeG(i, edges[i].fi - 1, edges[i].se - 1);
}
#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;
#define sz(x) (int)x.size()
#define fi first
#define se second
typedef long long lli;
typedef pair<int, int> pii;
const int maxn = 1505;
vector<int> gr[maxn];
bool origin[maxn], ok[maxn];
int mask[maxn];
void Bob(int V, int U, int C[], int D[])
{
const int logn = 10;
if(V < 3)
{
InitMap(V, U);
if(U == 1)
MakeMap(0, 1);
return;
}
int N = V - logn - 2;
vector<int> one_deg_vertices;
for(int i = 0; i < U; ++i)
{
++C[i]; ++D[i];
gr[C[i]].push_back(D[i]);
gr[D[i]].push_back(C[i]);
}
for(int i = 1; i <= V; ++i)
if(sz(gr[i]) == 1) one_deg_vertices.push_back(i);
assert(sz(one_deg_vertices) <= 2);
int id_bit_10th = -1, min_deg = maxn;
if(sz(one_deg_vertices) == 1)
{
int u = one_deg_vertices.back();
u = gr[u].back();
for(auto&v: gr[u])
origin[v] = true;
origin[u] = origin[one_deg_vertices.back()] = false;
for(int i = 1; i <= V; ++i)
if(!origin[i] && i != u && min_deg > sz(gr[i]))
{
min_deg = sz(gr[i]);
id_bit_10th = i;
}
}
else
{
int u = one_deg_vertices.back();
u = gr[u].back();
if(sz(gr[u]) != N + 1)
swap(one_deg_vertices[0], one_deg_vertices[1]);
id_bit_10th = one_deg_vertices[0];
u = one_deg_vertices[1]; u = gr[u].back();
for(auto&v: gr[u])
origin[v] = true;
origin[u] = origin[one_deg_vertices[1]] = false;
}
for(int i = logn - 1, j = id_bit_10th; i >= 0; --i)
{
int nj = -1;
for(auto&k: gr[j])
{
if(origin[k]) mask[k] ^= (1 << i);
else if(!ok[k])
{
assert(nj == -1);
nj = k;
}
}
ok[j] = true;
j = nj;
if(i > 0) assert(j != -1);
}
vector<pii> edges;
for(int i = 0; i < U; ++i)
if(origin[C[i]] && origin[D[i]])
edges.push_back(pii(mask[C[i]] - 1, mask[D[i]] - 1));
int M = sz(edges);
InitMap(N, M);
for(auto&e: edges)
MakeMap(e.fi, e.se);
}
