#include <bits/stdc++.h>
#include "Alicelib.h"
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>
using namespace std;
ll n, _to, _ax;
vector<vector<ll>> adj;
ll bit_node(ll b) { return _ax+1+b; }
void Alice( int N, int M, int A[], int B[] ){
n = N;
_to = n;
_ax = _to+1;
adj.resize(n + 12);
ll cnt = 0;
range(i, 0, n) {
adj[_to].push_back(i);
cnt++;
range(b, 0, 10) {
if (i & (1 << b)) {
adj[bit_node(b)].push_back(i);
cnt++;
}
}
}
range(i, 0, 9) {
adj[bit_node(i)].push_back(bit_node(i+1));
cnt++;
}
range(i, 0, M) {
adj[A[i]].push_back(B[i]);
cnt++;
}
adj[_ax].push_back(_to);
cnt++;
// cout << "V = " << N+12 << " U = " << cnt << '\n';
InitG(N+12, cnt);
cnt = 0;
range(i, 0, n + 12) {
for (ll& j : adj[i]) {
// cout << cnt << ' ' << i << ' ' << j << '\n';
MakeG(cnt++, i, j);
}
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>
using namespace std;
ll N;
ll ax, to;
vector<vector<ll>> alice_adj;
vector<bool> not_bit;
vector<ll> cast;
void translate_nodes(ll node, ll bit, ll last_node) {
for (ll i : alice_adj[node]) {
if (!not_bit[i] && i != last_node) {
translate_nodes(i, bit+1, node);
continue;
}
cast[i] += (1 << bit);
}
}
void Bob( int V, int U, int C[], int D[]){
N = V - 12;
alice_adj.resize(V);
not_bit.resize(V);
cast.resize(V);
range(i, 0, U) {
alice_adj[C[i]].push_back(D[i]);
alice_adj[D[i]].push_back(C[i]);
}
range(i, 0, V) {
if (alice_adj[i].size() == 1 && alice_adj[alice_adj[i][0]].size() == N+1) {
ax = i;
to = alice_adj[i][0];
break;
}
}
not_bit[to] = 1;
for (ll& i : alice_adj[to])
not_bit[i] = 1;
ll znode = -1, zgrade = 0;
range(i, 0, V) {
if (!not_bit[i]) {
ll cnt = 0;
for (ll& k : alice_adj[i]) {
if (!not_bit[k]) {
if (++cnt > 1)
break;
}
}
if (cnt == 1 && zgrade < alice_adj[i].size()) {
znode = i;
zgrade = alice_adj[i].size();
}
}
}
translate_nodes(znode, 0, -1);
vector<pair<ll, ll>> ans;
range(i, 0, V) {
if (not_bit[i] && i != to && i != ax) {
for (ll& k : alice_adj[i]) {
if (not_bit[k] && k != to && k != ax && cast[i] < cast[k]) {
ans.push_back({cast[i], cast[k]});
}
}
}
}
InitMap(N, ans.size());
for (pair<ll, ll>& it : ans)
MakeMap(it.first, it.second);
}
