#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
void Alice(int n,int m,int a[],int b[]){
vector<pair<int,int>> edges;
for(int i=0;i<m;i++){
edges.push_back({a[i],b[i]});
}
for(int i=1;i<=n;i++){
for(int j=0;j<10;j++){
if(i&(1<<j)){
edges.push_back({i-1,n+j});
}
}
}
for(int i=0;i<10;i++){
edges.push_back({n+i,n+10});
}
for(int i=0;i<n+10;i++){
edges.push_back({i,n+11});
}
for(int i=0;i+1<10;i++){
edges.push_back({n+i,n+i+1});
}
InitG(n+12,edges.size());
for(int i=0;i<edges.size();i++){
MakeG(i,edges[i].first,edges[i].second);
}
}
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
void Bob(int n,int m,int c[],int d[]){
int N=n-12;
int val[n];
memset(val,-1,sizeof(val));
int deg[n]={0};
vector<vector<int>> graph(n);
for(int i=0;i<m;i++){
graph[c[i]].push_back(d[i]),graph[d[i]].push_back(c[i]);
deg[c[i]]++,deg[d[i]]++;
}
int group[n]={0};
for(int r=0;r<n;r++){
if(deg[r]==n-2){
val[r]=N+11;
for(int u=0;u<n;u++){
if(u!=r){
val[u]=N+10;
}
}
for(int u:graph[r]){
val[u]=-1;
}
}
}
for(int u=0;u<n;u++){
if(val[u]!=-1){
group[u]=2;
}
}
int s=-1;
for(int u=0;u<n;u++){
if(val[u]==N+10){
for(int v:graph[u]){
group[v]=1;
}
for(int v:graph[u]){
int cnt[2]={0};
for(int w:graph[v]){
if(group[w]<=1){
cnt[group[w]]++;
}
}
if(cnt[1]==1&&cnt[0]==((N+1)/2)){
int s=v,tim=N;
while(true){
bool flag=false;
val[s]=tim;
tim++;
for(int w:graph[s]){
if(group[w]==1&&val[w]==-1){
s=w,flag=true;
break;
}
}
if(!flag){
break;
}
}
}
}
}
}
vector<pair<int,int>> edges;
for(int u=0;u<n;u++){
if(!group[u]){
for(int v:graph[u]){
if(group[v]==1){
val[u]+=(1<<(val[v]-N));
}
}
}
}
for(int u=0;u<n;u++){
for(int v:graph[u]){
if(u<v&&!group[u]&&!group[v]){
edges.push_back({val[u],val[v]});
}
}
}
InitMap(N,edges.size());
for(int i=0;i<edges.size();i++){
MakeMap(edges[i].first,edges[i].second);
}
}
