// In the name of Allah
#include <bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
const int maxlg = 10, maxs = 1000;
const int maxn = (1 << maxlg) + 4;
static int valx[maxn], ind[maxn];
static int n, m;
static vector<pii> E, Ex;
static void upd_valx() {
int j = 0;
for (int i = 0; i < maxs; i++) {
while (__builtin_popcount(j) <= 1) j++;
valx[i] = j; ind[j] = i; j++;
}
}
void Alice(int N, int M, int A[], int B[]) {
upd_valx(); n = N; m = M;
for (int i = 0; i < m; i++) E.pb(Mp(A[i], B[i]));
for (auto f : E) Ex.pb(f);
int vx = n + maxlg;
Ex.pb(Mp(vx, vx + 1));
for (int j = 0; j < maxlg; j++) Ex.pb(Mp(n + j, vx));
for (int j = 1; j < maxlg; j++) Ex.pb(Mp(n + j - 1, n + j));
for (int i = 0; i < n; i++) {
for (int j = 0; j < maxlg; j++) {
if (valx[i] & (1 << j)) {
Ex.pb(Mp(i, n + j));
}
}
}
InitG(n + maxlg + 2, len(Ex));
for (int i = 0; i < len(Ex); i++) MakeG(i, Ex[i].F, Ex[i].S);
}
// In the name of Allah
#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
const int maxlg = 10, maxs = 1000;
const int maxn = (1 << maxlg) + 4;
static int valx[maxn], ind[maxn];
static int n, m;
static vector<int> adj[maxn], ls;
static int M[maxn], D[maxn];
static int mark[maxn], Ax[maxn];
static vector<pii> E, Ex;
static void upd_valx() {
int j = 0;
for (int i = 0; i < maxs; i++) {
while (__builtin_popcount(j) <= 1) j++;
valx[i] = j; ind[j] = i; j++;
}
}
void dfs(int v) {
mark[v] = 1; ls.pb(v);
for (int u : adj[v]) {
if (!mark[u]) {
dfs(u);
}
}
}
void Bob(int V, int U, int C[], int D[]) {
upd_valx(); n = V; m = U;
for (int i = 0; i < m; i++) {
int u = C[i], v = D[i];
adj[u].pb(v); adj[v].pb(u);
Ex.pb(Mp(u, v));
}
int vx = -1;
for (int i = 0; i < n; i++) {
D[i] = len(adj[i]);
if (len(adj[i]) == 1) vx = i;
}
int ux = adj[vx].back();
for (int u : adj[ux]) {
if (u == vx) continue;
M[u] = 1;
}
for (int i = 0; i < n; i++) adj[i].clear();
for (auto f : Ex) {
int u = f.F, v = f.S;
if (M[u] && M[v]) {
adj[u].pb(v); adj[v].pb(u);
}
}
int u1 = -1, u2 = -1;
for (int i = 0; i < n; i++) {
if (len(adj[i]) == 1) {
if (u1 == -1) u1 = i;
else u2 = i;
}
}
if (D[u1] > D[u2]) dfs(u1);
else dfs(u2);
for (int i = 0; i < len(ls); i++) Ax[ls[i]] = (1 << i);
for (int i = 0; i < n; i++) adj[i].clear();
for (auto f : Ex) {
int u = f.F, v = f.S;
adj[u].pb(v); adj[v].pb(u);
}
for (int i = 0; i < n; i++) {
if (i == vx || i == ux || M[i]) continue;
for (int j : adj[i]) {
if (!M[j]) continue;
Ax[i] |= Ax[j];
}
}
for (auto f : Ex) {
int i = f.F, j = f.S;
if (i == vx || i == ux || M[i]) continue;
if (j == vx || j == ux || M[j]) continue;
E.pb(Mp(ind[Ax[i]], ind[Ax[j]]));
}
InitMap(n - maxlg - 2, len(E));
for (int i = 0; i < len(E); i++) MakeMap(E[i].F, E[i].S);
}
