#include "Alicelib.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;
void Alice(int N, int M, int A[], int B[]) {
vector<array<int, 2>> edge;
for (int i = 0; i < M; ++i) {
edge.push_back({A[i], B[i]});
}
for (int u = 0; u < N; ++u) for (int i = 0; i < 10; ++i) if (u >> i & 1) {
edge.push_back({N + i, u});
}
for (int i = N; i < N + 10; ++i) for (int j = i + 1; j < N + 10; ++j) {
edge.push_back({j, i});
}
for (int i = 0; i < N + 10; ++i) {
edge.push_back({N + 10, i});
}
for (int i = N; i < N + 10; ++i) {
edge.push_back({N + 11, i});
}
InitG(N + 12, isz(edge));
for (int i = 0; i < isz(edge); ++i) {
MakeG(i, edge[i][0], edge[i][1]);
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;
void Bob(int N, int M, int A[], int B[]) {
vector<vector<int>> g(N);
vector a(N, vector(N, false));
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
g[u].emplace_back(v);
g[v].emplace_back(u);
a[u][v] = true;
}
pair<int, int> mx(-1, -1);
for (int i = 0; i < N; ++i) {
mx = max(mx, {isz(g[i]), i});
}
int N10 = mx.second;
assert(mx.first == N - 2);
int N11 = -1, cntN10 = 0;
for (int i = 0; i < N; ++i) if (i != N10) {
if (not a[N10][i]) {
N11 = i;
}
else {
++cntN10;
}
}
assert(cntN10 == mx.first);
assert(N11 != -1);
vector<int> cand = g[N11];
assert(isz(cand) == 10);
vector<int> cand_bit(10);
for (int i = 0; i < 10; ++i) for (int j = 0; j < 10; ++j) {
cand_bit[i] += a[cand[i]][cand[j]];
}
vector<int> vis(N);
vis[N10] = vis[N11] = true;
for (auto u : cand) vis[u] = true;
vector<int> real(N);
for (int i = 0; i < isz(cand); ++i) {
int u = cand[i], bit = cand_bit[i];
for (auto v : g[u]) if (not vis[v]) {
real[v] |= 1 << bit;
}
}
vector<array<int, 2>> res;
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
if (not vis[u] and not vis[v]) {
res.push_back({real[u], real[v]});
}
}
InitMap(N - 12, isz(res));
for (auto [u, v] : res) MakeMap(u, v);
}
