#include<bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
#define st first
#define nd second
#define mp make_pair
using pii = pair<int, int>;
const int MAXN = 1020, MAXB = 10;
int deg[MAXN];
vector<pii> edge;
void Alice( int N, int M, int A[], int B[] ){
for(int i=0; i<M; ++i) {
A[i]++; B[i]++;
edge.push_back(mp(A[i], B[i]));
deg[A[i]]++;
deg[B[i]]++;
A[i]--;
B[i]--;
}
for(int i=1; i<=N; ++i) {
if(!deg[i]) continue;
for(int j=0; j<MAXB; ++j) {
if((1<<j)&i) {
edge.push_back(mp(i, N+1+j));
}
}
}
for(int i=0; i<MAXB; ++i) {
edge.push_back(mp(N+MAXB+1, N+i+1));
}
for(int i=0; i<MAXB/2; ++i) {
for(int j=MAXB-1; j>=MAXB-1-i; --j) {
edge.push_back(mp(N+i+1, N+j+1));
}
}
edge.push_back(mp(N+MAXB/2+1, N+MAXB/2+2));
edge.push_back(mp(N+MAXB+2, N+MAXB+1));
InitG(N+MAXB+2, edge.size());
for(int i=0; i<(int)edge.size(); ++i) {
MakeG(i, edge[i].st-1, edge[i].nd-1);
//cerr<<edge[i].st<<' '<<edge[i].nd<<'\n';
}
}
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define mp make_pair
using pii = pair<int, int>;
const int MAXN = 1020, MAXB = 10;
int N;
int root, bits[MAXN], first_bit, mid_bit, id[MAXN];
bool node[MAXN], is_bit[MAXN], sec_half[MAXN], skip[MAXN];
vector<int> g[MAXN], gb[MAXN];
vector<pii> edges;
void Bob( int V, int U, int C[], int D[] ){
N = V - (MAXB+2);
for(int i=0; i<U; ++i) {
g[C[i]].push_back(D[i]);
g[D[i]].push_back(C[i]);
}
for(int i=0; i<V; ++i) {
node[i] = 1;
if((int)g[i].size()==1) {
root = i;
node[i] = 0;
}
}
int spec = g[root][0];
node[spec] = 0;
for(int i: g[spec]) {
if(i == root) continue;
is_bit[i] = 1;
node[i] = 0;
}
for(int i=0; i<U; ++i) {
if(is_bit[C[i]] && is_bit[D[i]]) {
gb[C[i]].push_back(D[i]);
gb[D[i]].push_back(C[i]);
}
}
for(int iter=0; iter<MAXB/2-1; ++iter) {
for(int i=0; i<V; ++i) {
int cnt = 0, neigh;
for(int j: gb[i]) {
if(!skip[j]) {
cnt++;
neigh = j;
}
}
if(cnt==1) {
bits[i] = iter;
skip[i] = 1;
bits[neigh] = MAXB - iter - 1;
skip[neigh] = 1;
break;
}
}
}
vector<int> remaining;
for(int i=0; i<V; ++i) {
if(is_bit[i] && !skip[i]) {
remaining.push_back(i);
}
}
if(gb[remaining[0]].size() < gb[remaining[1]].size()) {
bits[remaining[0]] = MAXB/2;
bits[remaining[1]] = MAXB/2-1;
}
else {
bits[remaining[0]] = MAXB/2-1;
bits[remaining[1]] = MAXB/2;
}
for(int i=0; i<V; ++i) {
if(!node[i]) continue;
for(int j: g[i]) {
if(is_bit[j]) {
id[i] += (1<<bits[j]);
}
}
id[i]--;
}
for(int i=0; i<U; ++i) {
if(node[C[i]] && node[D[i]]) edges.push_back(mp(id[C[i]], id[D[i]]));
}
InitMap(V-(MAXB+2), edges.size());
int NN = V - (MAXB+2);
for(auto i: edges) {
assert(i.st>=0 && i.nd>=0);
MakeMap(i.st, i.nd);
}
}
