#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <iostream>
#include <array>
#include <vector>
#define ll long long
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
vector <array<ll, 2>> V;
ll k = N, tot = 0, cnt = N;
while (k) {
k /= 2;
++tot;
}
for (int i=0; i<M; ++i) {
V.push_back({A[i], B[i]});
}
k = 1;
if (tot != 10) {
V.push_back({cnt, cnt+1});
++cnt;
}
for (int i=0; i<tot; ++i) {
for (int j=0; j<N; ++j) {
if ((j+1) & k) V.push_back({cnt, j});
}
if (i != tot-1) V.push_back({cnt, cnt+1});
++cnt, k *= 2;
}
for (int i=0; i<cnt; ++i) {
V.push_back({i, cnt});
}
if (N < 10) {
for (int i=1; i<5; ++i) {
++cnt;
V.push_back({cnt-i, cnt});
}
}
++cnt;
for (int j=N; j<N+tot+(tot != 10 ? 1 : 0); ++j) {
V.push_back({j, cnt});
}
++cnt;
InitG(cnt, V.size());
int i = 0;
for (auto [a, b] : V) {
//cout << a << " " << b << endl;
MakeG(i++, a, b);
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long
using namespace std;
ll in[2000], F[2000];
bool B[2000], G[2000];
vector <ll> adj[2000];
vector <array<ll, 2> > V, X;
ll n, x, z, rt = 0;
void dfs(ll u, ll p, ll k) {
for (auto v : adj[u]) {
if (!G[v] && v != rt && v != z) {
F[v] += k;
}
}
for (auto v : adj[u]) {
if (G[v] && v != p) dfs(v, u, (!k ? 1 : k*2));
}
}
void Bob( int Z, int U, int C[], int D[] ){
n = Z;
V.clear();
X.clear();
for (int i=0; i<n; ++i) in[i] = B[i] = F[i] = G[i] = 0, adj[i].clear();
for (int i=0; i<U; ++i) {
++in[C[i]], ++in[D[i]];
adj[C[i]].push_back(D[i]);
adj[D[i]].push_back(C[i]);
}
x = 0;
for (int i=0; i<n; ++i) {
if (in[i] == 1) --x;
if (in[i] == n-2) {
rt = i;
}
}
B[rt] = 1;
for (auto v : adj[rt]) {
B[v] = 1;
}
z = rt;
for (int i=0; i<n; ++i) {
if (!B[i]) {
rt = i;
break;
}
}
x += Z-2-adj[rt].size();
for (auto v : adj[rt]) {
in[v] -= 2;
//cout << v << " " << in[v] << endl;
G[v] = 1;
}
bool ok = 0;
for (auto v : adj[rt]) {
if (in[v] == 1) {
ok = 1;
dfs(v, -1, 0);
break;
}
}
if (!ok) {
ll mx = -1, id = -1, deg;
for (auto v : adj[rt]) {
deg = 0;
for (auto x : adj[v]) {
if (G[x]) ++deg;
}
if (deg == 1 && mx < in[v]) {
mx = in[v];
id = v;
}
}
dfs(id, -1, 1);
}
/*for (int i=0; i<n; ++i) {
cout << F[i] << " ";
}
cout << endl;*/
for (int i=0; i<U; ++i) {
if (F[C[i]] && F[D[i]]) {
//cout << F[C[i]]-1 << " " << F[D[i]]-1 << endl;
V.push_back({F[C[i]]-1, F[D[i]]-1});
}
}
InitMap(x, V.size());
for (auto [a, b] : V) {
MakeMap(a, b);
}
}
