#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
struct edge_t {
int u, v;
edge_t() {}
edge_t(int u, int v) : u(u), v(v) {}
};
}
void Alice(int N, int M, int A[], int B[]) {
if (N == 1) return InitG(1, 0);
vector<edge_t> edges;
vector<int> BIT(10);
for (int i = 0; i < 10; i++) BIT[i] = N + i;
int ALL = N + 10, HUB = N + 11;
// Original Edges
for (int i = 0; i < M; i++) {
edges.emplace_back(A[i], B[i]);
}
// Connect each vertex to its corresponding BIT vertex to be able to restore identity
for (int i = 0; i < N; i++) {
for (int j = 0; j < 10; j++) {
if (i & (1 << j)) {
edges.emplace_back(i, BIT[j]);
}
}
}
// Connect every vertex except HUB to ALL
for (int i = 0; i < N + 10; i++) {
edges.emplace_back(ALL, i);
}
// Connect every BIT vertex to HUB
for (int i = 0; i < 10; i++) {
edges.emplace_back(HUB, BIT[i]);
}
// Connect every BIT to the preceding and following bit position
for (int i = 0; i < 9; i++) {
edges.emplace_back(BIT[i], BIT[i + 1]);
}
// Initialize Transformed Graph
InitG(N + 12, edges.size());
for (int i = 0; i < edges.size(); i++) {
MakeG(i, edges[i].u, edges[i].v);
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
struct edge_t {
int u, v;
edge_t() {}
edge_t(int u, int v) : u(u), v(v) {}
};
}
void Bob(int V, int U, int C[], int D[]) {
if (V == 1) return InitMap(1, 0);
vector<edge_t> edges;
int N = V - 12;
vector<int> BIT(10, -1);
int ALL = -1, HUB = -1;
vector<int> degree(V, 0);
vector<vector<bool>> adj(V, vector<bool>(V, false));
for (int i = 0; i < U; i++) {
degree[C[i]]++;
degree[D[i]]++;
adj[C[i]][D[i]] = adj[D[i]][C[i]] = true;
}
// Recover ALL
for (int i = 0; i < V; i++) {
if (degree[i] == N + 10) { // ALL is the only vertex connected to N + 10 other vertices
ALL = i;
break;
}
}
// Recover HUB
for (int i = 0; i < V; i++) {
if (ALL != i && !adj[ALL][i]) { // HUB is the only vertex not connected to ALL
HUB = i;
break;
}
}
{ // Recover BIT
vector<int> BIT_shuffled; // shuffled BITs, will be recovered later
vector<int> HUB_deg(V); // degree of verticeswhen only considering edges where both endpoints are adjacent to HUB
vector<vector<bool>> HUB_adj(V, vector<bool>(V, false)); // adjacency matrix of vertices adjacent to hub
for (int i = 0; i < V; i++) {
if (HUB != i && adj[HUB][i]) { // HUB is only connected to BITs
BIT_shuffled.emplace_back(i);
}
}
// Adjacency matrix consisting of elements where both edge endpoints are connected to HUB
for (auto bit : BIT_shuffled) {
for (int v = 0; v < V; v++) {
if (v == bit) continue;
if (v == HUB) continue;
if (adj[bit][v] && adj[HUB][v]) {
HUB_adj[bit][v] = HUB_adj[v][bit] = true;
HUB_deg[bit]++;
HUB_deg[v]++;
}
}
}
// Each edge is double counted, so we divide them
for (auto bit : BIT_shuffled) {
HUB_deg[bit] /= 2;
}
// Find endpoint of BIT line
int first = -1, last = -1;
for (auto bit : BIT_shuffled) {
if (HUB_deg[bit] == 1) {
if (first == -1) {
first = bit;
} else {
last = bit;
}
}
}
if (degree[first] < degree[last]) {
swap(first, last); // BIT[0] > BIT[N - 1], we can uniquely identify the BIT sequence
}
// Recover Line of BITs
for (int cur = first, cnt = 0, prv = -1; cnt < 10; cnt++) {
BIT[cnt] = cur;
for (int nxt = 0; nxt < V; nxt++) {
if (cur != nxt && prv != nxt && HUB_adj[cur][nxt]) {
prv = cur;
cur = nxt;
break;
}
}
}
}
auto OriginalVertex = [&](int X) {
bool res = false;
res |= X == ALL;
res |= X == HUB;
for (int i = 0; i < 10; i++) {
res |= X == BIT[i];
}
return !res;
};
for (int i = 0; i < U; i++) {
if (OriginalVertex(C[i]) && OriginalVertex(D[i])) {
edges.emplace_back(C[i], D[i]);
}
}
auto GetIdentity = [&](int X) {
int id = 0;
for (int i = 0; i < 10; i++) {
if (adj[X][BIT[i]]) {
id |= 1 << i;
}
}
return id;
};
for (int i = 0; i < edges.size(); i++) {
edges[i].u = GetIdentity(edges[i].u);
edges[i].v = GetIdentity(edges[i].v);
}
InitMap(N, edges.size());
for (auto e : edges) {
MakeMap(e.u, e.v);
}
}
