#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
vector<pair<int ,int>> edgs;
for(int i = 0 ; i < M ; i++)
{
edgs.push_back({A[i] , B[i]});
}
edgs.push_back({N + 1 , N});
for(int i = 0 ; i < N ; i++)
{
edgs.push_back({N , i});
}
for(int i = 0 ; i < N ; i++)
{
for(int j = 0 ; j <= 9 ; j++)
{
if((1<<j) & i)
{
edgs.push_back({j + N + 2 , i});
}
}
}
for(int j = 0 ; j <= 8 ; j++)
{
edgs.push_back({j + N + 2 , j + N + 3});
}
InitG(N + 12 , (int)edgs.size());
for(int i = 0 ; i < (int)edgs.size() ; i++)
{
MakeG(i , edgs[i].first , edgs[i].second);
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
int nb = -1;
void dfs(int x , vector<bool> &vis , vector<bool> &original , vector<int> &label , vector<vector<int>> &adj)
{
if(vis[x])
return;
vis[x] = 1;
nb++;
for(auto u : adj[x])
{
if(original[u])
{
label[u]|=(1<<nb);
}
}
for(auto u : adj[x])
{
dfs(u , vis , original , label , adj);
}
}
void Bob( int V, int U, int C[], int D[] ){
nb = -1;
int N = V - 12;
vector<vector<int>> adj(V);
vector<int> label(V);
vector<bool> original(V);
vector<bool> vis(V);
for(int i = 0 ; i < U ; i++)
{
adj[C[i]].push_back(D[i]);
adj[D[i]].push_back(C[i]);
}
int Node = 0 , extra = 0;
for(int i = 0 ; i < V ; i++)
{
if((int)adj[i].size() == N + 1)
{
int b = 0;
for(auto j : adj[i])
{
b+=((int)adj[j].size() == 1);
}
if(b == 1)
{
Node = i;
}
}
}
vis[Node] = 1;
for(auto i : adj[Node])
{
vis[i] = 1;
if((int)adj[i].size() > 1)
{
original[i] = 1;
}
else
extra = i;
}
int strt = -1;
int nbs = -1;
for(int i = 0 ; i < V ; i++)
{
if(i != Node && i != extra && !original[i])
{
int nb = 0;
for(auto j : adj[i])
{
nb+=original[j];
}
if(nb > nbs && (int)adj[i].size() == nb + 1)
{
strt = i;
nbs = nb;
}
}
}
dfs(strt , vis , original , label , adj);
vector<pair<int ,int>> edgs;
for(int i = 0 ; i < U ; i++)
{
if(original[C[i]] && original[D[i]])
{
edgs.push_back({label[C[i]] , label[D[i]]});
}
}
InitMap(N , (int)edgs.size());
for(int i = 0 ; i < (int)edgs.size() ; i++)
{
MakeMap(edgs[i].first , edgs[i].second);
}
}
