#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
//So it is obvious that you want to make log(n) extra nodes (10, 1 for each bit)
//But how will you determine these nodes
//You can think of using degrees to determine a node
//Add extra nodes X, Y. Connect X with all bit nodes, and connect Y with everything but X
//Y has maximum degree. You can determine X and Y. Then, you can determine the bits
//How to determine order of the bits? connect the bits in a chain. Now you just need to know
//which endpoint of the chain is bit 0. For all 3 <= n <= 1000, bit 0 will have greater degree
void Alice (int n, int m, int A[], int B[]) {
if (n == 1) {
InitG(1, 0);
return;
}
if (n == 2) {
InitG(2, m);
for (int i = 0; i < m; i++) {
MakeG(i, A[i], B[i]);
}
return;
}
vector <pair <int, int>> ee;
for (int i = 0; i < m; i++) {
ee.push_back({A[i], B[i]});
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 10; j++) {
if (i & (1 << j)) {
ee.push_back({i, n + j});
}
}
}
for (int j = 0; j < 10; j++) {
ee.push_back({n + j, n + 10});
}
for (int j = 0; j < n + 10; j++) {
ee.push_back({j, n + 11});
}
for (int j = 0; j + 1 < 10; j++) {
ee.push_back({n + j, n + j + 1});
}
for (auto &[x, y] : ee) {
if (x > y) {
swap(x, y);
}
}
sort(ee.begin(), ee.end());
ee.resize(unique(ee.begin(), ee.end()) - ee.begin());
assert(ee.size() >= 0 && ee.size() <= (n + 12) * (n + 11) / 2);
InitG(n + 12, ee.size());
int cnt = 0;
for (auto [x, y] : ee) {
MakeG(cnt++, x, y);
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob (int v, int u, int C[], int D[]) {
if (v == 1) {
InitMap(v, 0);
return;
}
if (v == 2) {
InitMap(v, u);
if (u == 1) {
MakeMap(0, 1);
}
return;
}
vector <int> deg(v, 0);
for (int i = 0; i < u; i++) {
deg[C[i]]++; deg[D[i]]++;
}
int Y = -1;
for (int i = 0; i < v; i++) {
if (Y == -1 || deg[i] > deg[Y]) {
Y = i;
}
}
vector <int> adj[v];
for (int i = 0; i < v; i++) {
adj[i] = vector <int> (v, 0);
}
for (int i = 0; i < u; i++) {
adj[C[i]][D[i]] = adj[D[i]][C[i]] = 1;
}
int X = -1;
for (int i = 0; i < v; i++) {
if (i != Y && !adj[Y][i]) {
X = i;
}
}
vector <int> ii(v, 0);
vector <int> path;
int start = -1;
for (int i = 0; i < v; i++) {
if (adj[X][i]) {
int d = 0;
for (int j = 0; j < v; j++) {
if (adj[X][j]) {
d += adj[i][j];
}
}
if (d == 1) {
start = i;
}
}
}
while (true) {
assert(start != -1);
path.push_back(start);
ii[start] = 1;
int nxt = -1;
for (int j = 0; j < v; j++) {
if (adj[start][j]) {
if (!ii[j] && adj[X][j]) {
nxt = j;
}
}
}
if (nxt == -1) {
break;
}
swap(start, nxt);
}
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < v; i++) {
cnt1 += adj[path[0]][i];
cnt2 += adj[path[9]][i];
}
if (cnt1 < cnt2) {
reverse(path.begin(), path.end());
}
vector <pair <int, int>> ans;
for (int i = 0; i < u; i++) {
if (C[i] != X && C[i] != Y && !adj[X][C[i]]) {
if (D[i] != X && D[i] != Y && !adj[X][D[i]]) {
int a = 0;
for (int j = 0; j < 10; j++) {
if (adj[C[i]][path[j]]) {
a += 1 << j;
}
}
int b = 0;
for (int j = 0; j < 10; j++) {
if (adj[D[i]][path[j]]) {
b += 1 << j;
}
}
ans.push_back({a, b});
}
}
}
InitMap(v - 12, ans.size());
for (auto [x, y] : ans) {
MakeMap(x, y);
}
}
