#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice(int n, int m, int a[], int b[]){
vector <pair<int,int>> v;
int i,j,tmp;
for(i=0;i<m;i++){
v.push_back({a[i],b[i]});
}
for(i=0;i<n;i++){
tmp=i;
j=0;
while(tmp>0){
if(tmp%2) v.push_back({i,n+j});
tmp/=2;
j++;
}
}
for(i=0;i<n+10;i++){
v.push_back({i,n+10});
}
for(i=n;i<n+10;i++){
v.push_back({i,n+11});
if(i!=n+9) v.push_back({i,i+1});
}
v.push_back({n,n+2});
v.push_back({n,n+3});
v.push_back({n,n+4});
InitG(n+12,v.size());
for(i=0;i<v.size();i++){
MakeG(i,v[i].first,v[i].second);
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
#define maxN 1020
using namespace std;
vector <int> v,adj[maxN];
bool k[maxN];
void dfs(int n){
v.push_back(n);
k[n]=false;
int i;
for(i=0;i<adj[n].size();i++){
if(k[adj[n][i]]){
dfs(adj[n][i]);
}
}
}
void Bob(int n, int m, int a[], int b[]){
int i,j,id,tmp,pom,p[maxN];
int ar[maxN],deg[maxN];
for(i=0;i<m;i++){
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
for(i=0;i<n;i++){
if(adj[i].size()==n-2) id=i;
}
tmp=id;
for(i=0;i<n;i++){
if(i==id) continue;
bool x=false;
for(j=0;j<adj[i].size();j++){
if(adj[i][j]==id) {x=true; break;}
}
if(!x) break;
}
id=i;
for(i=0;i<adj[id].size();i++) k[adj[id][i]]=true;
for(i=0;i<adj[id].size();i++){
pom=0;
for(j=0;j<adj[adj[id][i]].size();j++){
if(k[adj[adj[id][i]][j]]) pom++;
}
deg[adj[id][i]]=pom;
}
for(i=0;i<adj[id].size();i++){
if(deg[adj[id][i]]==4){
v.push_back(adj[id][i]);
k[adj[id][i]]=false;
}
if(deg[adj[id][i]]==1) pom=adj[id][i];
}
dfs(pom);
reverse(v.begin()+1,v.end());
for(i=0;i<v.size();i++) {k[v[i]]=true; ar[v[i]]=i;}
for(i=0;i<n;i++){
if(k[i] || i==id || i==tmp) continue;
pom=0;
for(j=0;j<adj[i].size();j++){
if(k[adj[i][j]]){
pom+=(1<<ar[adj[i][j]]);
}
}
p[i]=pom;
}
vector <pair<int,int>> u;
for(i=0;i<m;i++){
if(k[a[i]] || a[i]==id || a[i]==tmp || k[b[i]] || b[i]==id || b[i]==tmp) continue;
u.push_back({p[a[i]],p[b[i]]});
}
InitMap(n-12,u.size());
for(i=0;i<u.size();i++) MakeMap(u[i].first,u[i].second);
}
