#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll = long long;
using vll = vector <ll>;
void Alice (int n, int m, int A[], int B[]) {
bool mat[n][n]{};
for (ll i = 0; i < m; i++) {
mat[A[i]][B[i]] = true;
mat[B[i]][A[i]] = true;
}
vector <bool> th;
for (ll i = 0; i < n; i++) {
for (ll j = i; j < n; j++) {
th.push_back(mat[i][j]);
}
}
vector <pair <ll, ll> > egs;
for (ll i = 0; i < th.size(); i++) {
egs.push_back({ i, i+1 });
if (th[i]) egs.push_back({ 0, i+1 });
}
for (auto [u, v] : egs) cerr << u << ' ' << v << '\n';
InitG(th.size()+1+6, egs.size()+9);
ll i=th.size()+2;
for (ll j = 0; j < 4; j++) egs.push_back({ i+j, i+j+1 });
for (ll j = i; j < i+5; j++) egs.push_back({ 0, j });
ll timer=0;
for (auto [u, v] : egs) MakeG(timer++, u, v);
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll = long long;
using vll = vector <ll>;
const ll MAXN = 1E6+16;
vll adj[MAXN];
void Bob (int n, int m, int A[], int B[]) {
cerr << "BOB\n";
for (ll i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
cerr << A[i] << ' ' << B[i] << '\n';
}
cerr << "\n";
ll sp = -15, best=0;
ll nd = -15;
for (ll i = 0; i < n; i++) {
if (adj[i].size() > best) best = adj[i].size(), sp = i;
if (adj[i].size() == 1) nd = i;
}
cerr << "special: " << sp << '\n';
cerr << "end: " << nd << '\n';
vector <bool> th;
function <void(ll, ll)> dfs = [&](ll u, ll par) {
bool has1 = false;
for (ll v : adj[u]) {
if (v == sp) { has1 = true; continue; }
if (v == par) continue;
dfs(v, u);
}
th.push_back(has1);
};
dfs(nd, nd);
ll nn = 0;
while (nn*(nn+1)/2 < th.size()) nn++;
bool mat[nn][nn]{};
ll c = 0;
vector <pair <ll, ll> > egs;
for (ll i = 0; i < nn; i++) {
for (ll j = i; j < nn; j++) {
if (th[c++] && !(i==0 && j==0)) egs.push_back({ i, j });
}
}
for (auto [u, v] : egs) cerr << u << ' ' << v << '\n';
InitMap(nn, egs.size());
for (auto [u, v] : egs) MakeMap(u, v);
}
