#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice(int n, int m, int a[], int b[]) {
vector<pair<int, int>> e;
for (int i = 0; i < m; i++) {
e.emplace_back(a[i], b[i]);
}
const int L = 10;
for (int i = 0; i < n; i++) {
for (int j = 0; j < L; j++) {
if ((i + 1) >> j & 1) {
e.emplace_back(i, n + j);
}
}
}
int to_all = n + L;
int to_bits = to_all + 1;
for (int i = 0; i < to_all; i++) {
e.emplace_back(i, to_all);
}
for (int i = n; i < n + L; i++) {
e.emplace_back(to_bits, i);
}
auto Idx = [&](int x) {
return n + x;
};
e.emplace_back(Idx(0), Idx(1));
e.emplace_back(Idx(1), Idx(2));
e.emplace_back(Idx(0), Idx(3));
e.emplace_back(Idx(3), Idx(4));
e.emplace_back(Idx(4), Idx(5));
e.emplace_back(Idx(0), Idx(6));
e.emplace_back(Idx(6), Idx(7));
e.emplace_back(Idx(7), Idx(8));
e.emplace_back(Idx(8), Idx(9));
InitG(to_bits + 1, e.size());
for (int i = 0; i < (int) e.size(); i++) {
MakeG(i, e[i].first, e[i].second);
}
}
/*
4 3
0 1
0 2
0 3
5 7
0 1
0 2
1 3
1 4
3 4
2 3
2 4
*/
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob(int v, int u, int c[], int d[]) {
const int L = 10;
int n = v - L - 2;
vector<vector<int>> g(v);
for (int i = 0; i < u; i++) {
g[c[i]].push_back(d[i]);
g[d[i]].push_back(c[i]);
}
vector<int> deg(v);
for (int i = 0; i < v; i++) {
deg[i] = (int) g[i].size();
}
int to_all = (int) (max_element(deg.begin(), deg.end()) - deg.begin());
int to_bits = -1;
for (int i = 0; i < v; i++) {
if (i == to_all) {
continue;
}
bool ok = true;
for (int j : g[i]) {
if (j == to_all) {
ok = false;
}
}
if (ok) {
assert(to_bits == -1);
to_bits = i;
}
}
vector<int> bits;
for (int i : g[to_bits]) {
bits.push_back(i);
}
vector<int> nodes;
vector<bool> is_node(v);
for (int i = 0; i < v; i++) {
if (i == to_all) {
continue;
}
if (i == to_bits) {
continue;
}
bool is_bit = false;
for (int j : bits) {
if (i == j) {
is_bit = true;
}
}
if (is_bit) {
continue;
}
nodes.push_back(i);
is_node[i] = true;
}
vector<int> val(v, -1);
{
vector<bool> is_bit(v);
for (int i : bits) {
is_bit[i] = true;
}
vector<vector<int>> r(v);
for (int i = 0; i < u; i++) {
if (is_bit[c[i]] && is_bit[d[i]]) {
r[c[i]].push_back(d[i]);
r[d[i]].push_back(c[i]);
}
}
int cen = -1;
for (int i : bits) {
if ((int) r[i].size() == 3) {
cen = i;
}
}
val[cen] = 0;
vector<int> ch;
function<void(int, int)> Dfs = [&](int x, int pr) {
if (x != cen) {
ch.push_back(x);
}
for (int y : r[x]) {
if (y == pr) {
continue;
}
Dfs(y, x);
if (x == cen) {
if ((int) ch.size() == 2) {
val[ch[0]] = 1;
val[ch[1]] = 2;
} else if ((int) ch.size() == 3) {
val[ch[0]] = 3;
val[ch[1]] = 4;
val[ch[2]] = 5;
} else if ((int) ch.size() == 4) {
val[ch[0]] = 6;
val[ch[1]] = 7;
val[ch[2]] = 8;
val[ch[3]] = 9;
}
ch.clear();
}
}
};
Dfs(cen, cen);
}
vector<int> idx(v);
for (int i : nodes) {
for (int j : g[i]) {
if (val[j] != -1) {
idx[i] += (1 << val[j]);
}
}
}
vector<pair<int, int>> ans;
for (int i = 0; i < u; i++) {
if (is_node[c[i]] && is_node[d[i]]) {
ans.emplace_back(idx[c[i]], idx[d[i]]);
}
}
InitMap(n, (int) ans.size());
for (int i = 0; i < (int) ans.size(); i++) {
MakeMap(ans[i].first - 1, ans[i].second - 1);
}
}
