#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;
for(int i = 0; i < m; i++){
edge.push_back(make_pair(a[i], b[i]));
}
for(int bit = 0; bit < 9; bit++){
edge.push_back(make_pair(n + bit, n + bit + 1));
}
for(int i = 0; i < n; i++){
for(int bit = 0; bit < 10; bit++){
if(i >> bit & 1){
edge.push_back(make_pair(n + bit, i));
}
}
}
for(int i = 0; i < n + 10; i++){
edge.push_back(make_pair(n + 10, i));
}
for(int bit = 0; bit < 10; bit++){
edge.push_back(make_pair(n + 11, n + bit));
}
InitG(n + 12, edge.size());
for(int i = 0; i < edge.size(); i++){
MakeG(i, edge[i].first, edge[i].second);
}
}
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
void Bob(int n, int m, int c[], int d[]){
vector<vector<int>>g(n);
for(int i = 0; i < m; i++){
g[c[i]].push_back(d[i]);
g[d[i]].push_back(c[i]);
}
int full_vertex, full_bit;
for(int i = 0; i < n; i++){
if(g[i].size() == n - 2){
full_vertex = i;
break;
}
}
for(int i = 0; i < n; i++){
if(i != full_vertex && find(g[i].begin(), g[i].end(), full_vertex) == g[i].end()){
full_bit = i;
break;
}
}
vector<vector<int>>bit_chain(n);
for(int& bit : g[full_bit]){
for(int& next_bit : g[bit]){
if(find(g[full_bit].begin(), g[full_bit].end(), next_bit) != g[full_bit].end()){
bit_chain[bit].push_back(next_bit);
}
}
}
int bit_zero = -1;
for(int& bit : g[full_bit]){
if(bit_chain[bit].size() == 1 && (bit_zero == -1 || g[bit].size() > g[bit_zero].size())){
bit_zero = bit;
}
}
vector<int>bit_id(10, -1);
bit_id[0] = bit_zero;
for(int bit = 0; bit < 9; bit++){
for(int& i : bit_chain[bit_id[bit]]){
if(bit == 0 || i != bit_id[bit - 1]){
bit_id[bit + 1] = i;
break;
}
}
}
vector<int>label(n, 0);
for(int bit = 0; bit < 10; bit++){
for(int& i : g[bit_id[bit]]){
label[i] |= 1 << bit;
}
}
for(int bit = 0; bit < 10; bit++){
label[bit_id[bit]] = -1;
}
label[full_vertex] = label[full_bit] = -1;
vector<pair<int, int>>edge;
for(int i = 0; i < m; i++){
if(label[c[i]] != -1 && label[d[i]] != -1){
edge.push_back(make_pair(label[c[i]], label[d[i]]));
}
}
InitMap(n - 12, edge.size());
for(auto& [u, v] : edge){
MakeMap(u, v);
}
}
