#include "Alicelib.h"
#include <iostream>
#include <cassert>
#include <cstdio>
#include <vector>
#define f first
#define s second
using namespace std;
void Alice( int n, int m, int A[], int B[] ) {
vector<pair<int,int>> edge;
for (int i = 0; i < m; i++) edge.push_back({A[i],B[i]});
for (int i = n; i < n+10; i++) for (int j = 0; j < n; j++) if ((j&(1<<(i-n))) > 0) edge.push_back({i,j});
for (int i = n; i < n+10; i++) edge.push_back({n+10,i});
for (int i = 0; i < n+10; i++) edge.push_back({n+11,i});
edge.push_back({n,n+1});
edge.push_back({n,n+2});
edge.push_back({n+2,n+3});
edge.push_back({n,n+4});
for (int i = n+4; i < n+9; i++) edge.push_back({i,i+1});
InitG(n+12,edge.size());
for (int i = 0; i < edge.size(); i++) MakeG(i,edge[i].f,edge[i].s);
}
#include "Boblib.h"
#include <iostream>
#include <cassert>
#include <cstdio>
#include <vector>
#define f first
#define s second
using namespace std;
vector<int> edge[1020];
vector<pair<int,int>> ans;
int p[1020], d[1020];
void dfs(int u, int v) {
for (int i = 0; i < edge[u].size(); i++) if ((edge[u][i] != v) && (p[edge[u][i]] == -1)) dfs(edge[u][i],u), d[u] = d[edge[u][i]]+1;
}
void dfs2(int u, int cnt) {
p[u] = cnt;
for (int i = 0; i < edge[u].size(); i++) if (p[edge[u][i]] == -1) dfs2(edge[u][i],cnt+1);
}
void Bob( int n, int m, int C[], int D[] ) {
pair<int,int> maxx;
for (int i = 0; i < m; i++) edge[C[i]].push_back(D[i]), edge[D[i]].push_back(C[i]);
for (int i = 0; i < n; i++) {
if (edge[i].size() == n-2) {
p[i] = n-1;
for (int j = 0; j < n; j++) if (j != i) p[j] = n-2;
for (int j = 0; j < edge[i].size(); j++) p[edge[i][j]] = 0;
break;
}
}
for (int i = 0; i < n; i++) {
if (p[i] == n-2) {
for (int j = 0; j < edge[i].size(); j++) p[edge[i][j]] = -1;
for (int j = 0; j < n; j++) {
if (p[j] == -1) {
int cnt = 0;
for (int k = 0; k < edge[j].size(); k++) if (p[edge[j][k]] == -1) cnt++;
maxx = max(maxx,{cnt,j});
}
}
p[maxx.s] = n-12;
dfs(maxx.s,-1);
for (int j = 0; j < edge[maxx.s].size(); j++) {
int u = edge[maxx.s][j];
if (p[u] == -1) {
if (d[u] == 0) {
p[u] = n-11;
} else if (d[u] == 1) {
dfs2(u,n-10);
} else {
dfs2(u,n-8);
}
}
}
break;
}
}
for (int i = 0; i < n; i++) {
if ((n-12 <= p[i]) && (p[i] < n-2)) {
for (int j = 0; j < edge[i].size(); j++) {
if (n-12 <= p[edge[i][j]]) continue;
p[edge[i][j]] += (1<<(p[i]-(n-12)));
}
}
}
for (int i = 0; i < m; i++) if ((p[C[i]] < n-12) && (p[D[i]] < n-12)) ans.push_back({p[C[i]],p[D[i]]});
InitMap(n-12,ans.size());
for (int i = 0; i < ans.size(); i++) MakeMap(ans[i].f,ans[i].s);
}
