#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
typedef pair<int,int> pii;
void Alice(int n, int m, int a[], int b[] ){
vector<pii> edgelist;
for(int i=n; i<n+9; i++){
edgelist.pb({i,i+1});
}
for(int i=n; i<n+10; i++){
edgelist.pb({i,n+10});
}
edgelist.pb({n+10,n+11});
int deg[n] = {};
for(int i=0; i<m; i++){
edgelist.pb({a[i],b[i]});
deg[a[i]]++, deg[b[i]]++;
}
vector<int>spares;
for(int i=0; i<n; i++){
if(deg[i] == 0){
spares.pb(i);
continue;
}
int id = i+1;
for(int j=0; j<10; j++){
if(id&(1<<j)) edgelist.pb({i,n+j});
}
}
if(spares.size() > 1){
int u = spares[0], v = spares[1];
edgelist.pb({u,n});
edgelist.pb({v,n});
}
int nodes = n+12, edges = edgelist.size();
InitG(nodes,edges);
for(int i=0; i<edges; i++){
auto[u,v] = edgelist[i];
MakeG(i, u, v);
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
typedef pair<int,int> pii;
void Bob(int v, int u, int c[], int d[]){
int deg[v] = {};
for(int i=0; i<u; i++){
deg[c[i]]++;
deg[d[i]]++;
}
int num[v] = {};
for(int i=0; i<u; i++){
if(deg[c[i]] == 1) num[d[i]]++;
if(deg[d[i]] == 1) num[c[i]]++;
}
int sp, sp1 = -1;
for(int i=0; i<v; i++){
if(num[i] == 1){
sp = i;
} else if(num[i] == 2){
sp1 = i;
}
}
bool isline[v] = {};
for(int i=0; i<u; i++){
if(deg[c[i]] == 1 or deg[d[i]] == 1) continue;
if(c[i] == sp) isline[d[i]] = 1;
if(d[i] == sp) isline[c[i]] = 1;
}
vector<int>adj[v];
for(int i=0; i<u; i++){
if(isline[c[i]] and isline[d[i]]){
adj[c[i]].pb(d[i]);
adj[d[i]].pb(c[i]);
}
}
vector<int>ends;
for(int i=0; i<v; i++){
if(isline[i] and adj[i].size() == 1) ends.pb(i);
}
if(sp1 != -1){
if(sp1 == ends[1]) swap(ends[0], ends[1]);
assert(sp1 == ends[0]);
} else {
int deg1[v] = {};
for(int i=0; i<u; i++){
if(c[i] == sp or d[i] == sp) continue;
if(isline[c[i]] and isline[d[i]]) continue;
deg1[c[i]]++;
deg1[d[i]]++;
}
if(deg1[ends[0]] < deg1[ends[1]]) swap(ends[0], ends[1]);
}
int ptr = 0, mp[v] = {};
mp[ends[0]] = ptr++;
int prev = -1, cur = ends[0];
while(cur != ends[1]){
int nxt = -1;
for(auto i: adj[cur]){
if(i != prev) nxt = i;
}
prev = cur;
cur = nxt;
mp[cur] = ptr++;
}
int extra = 20;
if(sp1 != -1) extra += 2;
int mp1[v] = {};
for(int i=0; i<u; i++){
if(c[i] == sp or d[i] == sp) continue;
if(c[i] == sp1 or d[i] == sp1) continue;
if(isline[c[i]] and isline[d[i]]) continue;
if(isline[c[i]]){
mp1[d[i]] += (1<<(mp[c[i]]));
extra++;
}
if(isline[d[i]]){
mp1[c[i]] += (1<<(mp[d[i]]));
extra++;
}
}
InitMap(v-12, u-extra);
for(int i=0; i<u; i++){
if(c[i] == sp or d[i] == sp) continue;
if(c[i] == sp1 or d[i] == sp1) continue;
if(isline[c[i]] or isline[d[i]]) continue;
MakeMap(mp1[c[i]]-1, mp1[d[i]]-1);
}
}
