#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;
// von Z := N + 10 zu allen Knoten von G
for (int i = 0; i < N; ++i)
edges.push_back({N + 10, i});
// von C := N + 11 zu allen Kontrolknoten
for (int i = 0; i < 11; ++i)
edges.push_back({N + 11, N + i});
// Zwischen den Count Bits (der letzte zu Z)
for (int b = 0; b < 10; ++b)
edges.push_back({N + b, N + b + 1});
// für alle anderen Knoten im Graph:
for (int v = 0; v < N; ++v)
for (int b = 0; b < 10; ++b)
if (v & (1 << b))
edges.push_back({v, N + b});
// Ausfüllen
InitG(N + 12, M + sz(edges));
int idx = 0;
for (int i = 0; i < M; ++i)
MakeG(idx++, A[i], B[i]);
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;
for (int u : adj[v])
{
if (rename[u] != -1)
continue;
dfs(adj, u, countBits, rename);
}
countBits.push_back(v);
}
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]);
bool poss = false;
int c = -1, z = -1;
for (int cc = 0; cc < V; ++cc)
{
if (sz(adj[cc]) != 11)
continue;
for (int cz : adj[cc])
{
if (sz(adj[cz]) != V - 10)
continue;
vb nodes(V, false);
for (int x : adj[cz])
nodes[x] = true;
for (int x : adj[cc])
nodes[x] = true;
poss = true;
for (bool x : nodes)
if (!x)
poss = false;
if (poss)
{
c = cc;
z = cz;
}
}
if (poss)
break;
}
vi rename(V, 0);
rename[c] = -2;
for (int x : adj[c])
rename[x] = -1;
vi countBits;
dfs(adj, z, 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 += 21; // 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], rename[u]);
}
}
