#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int deg[1001];
int c=0,bro=0;;
void create(int a,int b){
bro++;
MakeG(c++,a,b);
}
void Alice( int N, int M, int A[], int B[] ){
for(int i=0;i<M;i++)deg[A[i]]++,deg[B[i]]++;
int cnt=0;
for(int i=0;i<N;i++){
for(int j=0;j<10;j++)if((i+1)&(1LL<<j))cnt++;
}
InitG(N+12,M+1+cnt+N+9);
int C=N;
for(int i=0;i<M;i++)create(A[i],B[i]);
//cycle
for(int i=0;i<9;i++){
create(C,C+1);
C++;
}
C++;
create(C,C+1);
C++;
for(int i=0;i<N;i++)create(i,C);
for(int i=0;i<N;i++)for(int j=0;j<10;j++)if((i+1)&(1LL<<j)){
create(i,j+N);
}
}
/*
4 3
0 1
0 2
0 3
*/
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
using namespace std;
vector<int>adj[1001];
int lab[1001];
int val[1001],mark[1001];
vector<int>sp;
void dfs(int cur){
mark[cur]=1;
sp.pb(cur);
for(auto j:adj[cur])if(!mark[j])dfs(j);
}
void Bob( int V, int U, int C[], int D[] ){
int node=-1;
for(int i=0;i<U;i++){
adj[C[i]].pb(D[i]);
adj[D[i]].pb(C[i]);
}
for(int i=0;i<V;i++){
if(adj[i].size()==1&&adj[adj[i][0]].size()==V-11){
if(node!=-1)assert(0);
node=i;
}
}
for(int i=0;i<V;i++)val[i]=-1;
for(auto j:adj[node])node=j;
mark[node]=1;
for(auto j:adj[node])mark[j]=1;
for(int i=0;i<V;i++)if(!mark[i]){
int c=0;
for(auto j:adj[i])if(!mark[j])c++;
if(c==1)dfs(i);
}
if(sp.size()!=10)assert(0);
if(adj[sp[0]].size()<adj[sp.back()].size())reverse(all(sp));
for(int j=0;j<sp.size();j++)val[sp[j]]=j;
vector<pii>ans;
for(int i=0;i<V;i++)if(val[i]==-1&&i!=node&&adj[i].size()>1){
int x=0;
for(auto j:adj[i])if(val[j]!=-1)x+=(1LL<<val[j]);
lab[i]=x;
for(auto j:adj[i])if(val[j]==-1&&j!=node&&j<i){
ans.pb({lab[i],lab[j]});
}
}
InitMap(V-12,ans.size());
for(auto i:ans)MakeMap(i.f-1,i.s-1);
}
