#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
void Alice( int n, int m, int a[], int b[] ){
//InitG( 3, 2 );
//MakeG( 1, 2 );
//MakeG( 1, 3 );
vector<pii> edges;
rep(m) edges.pb({a[i],b[i]});
rep(n) rep1(j,10) if(i&pow2(j)) edges.pb({i,n+j});
rep(9) edges.pb({n+i,n+i+1});
rep(n) edges.pb({i,n+10});
rep(10) edges.pb({n+i,n+10}),edges.pb({n+i,n+11});
InitG(n+12,sz(edges));
rep(sz(edges)) MakeG(i,edges[i].first,edges[i].second);
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define maxn 1505
static bool vis[maxn];
static vector<int> adj[maxn],vec,vec1;
static void dfs(int u, int par){
vec.pb(u);
for(auto v: adj[u]) if(v!=par&&vis[v]) dfs(v,u);
}
void Bob( int n, int m, int a[], int b[] ){
//InitMap( 3, 2 );
//MakeMap( 1, 2 );
//MakeMap( 1, 3 );
int deg[maxn],deg2[maxn],val[maxn],id[maxn];
memset(deg,0,sizeof deg);
rep(m) deg[a[i]]++,deg[b[i]]++;
rep(m) adj[a[i]].pb(b[i]),adj[b[i]].pb(a[i]);
int x=max_element(deg,deg+maxn)-deg,y;
memset(vis,0,sizeof vis);
for(auto v: adj[x]) vis[v]=1;
rep(n) if(x!=i&&!vis[i]) y=i;
memset(vis,0,sizeof vis);
for(auto v: adj[y]) vis[v]=1;
for(auto v: adj[y]) deg2[v]=0;
rep(m) if(vis[a[i]]&&vis[b[i]]) deg2[a[i]]++,deg2[b[i]]++;
for(auto v: adj[y]) if(deg2[v]==1) vec1.pb(v);
if(deg[vec1[0]]>deg[vec1[1]]) dfs(vec1[0],-1);
else dfs(vec1[1],-1);
rep(10) val[vec[i]]=i;
rep(n) if(i!=x&&i!=y&&!vis[i]){
id[i]=0;
for(auto v: adj[i]){
if(vis[v]) id[i]+=1<<val[v];
}
//cout << id[i] << "\n";
}
vector<pii> edges;
rep(m) if(a[i]!=x&&a[i]!=y&&(!vis[a[i]])&&b[i]!=x&&b[i]!=y&&(!vis[b[i]])) edges.pb({id[a[i]],id[b[i]]});
InitMap(n-12,sz(edges));
//for(auto& [x,y]: edges) cout << x << ' ' << y << "\n";
for(auto& [x,y]: edges) MakeMap(x,y);
}
