#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
mt19937 rng(time(0));
void Alice(int n, int m, int A[], int B[]){
vector<array<int, 2>> t;
for (int i = 0; i < m; ++i) t.pb({A[i], B[i]});
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 10; ++j) {
if ((i >> j) & 1) t.pb({i, n + 2 + j});
}
}
for (int i = 0; i < 9; ++i) t.pb({n+2+i, n+3+i});
for (int i = 0; i < 10; ++i) t.pb({n, n+2+i});
for (int i = 0; i < n+12; ++i) {
if (i != n && i != n+1) t.pb({i, n+1});
}
InitG(n + 12, t.size());
for (int i = 0; i < t.size(); ++i) {
MakeG(i, t[i][0], t[i][1]);
}
}
// https://www.youtube.com/watch?v=vUqzpujUU7c zeta z orz
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1024;
vector<int> g[N];
int f[N];
bool vis[N];
void Bob(int V, int U, int C[], int D[]){
int n = V - 12, x = 0;
for (int i = 0; i < U; ++i) {
g[C[i]].pb(D[i]);
g[D[i]].pb(C[i]);
}
for (int i = 0; i < V; ++i) {
if (g[i].size() == V-2) {
fill(vis, vis+V, 0);
for (auto x : g[i]) vis[x] = 1;
for (int j = 0; j < V; ++j) {
if (!vis[j] && j != i) x = j;
}
}
}
int z = -1;
for (auto y : g[x]) {
int c = 0;
for (auto i : g[y]) {
if (find(g[x].begin(), g[x].end(), i) != g[x].end()) {
c++;
}
}
if (c == 1 && z == -1) z = y;
if (c == 1 && z != -1 && g[y].size() > g[z].size()) z = y;
}
fill(vis, vis+V, 0);
int c = 0;
while (1) {
vis[z] = 1;
for (auto y : g[z]) f[y] += (1 << c);
int Y = -1;
for (auto y : g[z]) {
if (find(g[x].begin(), g[x].end(), y) != g[x].end() && !vis[y]) {
Y = y;
break;
}
}
if (Y == -1) break;
z = Y, ++c;
}
vector<array<int, 2>> vr;
for (int i = 0; i < V; ++i) {
if (i == x || g[i].size() == V-2 || find(g[i].begin(), g[i].end(), x) != g[i].end()) continue;
for (auto t : g[i]) {
if (f[t] < n && f[i] < f[t] && find(g[t].begin(), g[t].end(), x) == g[t].end()) {
vr.pb({f[i], f[t]});
}
}
}
InitMap(n, vr.size());
for (auto [x, y] : vr) {
MakeMap(x, y);
}
}
