#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1020;
static vector<int> grafo[MAXN];
void Alice( int N, int M, int A[], int B[] ){
if(N == 1){
InitG(1,0);
return;
}
// Padrao
for(int i = 0;i<M;i++){
int x = A[i];
int y = B[i];
x++;y++; // 1-indexado, se nao falha
grafo[x].push_back(y);
grafo[y].push_back(x);
}
int qtd_n = N + 13;
int qtd_m = 0;
// Bits
for(int i = 0;i<10;i++){
int pot = (1 << i);
int idx = N + i + 1;
for(int j = 1;j<=N;j++){
if(pot & j){
grafo[j].push_back(idx);
grafo[idx].push_back(j);
}
}
}
// Ligacao bits
for(int i = 0;i+1<10;i++){
int idx1 = N + i + 1;
int idx2 = N + i + 2;
grafo[idx1].push_back(idx2);
grafo[idx2].push_back(idx1);
}
// folha-1
grafo[N+10].push_back(N+11);
grafo[N+11].push_back(N+10);
//folha-2
grafo[N+12].push_back(N+13);
grafo[N+13].push_back(N+12);
// grau alto
for(int i = 1;i<=N;i++){
grafo[i].push_back(N+13);
grafo[N+13].push_back(i);
}
for(int i = 1;i<=N+13;i++) qtd_m += grafo[i].size();
qtd_m /=2;
InitG(qtd_n,qtd_m);
int ptr = 0;
for(int i = 1;i<=N+13;i++){
for(int j : grafo[i]){
if(i >= j) continue;
//printf("Ptr %d Alice I %d J %d\n",ptr,i,j);
MakeG(ptr,i-1,j-1);
ptr++;
}
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1020;
static vector<int> grafo[MAXN];
static int ehValido[MAXN],somatorio[MAXN];
void Bob( int V, int U, int C[], int D[] ){
//printf("##############################\n");
memset(ehValido,0,sizeof(ehValido));
memset(somatorio,0,sizeof(somatorio));
// caso especial
if(V == 1){
InitMap(1,0);
return;
}
int N = V - 13,M = 0,especial = 0,bit_davez = 0;
// recuperando o grafo
for(int i = 0;i<U;i++){
int x = C[i];
int y = D[i];
x++;y++;
grafo[x].push_back(y);
grafo[y].push_back(x);
//printf("G %d %d\n",x,y);
}
vector<int> candidatos;
for(int i = 1;i<=N+13;i++){
if(grafo[i].size() == 1) candidatos.push_back(i);
}
// Descobrindo o primeiro bit
int primeiro_cand = candidatos[0];
int outro_cara = grafo[primeiro_cand][0];
//printf("C1 %d C2 %d O %d\n",candidatos[0],candidatos[1],outro_cara);
if(grafo[outro_cara].size() == N + 1){
// printf("Caso 1\n");
bit_davez = grafo[candidatos[1]][0];
especial = outro_cara;
}
else{
// printf("Caso 2\n");
bit_davez = outro_cara;
especial = grafo[candidatos[1]][0];
}
for(int i : grafo[especial]){
ehValido[i] = 1;
}
ehValido[candidatos[0]] = 0;
ehValido[candidatos[1]] = 0;
for(int vez = 9;vez>=0;vez--){
int nxt = 0,pot = (1 << vez);
//printf("Meu %d\n",bit_davez);
for(int i : grafo[bit_davez]){
if(grafo[i].size() <= 1){
continue;
}
if(!ehValido[i]){
nxt = i;
}
else{
//printf("Add %d AH %d\n",pot,i);
somatorio[i] += pot;
}
}
grafo[bit_davez].clear();
bit_davez = nxt;
}
for(int i = 1;i<=N+13;i++){
for(int j : grafo[i]){
if(!ehValido[i] || !ehValido[j]) continue;
if(i <= j){
M++;
}
}
}
InitMap(N,M);
for(int i = 1;i<=N+13;i++){
for(int j : grafo[i]){
if(!ehValido[i] || !ehValido[j]) continue;
if(i <= j){
//printf("Bob I %d J %d (%d %d)\n",i,j,somatorio[i]-1,somatorio[j]-1);
MakeMap(somatorio[i] - 1,somatorio[j] - 1);
}
}
}
}
