#include "Alicelib.h"
#include <bits/stdc++.h>
const int MAXN = 1010;
const int MAXM = 1000010;
using namespace std;
typedef pair<int,int> pii;
vector<pii> ans;
void Alice(int N, int M, int A[], int B[])
{
if( N == 1 ) return void( InitG( 1 , 0 ) );
for(int i = 0 ; i < M ; i++)
ans.push_back( { A[i] , B[i] } );//Grafo original
for(int i = 1 ; i <= N ; i++)
for(int j = 0 ; j < 10 ; j++)
if( i & (1 << j) ) ans.push_back( { i - 1 , j + N } );//Representação binária
for(int i = N ; i < N + 9 ; i++)
ans.push_back( { i , i + 1 } );//Linha de bits
for(int i = 0 ; i < N ; i++)
ans.push_back( { i , N + 10 } );//A
ans.push_back( { N + 10 , N + 11 } );//Folha
InitG( N + 12 , (int)ans.size() );
for(int i = 0 ; i < (int)ans.size() ; i++)
MakeG( i , ans[i].first , ans[i].second );
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 2000;
int perm[MAXN];
int value[MAXN];
bool mark[MAXN];
bool isOriginal[MAXN];
vector<int> bits;
vector<int> adj[MAXN];
bool cmp(int i, int j) { return adj[i].size() > adj[j].size(); }
void DFS(int cur)
{
mark[cur] = true;
for(int i = 0 ; i < (int)adj[cur].size() ; i++)
if( !mark[ adj[cur][i] ] ) DFS( adj[cur][i] );
bits.push_back( cur );
}
void Bob(int V, int U, int C[], int D[])
{
if( V == 1 ) return void( InitMap( 1 , 0 ) );
for(int i = 0 ; i < U ; i++)
{
adj[ C[i] ].push_back( D[i] );
adj[ D[i] ].push_back( C[i] );
}
int leaf = -1;
for(int i = 0 ; i < V ; i++)
{
if( (int)adj[i].size() > 1 ) continue;
if( leaf == -1 )
{
leaf = i;
continue;
}
int vizI = adj[i].back();
int vizLeaf = adj[leaf].back();
if( (int)adj[vizLeaf].size() < (int)adj[vizI].size() )
leaf = i;
}
int A = adj[leaf].back();
mark[A] = true;
for(int i = 0 ; i < (int)adj[A].size() ; i++)
{
mark[ adj[A][i] ] = true;
isOriginal[ adj[A][i] ] = ( adj[A][i] != leaf );
}
int last = -1;
for(int i = 0 ; i < V ; i++)
{
if( mark[i] ) continue;
if( last == -1 ) last = i;
else if( adj[i].size() < adj[last].size() ) last = i;
}
DFS( last );
for(int i = 0 ; i < (int)bits.size() ; i++)
mark[ bits[i] ] = false;
for(int i = 0 ; i < (int)bits.size() ; i++)
value[ bits[i] ] = (1 << i);
for(int i = 0 ; i < V ; i++)
{
if( !mark[i] || i == A || i == leaf ) continue;
for(int j = 0 ; j < (int)adj[i].size() ; j++)
if( !mark[ adj[i][j] ] ) perm[i] += value[ adj[i][j] ];
perm[i]--;
}
vector<pii> edges;
for(int i = 0 ; i < U ; i++)
if( isOriginal[ C[i] ] && isOriginal[ D[i] ] )
edges.push_back( { perm[ C[i] ] , perm[ D[i] ] } );
InitMap( V - 12 , (int)edges.size() );
for(int i = 0 ; i < (int)edges.size() ; i++)
MakeMap( edges[i].first , edges[i].second );
}
