// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair
using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;
const int EX = 12;
const int B = 10;
void Alice(int N, int M, int C[], int D[]){
int EXT = N + EX - 1;
int PATH = N + EX - 2;
vpi E;
for(int i = 0; i < M; i++) {
E.pb(mp(C[i], D[i]));
}
int cur = 1;
for(int i = 0; i < N; i++) {
while(__builtin_popcount(cur) == 1) cur++;
for(int b = 0; b < B; b++) if ((cur >> b) & 1) {
E.pb(mp(N + b, i));
}
++cur;
}
// cout << "MX: " << cur << endl;
// cout << "PATH: " << PATH << endl;
for(int i = 0; i < B; i++) {
if (i) E.pb(mp(N + i - 1, N + i));
else E.pb(mp(PATH, N + i));
}
for(int i = 0; i < B; i++) {
E.pb(mp(N + i, EXT));
}
InitG(N + EX, sz(E));
for(int i = 0; i < sz(E); i++) {
MakeG(i, E[i].f, E[i].s);
}
}
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair
using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;
const int EX = 12;
const int B = 10;
void Bob(int N, int M, int C[], int D[]){
int cur = 1; map<int, int> conv; vi F(B);
for(int i = 0; i < (N - EX); i++) {
while(__builtin_popcount(cur) == 1) cur++;
for(int b = 0; b < B; b++) if ((cur >> b) & 1) F[b]++;
conv[cur++] = i;
}
V<vi> adj(N);
for(int i = 0; i < M; i++) {
adj[C[i]].pb(D[i]);
adj[D[i]].pb(C[i]);
}
// cout << B + N - EX << endl;
vi BITS(B); vi X(N);
int PATH = -1; for(int i = 0; i < N; i++) if (sz(adj[i]) == 1) {
PATH = i;
}
// cout << PATH << endl;
int times = 0;
for(int i = 0; i < N; i++) if (sz(adj[i]) == B) {
int EXT = i;
set<int> left; for(auto &x : adj[EXT]) left.insert(x);
vi path; int u = PATH;
for(int x = 0; x < B; x++) {
bool found = 0;
for(auto& v : adj[u]) {
if (left.count(v)) {
left.erase(v);
u = v;
found = 1;
break;
}
}
if (found) {
path.pb(u);
} else {
path = {};
break;
}
}
if (sz(path) == 0 || sz(left)) continue;
assert(sz(path) == B);
set<int> S(begin(path), end(path));
S.insert(PATH); S.insert(EXT);
// set of special nodes
vi FP;
for(auto& x : path) {
int amt = 0;
for(auto& y : adj[x]) if (!S.count(y)) amt++;
FP.pb(amt);
}
if (F != FP) continue;
X[PATH] = X[EXT] = -1;
// cout << "PATH: ";
for(int x = 0; x < B; x++) {
// cout << path[x] << " ";
X[path[x]] = -1;
BITS[x] = path[x];
}
// cout << endl;
++times;
}
// cout << times << endl;
assert(times == 1);
for(int i = 0; i < B; i++) {
for(auto& x : adj[BITS[i]]) {
if (X[x] == -1) continue;
X[x] ^= (1 << i);
}
}
vpi E;
for(int u = 0; u < N; u++) {
int U = X[u];
if (U == -1) continue;
for(auto& v : adj[u]) {
int V = X[v];
if (V == -1) continue;
if (U < V) {
// cout << U << " " << V << endl;
// cout << conv[U] << " " << conv[V] << endl;
E.pb(mp(conv[U], conv[V]));
}
}
}
// cout << sz(E) << endl;
InitMap(N - EX, sz(E));
for(int i = 0; i < sz(E); i++) MakeMap(E[i].f, E[i].s);
}
