#include "Alicelib.h"
#include <vector>
using namespace std;
void Alice(int n, int m, int A[], int B[] ){
vector<pair<int, int>> edges;
for (int i = 0; i < m; ++i) {
edges.emplace_back(A[i], B[i]);
}
for (int bit = 0; bit < 10; ++bit) {
for (int node = 0; node < n; ++node) {
if (node & (1 << bit)) {
edges.emplace_back(n + bit, node);
}
}
}
for (int node = 0; node < n; ++node) {
edges.emplace_back(n + 10, node);
}
for (int bit = 1; bit < 10; ++bit) {
edges.emplace_back(n + bit - 1, n + bit);
edges.emplace_back(n + 11, n + bit);
}
InitG(n + 12, edges.size());
for (int i = 0; i < (int)edges.size(); ++i) {
MakeG(i, edges[i].first, edges[i].second);
}
}
#include <bits/stdc++.h>
#include "Boblib.h"
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
bool Try(int n, int special0,
const vector<vector<int>> &adj,
const vector<pair<int, int>> &edges) {
vector<bool> is_bit(n + 12, true);
is_bit[special0] = false;
for (int x : adj[special0]) {
is_bit[x] = false;
}
vector<int> bits;
for (int i = 0; i < n + 12; ++i) {
if (is_bit[i]) bits.emplace_back(i);
}
assert((int)bits.size() == 11);
int special1 = -1;
for (int node : bits) {
int bit_deg = 0;
for (int x : adj[node]) {
bit_deg += is_bit[x];
}
if (bit_deg == 9) {
if (special1 != -1) return false;
special1 = node;
}
}
if (special1 == -1) return false;
// dbg() "Found " << name(special1) endl;
is_bit[special1] = false;
int zero = 0;
for (int bit : bits) {
if (is_bit[bit]) zero ^= bit;
}
for (int bit : adj[special1]) {
zero ^= bit;
}
vector<int> order = {zero};
int node = zero;
is_bit[zero] = false;
for (int it = 0; it < 9; ++it) {
int next = -1;
for (int x : adj[node]) {
if (is_bit[x]) {
if (next != -1) return false;
next = x;
}
}
if (next == -1) return false;
order.emplace_back(node = next);
is_bit[node] = false;
}
for (int bit : order) is_bit[bit] = true; //, dbg() bit << " "; dbg() endl;
is_bit[special0] = is_bit[special1] = true;
vector<int> label(n + 12);
for (int bit = 0; bit < 10; ++bit) {
int node = order[bit];
for (int x : adj[node]) {
if (!is_bit[x]) {
label[x] |= 1 << bit;
}
}
}
vector<int> nodes;
for (int i = 0; i < n + 12; ++i) {
if (!is_bit[i]) nodes.emplace_back(label[i]);
}
sort(nodes.begin(), nodes.end());
if (n != (int)nodes.size()) return false;
for (int i = 0; i < n; ++i) if (nodes[i] != i) return false;
vector<pair<int, int>> new_edges;
for (auto &p : edges) {
int x, y; tie(x, y) = p;
if (!is_bit[x] && !is_bit[y]) {
new_edges.emplace_back(label[x], label[y]);
}
}
sort(new_edges.begin(), new_edges.end());
// dbg() "Edges:\n";
// for (auto &p : new_edges) {
// dbg() p.first << ' ' << p.second << endl;
// }
InitMap(n, new_edges.size());
for (auto &p : new_edges) {
MakeMap(p.first, p.second);
}
return true;
}
void Bob(int V, int U, int C[], int D[]) {
int n = V - 12;
vector<vector<int>> adj(V);
vector<pair<int, int>> edges;
for (int i = 0; i < U; ++i) {
int x = C[i], y = D[i];
edges.emplace_back(x, y);
adj[x].emplace_back(y);
adj[y].emplace_back(x);
}
for (int node = 0; node < V; ++node) {
if ((int)adj[node].size() == n) {
if (Try(n, node, adj, edges)) {
return;
}
}
}
assert(false);
}
