#include "Alicelib.h"
#include <cassert>
#include <vector>
#include <cstdio>
using namespace std;
void AliceLt30(int N, int M, int* A, int* B, vector<pair<int, int>>& E) {
int root = N + 1, id = N + 2, zero = N + 3;
E.push_back({root, zero});
E.push_back({N, zero});
for (int n = 1; n < 9; n++)
E.push_back({root, zero + n}),
E.push_back({N, zero + n}),
E.push_back({zero + n - 1, zero + n});
E.push_back({id, zero});
for (int x = 0; x < N; x++) {
int c = x, i = 0;
while (c > 0) {
if (c & 1)
E.push_back({x, zero + i});
c >>= 1, i++;
}
}
}
void AliceGt30(int N, int M, int* A, int* B, vector<pair<int, int>>& E) {
int root = N + 1, zero = N + 2;
E.push_back({root, zero});
for (int n = 1; n < 10; n++)
E.push_back({root, zero + n}),
E.push_back({N, zero + n}),
E.push_back({zero + n - 1, zero + n});
for (int x = 0; x < N; x++) {
int c = x, i = 0;
while (c > 0) {
if (c & 1)
E.push_back({x, zero + i});
c >>= 1, i++;
}
}
}
void Alice( int N, int M, int A[], int B[] ){
vector<pair<int, int>> E;
E.reserve(M + N);
for (int m = 0; m < M; m++)
E.push_back({A[m], B[m]});
for (int n = 0; n < N; n++)
E.push_back({n, N});
if (N <= 500)
AliceLt30(N, M, A, B, E);
else
AliceGt30(N, M, A, B, E);
InitG(N + 12, E.size());
for (int i = 0; i < E.size(); i++)
MakeG(i, E[i].first, E[i].second);
}
#include "Boblib.h"
#include <algorithm>
#include <cassert>
#include <mutex>
#include <vector>
#include <cstdio>
#include <map>
#include <set>
using namespace std;
#define assert(x)
void Bob( int V, int U, int C[], int D[] ){
if (V == 2) {
InitMap(V, U);
if (U)
MakeMap(C[0], D[0]);
return;
}
vector<vector<int>> A(V);
for (int e = 0; e < U; e++) {
A[C[e]].push_back(D[e]);
A[D[e]].push_back(C[e]);
}
int Gid, Gsz = 0;
for (int x = 0; x < V; x++)
if (A[x].size() > Gsz)
Gsz = A[x].size(), Gid = x;
sort(A[Gid].begin(), A[Gid].end());
vector<int> nodes;
nodes.reserve(2);
int o = 0;
for (int id = 0; id < V; id++) {
if (id == Gid) continue;
if (A[Gid][o] == id) {
o++;
continue;
}
nodes.push_back(id);
} assert(nodes.size() == 2);
if ((V - 12) > 500) {
int R = nodes[0], ZR = nodes[1];
if (A[ZR].size() == 10)
swap(R, ZR);
set<int> EX = {
Gid, R, ZR
};
map<int, int> indexes; {
set<int> G;
for (int x = 0; x < 10; x++)
G.insert(A[R][x]), EX.insert(A[R][x]);
indexes[ZR] = 0;
int last = ZR;
G.erase(last);
for (int i = 1; i < 10; i++) {
bool found = 0;
for (int j: A[last]) {
if (!G.count(j)) continue;
last = j;
indexes[j] = i;
found = 1;
break;
} assert(found);
G.erase(last);
}
}
map<int, int> transl;
for (int v = 0; v < V; v++) {
if (EX.count(v)) continue;
int realv = 0;
for (int c: A[v]) {
if (!indexes.count(c)) continue;
realv |= 1 << indexes[c];
}
transl[v] = realv;
}
vector<pair<int, int>> edges;
for (int e = 0; e < U; e++) {
if (EX.count(C[e]) || EX.count(D[e])) continue;
edges.push_back({transl[C[e]], transl[D[e]]});
}
InitMap(V - 12, edges.size());
for (auto [a, b]: edges)
MakeMap(a, b);
} else {
int R = nodes[0], ZR = nodes[1];
if (A[nodes[0]].size() == 1)
swap(R, ZR);
assert(A[R].size() == 9);
assert(A[ZR].size() == 1);
set<int> EX = {Gid, R, ZR};
map<int, int> indexes; {
set<int> G;
for (int x = 0; x < 9; x++)
G.insert(A[R][x]), EX.insert(A[R][x]);
// for (int c: G)
// printf("%d ", c);
// printf("\n");
indexes[A[ZR][0]] = 0;
int last = A[ZR][0];
G.erase(last);
for (int i = 1; i < 9; i++) {
bool found = 0;
for (int j: A[last]) {
if (!G.count(j)) continue;
last = j;
indexes[j] = i;
found = 1;
break;
}
assert(found);
G.erase(last);
}
}
map<int, int> transl;
for (int v = 0; v < V; v++) {
if (EX.count(v)) continue;
int realv = 0;
for (int c: A[v]) {
if (!indexes.count(c)) continue;
realv |= 1 << indexes[c];
}
transl[v] = realv;
}
vector<pair<int, int>> edges;
for (int e = 0; e < U; e++) {
if (EX.count(C[e]) || EX.count(D[e])) continue;
edges.push_back({transl[C[e]], transl[D[e]]});
}
InitMap(V - 12, edges.size());
for (auto [a, b]: edges)
MakeMap(a, b);
}
}
