#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<array<int,2>>edges;
for(int i = 0;i<m;i++){
edges.push_back({A[i]+12,B[i]+12});
}
for(int i = 0;i<n;i++){
int p = i+1;
for(int bit = 0;bit<10;bit++){
if((1<<bit)&p) {
edges.push_back({bit,i+12});
}
}
edges.push_back({10,i+12});
}
edges.push_back({10,11});
edges.push_back({0,1});
edges.push_back({1,2});
edges.push_back({2,3});
edges.push_back({3,4});
edges.push_back({4,5});
edges.push_back({5,6});
edges.push_back({6,7});
edges.push_back({7,8});
edges.push_back({8,9});
InitG(n+12,edges.size());
for(int i = 0;i<edges.size();i++){
MakeG(i,edges[i][0],edges[i][1]);
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
vector<int>leafs;
vector<int>ord;
void dfs(int st, set<int>g[], set<int>nodes, int par){
ord.push_back(st);
bool leaf=1;
for(int i : g[st]){
if(nodes.find(i)!=nodes.end()&&i!=par){
dfs(i,g,nodes,st);
leaf=0;
}
}
if(leaf){
leafs.push_back(st);
}
}
void Bob( int v, int u, int C[], int D[] ){
int n = v-12;
set<int>rg[v];
int deg[v];
fill(deg,deg+v,0);
for(int i = 0;i<u;i++){
rg[C[i]].insert(D[i]);
rg[D[i]].insert(C[i]);
deg[C[i]]++;
deg[D[i]]++;
}
set<int>bitnode;
for(int i = 0;i<v;i++){
bitnode.insert(i);
}
int cov = -1;
for(int i = 0;i<v;i++){
if(deg[i]==1){
if(deg[*rg[i].begin()]==n+1){
cov=*rg[i].begin();
break;
}
}
}
assert(cov!=-1);
for(int i : rg[cov]){
bitnode.erase(i);
}
bitnode.erase(cov);
assert(bitnode.size()==10);
leafs.clear();
dfs(*bitnode.begin(), rg, bitnode, -1);
if(leafs.size()<2){
assert(leafs.size()==1);
leafs.push_back(*bitnode.begin());
}
assert(leafs.size()==2);
ord.clear();
if(deg[leafs[0]]>deg[leafs[1]]){
dfs(leafs[0],rg,bitnode, -1);
}
else{
dfs(leafs[1],rg,bitnode, -1);
}
assert(ord.size()==10);
//order obtained
vector<array<int,2>>edges;
for(int i = 0;i<v;i++){
if(bitnode.find(i)!=bitnode.end())
continue;
int ind = 0;
for(int b = 0;b<10;b++){
if(rg[i].find(ord[b])!=rg[i].end()){
ind+=(1<<b);
}
}
ind--;
for(int j : rg[i]){
if(bitnode.find(j)!=bitnode.end())
continue;
int ind2 = 0;
for(int b = 0;b<10;b++){
if(rg[j].find(ord[b])!=rg[j].end()){
ind2+=(1<<b);
}
}
ind2--;
if(ind<0||ind2<0){
continue;
}
if(ind>ind2)
continue;
edges.push_back({ind,ind2});
}
}
InitMap(n,edges.size());
for(int i = 0;i<edges.size();i++){
MakeMap(edges[i][0],edges[i][1]);
}
}
