#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <queue>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
vector<pair<int, int>> edges;
for(int i=M; i--;)
edges.emplace_back(A[i], B[i]);
for(int i=N; i--;){
for(int j=10; j--;){
if(i>>j&1)
edges.emplace_back(N+j, i);
}
edges.emplace_back(N+10, i);
}
for(int i=10; i--;){
edges.emplace_back(N+10, N+i);
edges.emplace_back(N+11, N+i);
if(i)
edges.emplace_back(N+i, N+i-1);
}
edges.emplace_back(N+1, N+3);
InitG(N+12, edges.size());
while(not edges.empty()){
MakeG(edges.size()-1, edges.back().first, edges.back().second),
edges.pop_back();
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
vector<vector<int>> adjLis(V);
for(int i=U; i--;)
adjLis[C[i]].push_back(D[i]),
adjLis[D[i]].push_back(C[i]);
//finding allcon (N+10)
int allcon=0;
for(int i=V; i--;){
if(adjLis[allcon].size()<adjLis[i].size())
allcon=i;
}
//finding tencon (N+11)
int tencon=0;
adjLis[allcon].push_back(allcon);
sort(adjLis[allcon].begin(), adjLis[allcon].end());
for(auto i: adjLis[allcon]){
if(i!=tencon)
break;
tencon++;
}
//finding ten (N+[0..9])
auto ten=adjLis[tencon];
sort(ten.begin(), ten.end());
vector<vector<int>> adjten(10);
for(int i=0; i<10; i++){
for(int j: adjLis[ten[i]]){
if(binary_search(ten.begin(), ten.end(), j))
adjten[i].push_back(lower_bound(ten.begin(), ten.end(), j)-ten.begin());
}
}
vector<int> tenord;
//0
for(int i=0; i<10; i++){
if(adjten[i].size()==1 and adjten[adjten[i][0]].size()==3){
tenord.push_back(i);
break;
}
}
//1
tenord.push_back(adjten[tenord[0]][0]);
//2
for(int i=3; i--;){
if(adjten[adjten[tenord[1]][i]].size()==2)
tenord.push_back(adjten[tenord[1]][i]);
}
//3
for(int i=3; i--;){
if(adjten[adjten[tenord[1]][i]].size()==3)
tenord.push_back(adjten[tenord[1]][i]);
}
//4
for(int i=3; i--;){
if(adjten[adjten[tenord[3]][i]].size()==2 and adjten[tenord[3]][i]!=tenord[2])
tenord.push_back(adjten[tenord[3]][i]);
}
//5..9
for(int i=5; i<10; i++)
tenord.push_back(adjten[tenord[i-1]][adjten[tenord[i-1]][0]==tenord[i-2]]);
for(int i=0; i<10; i++)
tenord[i]=ten[tenord[i]];
//finding all (0..N-1)
vector<int> trueIndex(V, -1);
int m=U-(10+V-2+10);
for(int i=0; i<V; i++){
if(i==allcon or i==tencon or count(tenord.begin(), tenord.end(), i))
continue;
sort(adjLis[i].begin(), adjLis[i].end());
trueIndex[i]=0;
for(int j=10; j--;){
if(count(adjLis[i].begin(), adjLis[i].end(), tenord[j]))
trueIndex[i]+=1<<j, m--;
}
}
InitMap(V-12, m);
for(int i=0; i<V; i++){
if(trueIndex[i]==-1)
continue;
for(int j: adjLis[i]){
if(trueIndex[j]<trueIndex[i])
continue;
MakeMap(trueIndex[i], trueIndex[j]);
}
}
}
