#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
namespace{
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define tcT template<class T
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)
tcT> bool minimize(T& a, const T& b){
return (a > b ? a = b, 1 : 0);
}
tcT> bool maximize(T& a, const T& b){
return (a < b ? a = b, 1 : 0);
}
tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;
using ll = long long;
using db = double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
}
void Alice( int N, int M, int A[], int B[] ){
int LG = 10;
vpi edges;
F0R(i, LG - 1){
edges.eb(i + N, N + i + 1);
}
int extraBit = N + LG;
int extraAll = N + LG + 1;
F0R(i, N){
F0R(j, LG) if((i + 2) >> j & 1){
edges.eb(i, j + N);
}
edges.eb(extraAll, i);
}
F0R(j, LG) edges.eb(extraAll, j + N), edges.eb(extraBit, j + N);
F0R(i, M) edges.eb(A[i], B[i]);
InitG(N + LG + 2, sz(edges));
for(int i = 0; auto [u, v] : edges) MakeG(i++, u, v);
// cerr << "Alice send : " << N + LG + 2 << ' ' << sz(edges) << '\n';
// for(auto [u, v] : edges) cerr << u << ' ' << v << '\n';
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
namespace{
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define tcT template<class T
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)
tcT> bool minimize(T& a, const T& b){
return (a > b ? a = b, 1 : 0);
}
tcT> bool maximize(T& a, const T& b){
return (a < b ? a = b, 1 : 0);
}
tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;
using ll = long long;
using db = double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
const int MAX = 1505;
int deg[MAX], degChain[MAX];
vpi edges;
vi adjChain[MAX];
}
void Bob( int V, int U, int C[], int D[] ){
// cerr << __func__ << ' ' << V << ' ' << U << '\n';
// F0R(i, U) cerr << C[i] << ' ' << D[i] << '\n';
F0R(i, U){
int u = C[i], v = D[i];
++deg[u];
++deg[v];
edges.eb(u, v);
}
int extraAll = max_element(deg, deg + V) - deg;
// cerr << "extraAll = " << extraAll << '\n';
vi used(V);
F0R(i, U){
if(C[i] == extraAll || D[i] == extraAll){
int x = C[i] ^ D[i] ^ extraAll;
used[x] = 1;
}
}
int extraBit = -1;
F0R(i, V){
if(!used[i] && i != extraAll){
// cerr << "accept " << i << " as extraBit \n";
// assert(extraBit == -1);
extraBit = i;
}
}
vi bitNode(V);
int LG = 0;
F0R(i, U){
if(C[i] == extraBit || D[i] == extraBit){
int x = C[i] ^ D[i] ^ extraBit;
bitNode[x] = 1;
++LG;
}
}
// assert(LG == 10);
F0R(i, U){
int u = C[i], v = D[i];
if(bitNode[u] && bitNode[v]){
++degChain[u];
++degChain[v];
adjChain[u].eb(v);
adjChain[v].eb(u);
}
}
pi heads = {-1, -1};
F0R(i, V){
if(degChain[i] == 1){
if(heads.ff == -1) heads.ff = i;
else{
// assert(heads.ss == -1);
heads.ss = i;
}
}
}
// assert(heads.ff != -1 && heads.ss != -1);
// assert(deg[heads.ff] != deg[heads.ss]);
int bit0 = deg[heads.ff] > deg[heads.ss] ? heads.ff : heads.ss;
// cerr << deg[heads.ff] << ' ' << deg[heads.ss] << '\n';
// cerr << heads.ff << ' ' << heads.ss << " | " << bit0 << '\n';
vi bit(V, -1);
int u = bit0, pre = -1, cnt = 0;
while(true){
bit[u] = cnt++;
if(cnt == 10) break;
int nxt = -1;
for(auto v : adjChain[u]) if(v != pre){
nxt = v;
break;
}
pre = u; u = nxt;
}
vi original(V);
int N = V - 12;
F0R(i, U){
int u = C[i], v = D[i];
if(bit[u] != -1 && bit[v] == -1){
original[v] |= (1 << bit[u]);
} else if(bit[u] == -1 && bit[v] != -1){
original[u] |= (1 << bit[v]);
}
}
vpi edges;
F0R(i, U){
int u = C[i], v = D[i];
if(u == extraAll || v == extraAll) continue;
if(u == extraBit || v == extraBit) continue;
if(bit[u] != -1 || bit[v] != -1) continue;
int x = original[u] - 2, y = original[v] - 2;
// assert(x >= 0 && y >= 0);
edges.eb(x, y);
}
int M = sz(edges);
InitMap(N, M);
for(auto [u, v] : edges) MakeMap(u, v);
}
