#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
inline bool checkbit(int i, int j)
{
return i>>j&1;
}
void Alice( int N, int M, int A[], int B[] ){
int n,m;
n=N; m=M;
vector <ii> edges;
for (int i=0; i<m; i++) edges.push_back({A[i],B[i]});
for (int i=0; i<10; i++)
{
for (int j=0; j<n; j++) if (checkbit(j,i)) edges.push_back({n+i,j});
if (i>0) edges.push_back({n+i,n+i-1});
}
for (int i=0; i<n; i++) edges.push_back({n+10,i});
edges.push_back({n+10,n+11});
InitG(n+12,edges.size());
int cnt=0;
for (ii i:edges) MakeG(cnt++,i.ff,i.ss);
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
int n,m;
n=V - 12;
vector <vector<int>> adj(V);
for (int i=0; i<U; i++)
{
adj[C[i]].push_back(D[i]);
adj[D[i]].push_back(C[i]);
}
// cerr<<V<<endl;
// for (int i=0; i<V; i++)
// {
// cerr<<i<<" := ";
// for (int j:adj[i]) cerr<<j<<' '; cerr<<endl;
// }
int type1,type2;
for (int i=0; i<V; i++) if (adj[i].size()==1&&adj[adj[i][0]].size()==n+1)
{
type2 = i;
type1 = adj[i][0];
}
vector <int> type(V,0);
type[type2] = type[type1] = 2;
for (int i:adj[type1]) if (i!=type2) type[i] = 1;
vector <int> nodes;
vector <vector<int>> sub_adj(V);
for (int i=0; i<V; i++) if (type[i]==0) nodes.push_back(i);
for (int i:nodes)
for (int j:adj[i])
if (type[j]==0) sub_adj[i].push_back(j);
// for (int i=0; i<V; i++)
// {
// cerr<<i<<" := ";
// for (int j:sub_adj[i]) cerr<<j<<' '; cerr<<endl;
// }
int it = -1;
for (int i:nodes)
if (sub_adj[i].size()==1)
{
if (it==-1||adj[it].size() < adj[i].size()) it = i;
}
vector <int> path;
path.push_back(it);
int p=-1;
for (int i=1; i<10; i++)
for (int j:sub_adj[it]) if (j!=p)
{
p = it;
it = j;
path.push_back(it);
break;
}
// for (int i:nodes) cerr<<i<<' '; cerr<<"!!"<<endl;
// cerr<<type1<<' '<<type2<<" = "; for (int i:path) cerr<<i<<' '; cerr<<endl;
vector <int> inv_path(V);
for (int i=0; i<10; i++) inv_path[path[i]] = i;
vector <int> final_id(V);
vector <vector<bool>> has_edge;
has_edge.assign(10,vector<bool>(V,0));
for (int i=0; i<U; i++)
{
int u=C[i]; int v=D[i];
if (type[u] == 0 && type[v] == 1)
has_edge[inv_path[u]][v] = 1;
swap(u,v);
if (type[u] == 0 && type[v] == 1)
has_edge[inv_path[u]][v] = 1;
}
for (int i=0; i<V; i++) if (type[i] == 1)
{
for (int j=0; j<10; j++) if (has_edge[j][i]) final_id[i] |= (1<<j);
}
vector <pair<int,int>> edges;
for (int i=0; i<U; i++)
{
int u=C[i]; int v=D[i];
if (type[u]==1&&type[v]==1)
{
edges.push_back({final_id[u],final_id[v]});
}
}
InitMap(n,edges.size());
for (pair<int,int> i:edges) MakeMap(i.first,i.second);
}
