#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
void Alice( int N, int M, int A[], int B[] )
{
vector<ii> edges;
for(int i=0;i<M;i++)
{
edges.pb(mp(A[i],B[i]));
}
for(int i=0;i<10;i++)
{
for(int j=0;j<N;j++)
{
if(j&(1<<i))
{
edges.pb(mp(N+i, j));
}
}
}
for(int j=0;j<9;j++)
{
edges.pb(mp(N+j, N+j+1));
}
for(int i=0;i<2;i++)
{
for(int j=0;j<10;j++)
{
edges.pb(mp(N+10+i, N+j));
}
}
InitG(N+12, int(edges.size()));
//cerr<<N+12<<' '<<edges.size()<<'\n';
for(int i=0;i<edges.size();i++)
{
//cerr<<i<<' '<<edges[i].fi<<' '<<edges[i].se<<'\n';
MakeG(i, edges[i].fi, edges[i].se);
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
static int perm[1111];
static set<int> adj[1111];
static bool vis[1111];
void Bob( int V, int U, int C[], int D[] )
{
for(int i=0;i<U;i++)
{
adj[C[i]].insert(D[i]); adj[D[i]].insert(C[i]);
}
int idx=0; int idy=0;
for(int i=0;i<V;i++)
{
for(int j=i+1;j<V;j++)
{
if(adj[i].size()==10&&adj[j].size()==10&&adj[i]==adj[j])
{
idx=i; idy=j; break;
}
}
}
int bitgod[10]={};
set<int> gods;
for(int v:adj[idx]) gods.insert(v);
vi pathend;
for(int v:adj[idx])
{
int cnt=0;
for(int x:gods)
{
cnt+=(adj[v].find(x)!=adj[v].end());
}
if(cnt==1) pathend.pb(v);
}
assert(pathend.size()==2);
if(adj[pathend[0]].size()<adj[pathend[1]].size()) swap(pathend[0],pathend[1]);
bitgod[0] = pathend[0];
vis[bitgod[0]] = 1;
for(int i=1;i<10;i++)
{
int cur = bitgod[i-1];
for(int v:adj[cur])
{
if(gods.find(v)!=gods.end()&&!vis[v])
{
bitgod[i] = v; vis[v] = 1; break;
}
}
}
memset(perm,-1,sizeof(perm));
for(int i=0;i<V;i++)
{
if(gods.find(i)==gods.end()&&i!=idx&&i!=idy)
{
int label=0;
for(int j=0;j<10;j++)
{
if(adj[i].find(bitgod[j])!=adj[i].end())
{
label^=(1<<j);
}
}
perm[i] = label;
}
}
vector<ii> edges;
for(int i=0;i<U;i++)
{
if(perm[C[i]]!=-1&&perm[D[i]]!=-1) edges.pb(mp(perm[C[i]],perm[D[i]]));
}
InitMap(V - 12, int(edges.size()));
for(int i=0;i<edges.size();i++)
{
MakeMap(edges[i].fi, edges[i].se);
}
}
