#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <array>
#include <numeric>
#include <vector>
using namespace std;
void Alice(int N, int M, int A[], int B[]) {
if (N == 1) {
InitG(1, 0);
return;
}
if (N == 2) {
if (M == 0) {
InitG(2, M);
} else {
InitG(2, 1);
MakeG(0, 0, 1);
}
return;
}
int all = 0;
int mark = N + 1;
vector<int> bit(10);
iota(bit.begin(), bit.end(), N + 2);
vector<array<int, 2>> edge;
for (int i = 0; i < M; i++) {
edge.push_back({A[i] + 1, B[i] + 1});
}
for (int i = 1; i <= N; i++) {
edge.push_back({all, i});
for (int j = 0; j < 10; j++) {
if ((i >> j) & 1) {
edge.push_back({i, bit[j]});
}
}
}
for (int i = 0; i < 9; i++) {
edge.push_back({N + i + 2, N + i + 3});
}
edge.push_back({all, mark});
int sz = edge.size();
InitG(N + 12, sz);
for (int i = 0; i < sz; i++) {
MakeG(i, edge[i][0], edge[i][1]);
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <utility>
#include <array>
using namespace std;
void Bob(int V, int U, int C[], int D[]) {
if (V == 1) {
InitMap(1, 0);
return;
}
if (V == 2) {
if (U == 0) {
InitMap(2, 0);
} else {
InitMap(2, 1);
MakeMap(0, 1);
}
return;
}
vector<vector<int>> adj(V);
for (int i = 0; i < U; i++) {
adj[C[i]].push_back(D[i]);
adj[D[i]].push_back(C[i]);
}
int all = -1, mark = -1;
for (int i = 0; i < V; i++) {
if (adj[i].size() == 1) {
int nxt = adj[i][0];
if ((int)(adj[nxt].size()) == V - 11) {
all = nxt;
mark = i;
}
}
}
vector<int> bit_num(V);
for (int i = 0; i < V; i++) {
if (i == all || i == mark) continue;
bool ok = true;
for (auto x : adj[i]) {
if (x == all) {
ok = false;
break;
}
}
bit_num[i] = ok;
}
pair<int, int> ten = {1000001, -1};
for (int i = 0; i < V; i++) {
if (!bit_num[i]) continue;
int cnt = 0;
for (int x : adj[i]) {
if (bit_num[x]) cnt++;
}
if (cnt == 1) {
ten = min(ten, {adj[i].size(), i});
}
}
assert(ten.second != -1);
int prevnum = -1;
int cur = ten.second;
int curp = 512;
while (curp) {
bit_num[cur] = curp;
curp /= 2;
for (int x : adj[cur]) {
if (bit_num[x] && x != prevnum) {
prevnum = cur;
cur = x;
break;
}
}
}
vector<int> correct_num(V);
for (int i = 0; i < V; i++) {
if (!bit_num[i] && i != all && i != mark) {
for (int x : adj[i]) {
correct_num[i] += bit_num[x];
}
}
}
vector<array<int, 2>> edge;
for (int i = 0; i < U; i++) {
int a = correct_num[C[i]];
int b = correct_num[D[i]];
if (a && b) {
edge.push_back({a - 1, b - 1});
}
}
InitMap(V - 12, (int)(edge.size()));
for (auto [a, b] : edge) {
MakeMap(a, b);
}
}
