#include "Alicelib.h"
#include <cstdio>
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
static const int k = 10;
set<pii> AliceAns;
void AliceMake(int u,int v){
if(u>v) swap(u,v);
AliceAns.insert({u,v});
}
void AliceFinish(int n){
// dbg("ALICE DONE");
InitG(1+n+k+1, (int)AliceAns.size());
int i = 0;
for(auto[u,v] : AliceAns){
// cout << u _ v << endl;
MakeG(i++, u,v);
}
// cout << endl << endl;
}
void Alice(int n,int m,int u[],int v[]){
rep(i,0,m){
u[i]++; v[i]++;
AliceMake(u[i],v[i]);
}
int a = 0;
// connect 2^i to a and nodes with ith-bit ON
AliceMake(n+1, n+3);
AliceMake(n+1, n+4);
rep(i,0,k){
int vtx = n+1+i;
AliceMake(a,vtx);
if(i>=2) AliceMake(vtx-1, vtx);
for(int j=1; j<=n; j++) if(j&1<<i){
AliceMake(vtx, j);
}
}
// connect b to all except a
int b = n+k+1;
for(int i=0; i<=n+k; i++) if(i!=a){
AliceMake(b, i);
}
AliceFinish(n);
rep(i,0,m){
u[i]--; v[i]--;
}
return; InitG(3,2); MakeG(0,1,2); MakeG(1,1,3);
}
#include "Boblib.h"
#include <cstdio>
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
static const int k = 10;
set<pii> BobAns;
void BobMake(int u,int v){
if(u>v) swap(u,v);
BobAns.insert({u,v});
}
void BobFinish(int n){
// dbg(BobAns.size());
InitMap(n, (int)BobAns.size());
for(auto[u,v] : BobAns){
MakeMap(u-1, v-1);
}
}
const int N = 1069;
V<int> adj[N];
bool g[N][N];
int two[k];
int ori[N];
V<int> aadj[N];
void Bob(int ntot,int m,int u[],int v[]){
int n = ntot-k-2;
// dbg(n);
rep(i,0,N){
adj[i].clear();
rep(j,0,N) g[i][j] = 0;
}
rep(i,0,m){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
g[u[i]][v[i]] = g[v[i]][u[i]] = 1;
// cout << u[i] _ v[i] << nl;
}
// dbg("BOB0");
// find node with degree n+k
int b = 0;
while((int)adj[b].size()!=n+k) b++;
rep(i,0,ntot) if(i!=b) assert((int)adj[i].size()!=n+k);
// dbg(b);
// dbg("BOB1");
// find the node disconnected from b
int a;
rep(i,0,ntot) if(i!=b && !g[i][b]){
a = i; break;
}
rep(i,0,ntot) if(i!=b && !g[i][b]) assert(i==a);
assert(adj[a].size()==k);
// dbg("BOB2");
// dbg(a);
// determine two[], take a subgraph
V<int>&vec = adj[a];
for(int x : vec){
for(int y : adj[x]){
bool ok = 0;
for(int z : vec) ok |= y==z;
if(ok){
// cout << x _ y << nl;
aadj[x].push_back(y);
}
}
}
int p;
rep(i,0,k){
p = adj[a][i];
bool ok = 1;
ok &= aadj[p].size()==2;
if(!ok) continue;
// dbg(i);
// dbg(p);
int q = aadj[p][0], r = aadj[p][1];
// dbg(q); dbg(r);
ok &= aadj[q].size()==3;
ok &= aadj[r].size()==3;
ok &= g[q][r];
// dbg(ok);
if(ok) break;
}
// dbg(p);
// dbg(aadj[p].size());
// cout << nl << nl;
int q = aadj[p][0], r = aadj[p][1];
bool ok = 0;
for(int x : aadj[q]) if(x!=p && x!=r && g[a][x]){
ok = aadj[x].size()==1;
}
if(!ok) swap(q, r);
two[0] = p;
two[2] = q;
two[3] = r;
for(int x : aadj[q]) if(x!=p && x!=r){
two[1] = x;
}
// find the rest of two[]
rep(i,4,k){
for(int y : aadj[two[i-1]]) if(y!=two[i-2] && y!=two[i-4] && g[a][y]){
two[i] = y;
}
}
// dbg("BOB3");
// rep(i,0,k) cout << i _ two[i] << nl;
// recover nodes
rep(i,0,ntot){
// check importance
bool flag = 0;
flag |= i==a || i==b;
rep(j,0,k) flag |= i==two[j];
if(flag) continue;
ori[i] = 0;
// dbg(i);
rep(j,0,k) if(g[i][two[j]]){
ori[i] ^= 1<<j;
}
}
// dbg("BOB4");
// recover edges
rep(i,0,m){
// check importance
bool flag = 0;
flag = u[i]==a || u[i]==b || v[i]==a || v[i]==b;
rep(j,0,k) flag |= u[i]==two[j] || v[i]==two[j];
if(flag) continue;
// cout << u[i] _ v[i] << nl;
// cout << ori[u[i]] _ ori[v[i]] << nl;
BobMake(ori[u[i]],ori[v[i]]);
}
BobFinish(n);
return; InitMap(3,2); MakeMap(1,2); MakeMap(1,3);
}
