#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
void Alice(int N, int M, int A[], int B[])
{
vpii edges;
// Knoten sind 1 Indiziert...
// von Z := 0 zu allen Knoten von G
for (int i = 1; i <= N; ++i)
edges.push_back({0, i});
// Zwischen den Count Bits
for (int b = 0; b + 1 < 10; ++b)
edges.push_back({N + b + 1, N + b + 2});
// Kontrollbit K = N+11 zu Z = 0
edges.push_back({0, N + 11});
// für alle anderen Knoten im Graph:
for (int v = 1; v <= N; ++v)
for (int b = 0; b < 10; ++b)
if (v & (1 << b))
edges.push_back({v, N + b + 1});
// Ausfüllen
InitG(N + 12, M + sz(edges));
int idx = 0;
for (int i = 0; i < M; ++i)
MakeG(idx++, A[i] + 1, B[i] + 1);
for (pii e : edges)
MakeG(idx++, e.first, e.second);
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
#define sz(x) (int)(x).size()
void dfs(vvi &adj, int v, vi &countBits, vi &rename)
{
rename[v] = -2;
countBits.push_back(v);
for (int u : adj[v])
{
if (rename[u] == -1)
dfs(adj, u, countBits, rename);
}
}
void Bob(int V, int U, int C[], int D[])
{
vvi adj(V);
for (int i = 0; i < U; ++i)
adj[C[i]].push_back(D[i]), adj[D[i]].push_back(C[i]);
int k = -1;
for (int v = 0; v < V; ++v)
if (sz(adj[v]) == 1 && sz(adj[adj[v][0]]) == V - 11)
// es kann maximal zwei Kandidaten sz(adj[v]) == 1 geben (k und cnt_9)
k = v;
int z = adj[k][0];
vi rename(V, -1);
for (int x : adj[z])
rename[x] = 0; // alle Normalen Knoten und k werden mit 0 bennant
rename[k] = rename[z] = -2; // k wieder extra Rolle
pii cnt0 = {-1, -1}; // { degree , node }
for (int v = 0; v < V; ++v)
if (rename[v] == -1) // alle Count Bits
{
int neighbors = 0;
for (int x : adj[v])
if (rename[x] == -1)
++neighbors;
if (neighbors == 1)
cnt0 = max(cnt0, {sz(adj[v]), v});
}
vi countBits;
dfs(adj, cnt0.second, countBits, rename);
for (int b = 0; b < 10; ++b)
{
for (int v : adj[countBits[b]])
if (rename[v] >= 0)
rename[v] += (1 << b);
}
int M = 0;
for (int v = 0; v < V; ++v)
// Alle Kanten zwischen den Kontrollknoten und den Normalen werden enternt
M += sz(adj[v]) * ((rename[v] >= 0) ? 1 : -1);
M /= 2;
M += 1 + 9; // Kanten zwischen den Knotrollknoten, müssen noch addiert werden.
InitMap(V - 12, M);
for (int v = 0; v < V; ++v)
{
if (rename[v] < 0)
continue;
for (int u : adj[v])
if (rename[u] >= 0 && rename[v] > rename[u])
MakeMap(rename[v] - 1, rename[u] - 1);
}
}
