#include <bits/stdc++.h>
#include "Alicelib.h"
#pragma GCC target("sse4")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define all(a) a.begin(), a.end()
#define F first
#define S second
//#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc + 1)
const int maxn = 1e3, maxm = 1e4, lg = 10;
static int n, m, nn;
static int id[maxn];
static vector<pii> e;
static void prep(){
int j = 1;
for (int i = 0; i < maxn;i++){
while (__builtin_popcount(j) <= 1)
j++;
id[i] = j;
}
}
void Alice(int N, int M, int A[], int B[]) {
prep();
n = N;
m = M;
for (int i = 0; i < m; i++)
e.push_back({A[i], B[i]});
// d[nn - 1] = 1;
nn = n - 1 + lg + 2;
e.push_back({nn - 1, nn});
for (int b = 0; b < lg;b++)
e.push_back({n + b, nn});
for (int b = 1; b < lg; b++)
e.push_back({n + b - 1, n + b});
for (int b = 2; b < lg; b++)
e.push_back({n, n + b});
for (int i = 0; i < n;i++)
for (int b = 0; b < lg;b++)
if(id[i] & (1ll << b))
e.push_back({i, n + b});
InitG(nn + 1, e.size());
for (int i = 0; i < e.size(); i++)
MakeG(i, e[i].F, e[i].S);
}
#include <bits/stdc++.h>
#include "Boblib.h"
#pragma GCC target("sse4")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define all(a) a.begin(), a.end()
#define F first
#define S second
//#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc + 1)
const int maxn = 1e3, maxm = 1e4, lg = 10;
static int n, m, nn;
static int id[maxn], rev[maxn];
static vector<int> adj[maxn];
static vector<pii> e[2];
static bool bt[maxn];
static int w[maxn];
static void prep(){
int j = 1;
for (int i = 0; i < maxn;i++){
while (__builtin_popcount(j) <= 1)
j++;
rev[j] = i;
}
}
void Bob(int V, int U, int C[], int D[]) {
prep();
n = V;
m = U;
for (int i = 0; i < m; i++) {
int u = C[i], v = D[i];
adj[u].push_back(v);
adj[v].push_back(u);
e[0].push_back({u, v});
}
int d1 = 0;
for (int i = 0; i < n; i++)
if (adj[i].size() == 1)
d1 = i;
int db = adj[d1].back();
for(auto v : adj[db])
if(v ^ d1)
bt[v] = 1;
for (int i = 0; i < n; i++)
adj[i].clear();
for (auto [u, v] : e[0])
if (bt[u] && bt[v]) {
adj[u].push_back(v);
adj[v].push_back(u);
}
int b0 = 0;
for (int i = 0; i < n;i++)
if(adj[i].size() > adj[b0].size())
b0 = i;
w[b0] = 1;
int mxb = 0;
for (int i = 0; i < n;i++)
if(adj[i].size() == 2)
mxb = i;
w[mxb] = (1ll << (lg - 1));
for (int b = lg - 2; b;b--)
for(auto v : adj[mxb])
if(!w[v]){
mxb = v;
w[mxb] = (1ll << b);
break;
}
for (int i = 0; i < n;i++){
if(!w[i] && (i ^ d1) && (i ^ db)){
for (auto u : adj[i])
if(w[u])
id[i] += w[u];
id[i] = rev[id[i]];
}
}
w[d1] = w[db] = 1;
for(auto [u, v] : e[0])
if (!w[u] && !w[v])
e[1].push_back({id[u], id[v]});
InitMap(n - lg - 2, e[1].size());
for (int i = 0; i < e[1].size(); i++)
MakeMap(e[1][i].F, e[1][i].S);
}
