#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
static const int MAXN=1505;
static const int BIT_CNT=10;
static int n,m;
static vector<pair<int,int> > edges;
static int code[MAXN];
static int deg1=0;
void addEdge(int u,int v)
{
if(u==n+1 || v==n+1) deg1++;
edges.push_back({u-1,v-1});
}
void returnGraph()
{
InitG(n+BIT_CNT+2, edges.size());
int pos=0;
for(auto cur: edges)
{
MakeG(pos++, cur.first, cur.second);
}
}
void Alice( int N, int M, int A[], int B[] )
{
n=N;
m=M;
for(int i=0;i<m;i++)
{
int u=A[i]+1;
int v=B[i]+1;
addEdge(u,v);
}
int ptr=1;
for(int i=1;i<=n;i++)
{
while(__builtin_popcount(ptr)==9) ptr++;
code[i]=ptr++;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<BIT_CNT;j++)
{
if(code[i]&(1<<j)) addEdge(i,n+1+j);
}
}
for(int i=1;i<=n+BIT_CNT;i++)
{
if(i==n+1) continue;
addEdge(n+BIT_CNT+1,i);
}
for(int i=1;i<=BIT_CNT;i++)
{
addEdge(n+BIT_CNT+2,n+i);
}
for(int i=2;i<BIT_CNT;i++)
{
addEdge(n+i-1,n+i);
}
if(deg1==BIT_CNT) addEdge(n+1,n+BIT_CNT);
else addEdge(n+BIT_CNT-1,n+BIT_CNT);
returnGraph();
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAXN=1505;
static const int BIT_CNT=10;
static int n,m;
static vector<int> adj[MAXN];
static int mark[MAXN];
static bool isBit[MAXN];
static int val[MAXN];
static int id[MAXN];
static int decode[MAXN];
static bool edge[MAXN][MAXN];
static vector<pair<int,int> > MapEdges;
void addMapEdge(int u,int v)
{
MapEdges.push_back({u-1,v-1});
}
void returnMap()
{
InitMap(n,MapEdges.size());
for(auto cur: MapEdges)
{
MakeMap(cur.first, cur.second);
}
}
void dfsBit(int v,int d,int par)
{
int cnt=0;
for(auto u: adj[v])
{
if(!isBit[u]) continue;
if(u==par) continue;
cnt++;
dfsBit(u,d+1,v);
}
if(cnt==0 && d==1) val[v]=(1<<(BIT_CNT-1));
else val[v]=(1<<d);
}
void Bob( int V, int U, int C[], int D[] )
{
n=V-BIT_CNT-2;
m=U;
for(int i=0;i<m;i++)
{
int u=C[i]+1;
int v=D[i]+1;
adj[u].push_back(v);
adj[v].push_back(u);
}
int bigR=0;
for(int i=1;i<=V;i++)
{
if(adj[i].size()==n+BIT_CNT-1)
{
bigR=i;
break;
}
}
for(auto u: adj[bigR])
{
mark[u]=1;
}
int smR=0;
int bit1=0;
for(int i=1;i<=V;i++)
{
if(i!=bigR && !mark[i])
{
if(adj[i].size()==BIT_CNT) smR=i;
else bit1=i;
}
}
for(auto u: adj[smR])
{
isBit[u]=1;
}
dfsBit(bit1, 0, -1);
for(int i=1;i<=V;i++)
{
if(i==bigR || i==smR || isBit[i]) continue;
for(auto u: adj[i])
{
if(isBit[u]) id[i]+=val[u];
}
}
int ptr=1;
for(int i=1;i<=n;i++)
{
while(__builtin_popcount(ptr)==9) ptr++;
decode[ptr++]=i;
}
for(int i=1;i<=V;i++)
{
if(id[i]>0) id[i]=decode[id[i]];
}
for(int i=1;i<=V;i++)
{
if(i==bigR || i==smR || isBit[i]) continue;
for(auto u: adj[i])
{
if(u==bigR || u==smR || isBit[u]) continue;
edge[id[i]][id[u]]=1;
}
}
for(int i=1;i<=V;i++)
{
for(int j=i+1;j<=V;j++)
{
if(edge[i][j]) addMapEdge(i,j);
}
}
returnMap();
}
