#include "Alicelib.h"
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
void Alice( int N, int M, int A[], int B[] )
{
int n=N,m=M;
vector<pair<int,int>> edges;
for(int i=0;i<m;i++) edges.push_back({A[i],B[i]});
for(int i=0;i+1<=9;i++) edges.push_back({n+i,n+i+1});
for(int i=0;i<=9;i++) edges.push_back({n+i,n+10});
edges.push_back({n+10,n+11});
int num=2;
for(int i=0;i<n;i++)
{
num++;
while(__builtin_popcount(num)<=1) num++;
//cout<<i<<" is represented by:"<<num<<"\n";
for(int bit=0;bit<=9;bit++)
{
if((num&(1<<bit))>0) edges.push_back({i,n+bit});
}
}
int sz=edges.size();
InitG(n+12,sz);
for(int i=0;i<sz;i++) MakeG(i,edges[i].first,edges[i].second);
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
const int MAX=1024;
vector<int> adj[MAX];
int deg[MAX];
bool spec[MAX];
bool vis[MAX];
int cnt_spec[MAX];
int number[MAX];
int rep[MAX];
void Bob( int V, int U, int C[], int D[] )
{
for(int i=0;i<U;i++)
{
int u=C[i],v=D[i];
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++;
deg[v]++;
}
//for(int i=0;i<V;i++) cout<<i<<":"<<deg[i]<<"\n";
int s=0;
for(int i=0;i<V;i++)
{
if(deg[i]==1)
{
s=i;
break;
}
}
s=adj[s][0];
for(int nxt: adj[s])
{
if(deg[nxt]!=1)
{
spec[nxt]=1;
}
}
for(int i=0;i<V;i++)
{
if(spec[i])
{
for(int nxt: adj[i])
{
if(spec[nxt]) cnt_spec[i]++;
}
}
}
vector<int> bits;
int curr=-1;
for(int i=0;i<V;i++)
{
if(spec[i] and cnt_spec[i]==1)
{
if(curr==-1) curr=i;
else if(deg[curr]<deg[i]) curr=i;
}
}
for(int i=0;i<10;i++)
{
bits.push_back(curr);
vis[curr]=1;
if(i==9) break;
for(int nxt: adj[curr])
{
if(spec[nxt] and !vis[nxt])
{
curr=nxt;
break;
}
}
}
spec[s]=1;
//for(int x: bits) cout<<x<<" ";
//cout<<"\n";
for(int bit=0;bit<10;bit++)
{
curr=bits[bit];
for(int nxt: adj[curr])
{
if(!spec[nxt]) number[nxt]+=(1<<bit);
}
}
int num=2;
for(int i=0;i<V-12;i++)
{
num++;
while(__builtin_popcount(num)<=1) num++;
rep[num]=i;
}
vector<pair<int,int>> edges;
for(int i=0;i<U;i++)
{
int u=C[i],v=D[i];
if(!spec[u] and !spec[v]) edges.push_back({rep[number[u]],rep[number[v]]});
}
int sz=edges.size();
//cout<<"->"<<V-12<<" "<<sz<<"\n";
InitMap(V-12,sz);
for(int i=0;i<sz;i++) MakeMap(edges[i].first,edges[i].second);
}
