#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
static bool test(int mask, int bit) {
return mask & (1 << bit);
}
void Alice(int n, int m, int a[], int b[]) {
vector<pair<int, int>> e;
rep(i, 0, m) {
e.pb({a[i], b[i]});
}
rep(i, 0, n + 12) {
if (i != n && i != n + 1) {
e.pb({n, i});
}
}
rep(i, n + 2, n + 12) {
e.pb({n + 1, i});
}
rep(i, n + 2, n + 11) {
e.pb({i, i + 1});
}
rep(i, 0, n) {
rep(bit, 0, 10) {
if (test(i, bit)) {
e.pb({i, n + 2 + bit});
}
}
}
InitG(n + 12, sz(e));
rep(i, 0, sz(e)) {
auto it = e[i];
MakeG(i, it.first, it.second);
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
static bool test(int mask, int bit) {
return mask & (1 << bit);
}
void Bob(int V, int U, int C[], int D[]) {
int n = V - 12;
vector<vector<int>> g(V);
rep(i, 0, U) {
g[C[i]].pb(D[i]);
g[D[i]].pb(C[i]);
}
rep(i, 0, V) {
sort(all(g[i]));
}
int C1 = -1;
rep(i, 0, V) {
if (sz(g[i]) == n + 10) {
assert(C1 == -1);
C1 = i;
}
}
assert(C1 != -1);
int C2 = -1;
rep(i, 0, V) {
if (i == C1) {
continue;
}
if (!binary_search(all(g[C1]), i)) {
assert(C2 == -1);
C2 = i;
}
}
assert(C2 != -1);
vector<int> cool;
for (int i : g[C2]) {
cool.pb(i);
}
sort(all(cool));
assert(sz(cool) == 10);
int v = cool.back();
int prv = -1;
while (1) {
int to = -1;
for (int u : g[v]) {
if (!binary_search(all(cool), u) || u == prv) {
continue;
}
to = u;
}
if (to == -1) {
break;
}
prv = v;
v = to;
}
vector<int> seq;
seq.pb(v);
prv = -1;
while (1) {
int to = -1;
for (int u : g[v]) {
if (!binary_search(all(cool), u) || u == prv) {
continue;
}
to = u;
}
if (to == -1) {
break;
}
prv = v;
v = to;
seq.pb(v);
}
assert(sz(seq) == 10);
vector<bool> our(V, 1);
our[C1] = 0;
our[C2] = 0;
for (int v : seq) {
our[v] = 0;
}
int cnt_our = 0;
for (bool i : our) {
cnt_our += i;
}
assert(cnt_our == n);
rep(iter, 0, 2) {
vector<int> wow(V, -1);
rep(i, 0, 10) {
wow[seq[i]] = i;
}
bool ok = 1;
rep(v, 0, V) {
if (!our[v]) {
continue;
}
int id = 0;
for (int u : g[v]) {
if (wow[u] != -1) {
id |= (1 << wow[u]);
}
}
if (id >= n) {
ok = 0;
break;
}
}
if (iter == 1) {
assert(ok);
}
if (ok) {
break;
}
reverse(all(seq));
}
vector<int> wow(V, -1);
rep(i, 0, 10) {
wow[seq[i]] = i;
}
vector<int> id(V, -1);
rep(v, 0, V) {
if (!our[v]) {
continue;
}
id[v] = 0;
for (int u : g[v]) {
if (wow[u] != -1) {
id[v] |= (1 << wow[u]);
}
}
}
vector<pair<int, int>> adj;
rep(i, 0, V) {
for (int j : g[i]) {
int u = id[i];
int v = id[j];
if (u == -1 || v == -1) {
continue;
}
if (u < v) {
adj.pb({u, v});
}
}
}
InitMap(n, sz(adj));
for (auto &it : adj) {
MakeMap(it.first, it.second);
}
}
