#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
vector<pair<int,int>> edge;
int lst[1100];
int pow[11];
vector<int> de;
int it = 0;
for(int i = 0; i < 10; i++){
pow[i] = N + 50 + i;
de.push_back(pow[i]);
}
for(int i = 0; i < N; i++){
int cont = 0;
while(cont < 2){
it++;
int c = it;
cont = 0;
while(c != 0){
cont++;
c -= (c&(-c));
}
}
lst[i] = it;
de.push_back(it);
for(int i = 0; i < 10; i++){
if( (it&(1<<i)) > 0 ){
edge.push_back({it,pow[i]});
}
}
}
for(int i = 0; i < M; i++){
edge.push_back({lst[A[i]],lst[B[i]]});
}
for(int i = 0; i < 9; i++){
edge.push_back({pow[i],pow[i + 1]});
}
int b = N + 70;
de.push_back(b);
for(int i = 0; i < 10; i++) edge.push_back({pow[i],b});
de.push_back(N + 100);
edge.push_back({N + 100, b});
InitG(de.size(), edge.size());
sort(de.begin(),de.end());
int i = 0;
for(pair<int,int> ii : edge){
int a = lower_bound(de.begin(),de.end(),ii.first) - de.begin();
int b = lower_bound(de.begin(),de.end(),ii.second) - de.begin();
MakeG(i,a,b);
i++;
}
return;
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
int d[V];
vector<int> adjlst[V + 2];
bool isten[V + 2];
int itentity[V + 2];
for(int i = 0; i < V; i++) d[i] = 0;
for(int i = 0; i < V; i++) isten[i] = false;
for(int i = 0; i < U; i++){
d[C[i]]++;
d[D[i]]++;
adjlst[C[i]].push_back(D[i]);
adjlst[D[i]].push_back(C[i]);
}
int mark = 0;
int mark1 = 0;
for(int i = 0; i < V; i++){
if(d[i] == 1){
mark = i;
}
}
mark1 = adjlst[mark][0];
vector<int> ten;
vector<int> endp;
for(int i : adjlst[mark1]){
if(i == mark) continue;
isten[i] = true;
ten.push_back(i);
}
for(int i : ten){
int cont = 0;
for(int j : adjlst[i]){
if(isten[j]) cont++;
}
if(cont == 1) endp.push_back(i);
}
ten.clear();
if(d[endp[0]] < d[endp[1]]) swap(endp[0],endp[1]);
endp.pop_back();
int i = endp[0];
int p = -1;
while(true){
ten.push_back(i);
bool die = true;
for(int j : adjlst[i]){
if(!isten[j] || j == p) continue;
p = i;
i = j;
die = false;
break;
}
if(die) break;
}
assert(ten.size() == 10);
for(int i = 0; i < V; i++) itentity[i] = -1;
itentity[mark] = -2;
itentity[mark1] = -2;
for(int i = 0; i < 10; i++){
itentity[ten[i]] = V + 100 + i;
}
vector<int> de;
for(int i = 0; i < V; i++){
if(itentity[i] == -1){
itentity[i] = 0;
for(int j : adjlst[i]){
if(itentity[j] >= V + 100){
itentity[i] += (1<<(itentity[j]-V-100)) ;
}
}
de.push_back(itentity[i]);
}
}
sort(de.begin(),de.end());
vector<pair<int,int>> edge;
for(int i = 0; i < U; i++){
if(itentity[C[i]] < 0 || itentity[D[i]] < 0) continue;
if(itentity[C[i]] >= V + 100 || itentity[D[i]] >= V + 100) continue;
int a = lower_bound(de.begin(),de.end(),itentity[C[i]]) - de.begin();
int b = lower_bound(de.begin(),de.end(),itentity[D[i]]) - de.begin();
edge.push_back({a,b});
}
InitMap( V - 12, edge.size());
for(pair<int,int> ii : edge) MakeMap(ii.first,ii.second);
}
