#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
void Alice(int n, int m, int a[], int b[]){
if (n==1||n==2){
InitG(n, m);
return;
}
vector<pii> res;
for (int i=0; i<m; ++i)res.pb(mp(a[i], b[i]));
for (int i=0; i<n; ++i)for (int j=0; j<10; ++j)if (i&(1<<j))res.pb(mp(i, n+j));
for (int i=0; i<10; ++i)res.pb(mp(n+i, n+10));
for (int i=0; i<n+10; ++i)res.pb(mp(i, n+11));
for (int i=0; i<9; ++i)res.pb(mp(n+i, n+i+1));
InitG(n+12, res.size());
for (int i=0; i<res.size(); ++i)MakeG(i, res[i].fi, res[i].se);
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
void Bob(int n, int m, int c[], int d[]){
if (n==1){
InitMap(1, 0);
return;
}
if (n==2){
InitMap(1, 0);
if (m==1)MakeMap(1, 0);
return;
}
vector<int> deg(n, 0);
for (int i=0; i<m; ++i)++deg[c[i]], ++deg[d[i]];
int fat, mx=-1, par, node=-1, d1=0, d2=0;
vector<vector<bool> > graph(n, vector<bool>(n, 0));
for (int i=0; i<n; ++i)if (deg[i]>mx)mx=deg[i], fat=i;
for (int i=0; i<m; ++i)graph[c[i]][d[i]]=graph[d[i]][c[i]]=1;
for (int i=0; i<n; ++i)if (!graph[i][fat]&&i!=fat)par=i;
for (int i=0; i<n; ++i)if (graph[par][i]){
int count=0;
for (int j=0; j<n; ++j)if (graph[par][j]&&graph[i][j])++count;
if (count==1)node=i;
}
vector<bool> visited(n, 0);
vector<int> vect;
bool loop=1;
while (loop){
vect.pb(node);
visited[node]=1;
loop=0;
for (int i=0; i<n; ++i)if (graph[i][node]&&!visited[i]&&graph[par][i]){
node=i, loop=1;
break;
}
}
for (int i=0; i<n; ++i)d1+=graph[vect[0]][i], d2+=graph[vect[9]][i];
if (d1<d2)reverse(vect.begin(), vect.end());
vector<pii> ans;
for (int i=0; i<m; ++i)if (!graph[par][c[i]]&&!graph[par][d[i]]&&c[i]!=fat&&d[i]!=fat&&c[i]!=par&&d[i]!=par){
int a=0, b=0;
for (int j=0; j<10; ++j)if (graph[c[i]][vect[j]])a+=(1<<j);
for (int j=0; j<10; ++j)if (graph[d[i]][vect[j]])b+=(1<<j);
ans.pb(mp(a, b));
}
InitMap(n-12, ans.size());
for (auto a:ans)MakeMap(a.fi, a.se);
}
