#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(1, 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});
}
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;
}
}
set <int> adj[v];
for (int i = 0; i < u; i++) {
adj[C[i]].insert(D[i]);
adj[D[i]].insert(C[i]);
}
int X = -1;
for (int i = 0; i < v; i++) {
if (i != Y && !adj[Y].count(i)) {
X = i;
}
}
set <int> ii;
vector <int> path;
int start = -1;
for (auto i : adj[X]) {
int d = 0;
for (auto j : adj[X]) {
d += adj[i].count(j);
}
if (d == 1) {
start = i;
}
}
while (true) {
path.push_back(start);
ii.insert(start);
int nxt = -1;
for (auto j : adj[start]) {
if (!ii.count(j) && adj[X].count(j)) {
nxt = j;
}
}
if (nxt == -1) {
break;
}
swap(start, nxt);
}
if (adj[path[0]].size() < adj[path[9]].size()) {
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].count(C[i])) {
if (D[i] != X && D[i] != Y && !adj[X].count(D[i])) {
int a = 0;
for (int j = 0; j < 10; j++) {
if (adj[C[i]].count(path[j])) {
a += 1 << j;
}
}
int b = 0;
for (int j = 0; j < 10; j++) {
if (adj[D[i]].count(path[j])) {
b += 1 << j;
}
}
ans.push_back({a, b});
}
}
}
InitMap(v - 12, ans.size());
for (auto [x, y] : ans) {
MakeMap(x, y);
}
}
