#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
void Alice( int N, int M, int A[], int B[] ){
static ll n,m;
n = N;
m = M;
vector<pair<ll,ll>> ans;
for(int i = 0; i < m; i++) ans.pb({A[i], B[i]});
for(int i = 0; i < n + 10; i++) ans.pb({n + 10, i});
for(int i = n; i < n + 10; i++) ans.pb({n + 11, i});
for(int i = 0; i < n; i++){
for(int bit = 0; bit < 10; bit++){
if((1 << bit) & i) ans.pb({i, n + bit});
}
}
for(int i = n + 2; i < n + 10; i++) ans.pb({i, i - 1});
for(int i = n + 2; i < n + 10; i++) ans.pb({n, i});
InitG(n + 12, ans.size());
ll cc = 0;
for(auto it : ans) MakeG(cc++, it.ff, it.sd);
// for(auto it : ans) cout << it.ff << ' ' << it.sd << endl;
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
static const int mxN = 2005;
static bool vis1[mxN],vis[mxN],edge[mxN][mxN];
static vector<ll> v[mxN];
void Bob( int V, int U, int C[], int D[] ){
static ll n,m;
vector<ll> bit(20, -1),val(mxN,0LL);
n = V;
m = U;
for(int i = 0; i < m; i++){
v[C[i]].pb(D[i]);
v[D[i]].pb(C[i]);
edge[C[i]][D[i]] = edge[D[i]][C[i]] = true;
}
ll st = 0;
for(int i = 0; i < n; i++){
if(v[i].size() == n - 2) st = i;
// else assert(v[i].size() < n - 2);
}
// cout << " --> " << st << endl;
vis1[st] = true;
vis[st] = true;
for(auto it : v[st]) vis1[it] = true;
for(int i = 0; i < n; i++){
if(!vis1[i]) st = i;
}
// cout << " --> " << st << ' ' << v[st].size() << endl;
// for(int i = 0; i < n; i++) vis1[i] = false;
vis[st] = true;
vector<ll> vv;
for(auto it : v[st]){
vv.pb(it);
// vis[it] = true;
}
for(auto at : vv){
ll ok = 2;
for(auto it : vv){
if(it == at) continue;
if(!edge[it][at]){
ok--;
bit[1] = it;
}
}
if(ok > 0){
bit[0] = at;
break;
}
}
// cout << bit[0] << ' ' << bit[1] << endl;
vis[bit[0]] = vis[bit[1]] = true;
for(int i = 2; i < 10; i++){
for(auto it : vv){
if(edge[it][bit[i - 1]] and !vis[it]){
vis[it] = true;
bit[i] = it;
break;
}
}
}
// for(int i = 0; i < n; i++){
// for(int j = 0; j < n; j++) cout << edge[i][j] << ' ';
// cout << endl;
// }
// for(auto it : vv) cout << it << ' ';
// cout << endl;
// for(int i = 0; i < 10; i++) cout << bit[i] << ' ' << v[bit[i]].size() << endl;
// cout << endl;
vector<pair<ll,ll>> ans;
for(int i = 0; i < n; i++){
if(vis[i]) continue;
val[i] = 0;
for(int j = 0; j < 10; j++) if(edge[bit[j]][i]) val[i] += (1 << j);
// cout << i << " ----> " << val[i] << endl;
}
for(int i = 0; i < n; i++){
if(vis[i]) continue;
for(auto it : v[i]) if(!vis[it] and i < it) ans.pb({val[i], val[it]});
}
// for(auto it : ans) cout << it.ff << ' ' << it.sd << endl;
InitMap(n - 12, ans.size());
for(auto it : ans) MakeMap(it.ff, it.sd);
}
