#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
using namespace std ;
bool isOn(int i, int m) { return ((1<<i)&m) != 0 ; }
void Alice( int N, int M, int A[], int B[] ){
if(N == 1)
{
InitG(1,0) ;
return ;
}
int _log = 9 ;
vector< pair<int,int> > edge ;
for(int i = 0 ; i< M ; i++ ) edge.push_back( make_pair(A[i] , B[i]) ) ;
for(int i = 0 ; i <= _log ; i++ )
for(int j = 0 ; j < N ; j++ )
if(isOn(i,j+1)) edge.push_back( make_pair(i+N, j) ) ;
for(int i = 0 ; i < _log ; i++ ) edge.push_back(make_pair(i+N, i+1+N)) ;
for(int i = N ; i <= N+_log ; i++ ) edge.push_back( make_pair(N+_log+1, i) ) ;
for(int i = 0 ; i <= N+_log ; i++ ) edge.push_back( make_pair(N+_log+2 , i ) ) ;
//for(auto e : edge ) cout << e.first << " " << e.second << endl ;
InitG(N+_log+3, sz(edge)) ;
for(int i = 0 ; i < sz(edge) ; i++ ) MakeG( i, edge[i].first, edge[i].second );
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#define debug printf
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
using namespace std ;
void Bob( int V, int U, int C[], int D[] ){
if(V == 1)
{
InitMap(1,0) ;
return ;
}
int cnt = 0 ;
vector<int> deg( V, 0 ) ;
vector<vector<int> > adj(V, vector<int>()) ;
for(int i = 0 ; i < U ; i++ )
{
deg[ C[i] ]++ ;
deg[ D[i] ]++ ;
adj[ C[i] ].push_back(D[i]) ;
adj[ D[i] ].push_back(C[i]) ;
}
vector<int> idx(V) ; iota(all(idx), 0) ;
sort(all(idx) ,[&](int i, int j) { return deg[i] < deg[j]; }) ;
vector<bool> mark(V, false) ;
mark[ idx[V-1] ] = true ;
for(auto e : adj[ idx[V-1] ])
mark[e] = true ;
int indicador = V-1 ;
while(mark[indicador]) { indicador--; }
vector<bool> isBoring(V, true) ;
vector<int> soma(V, 0) ;
for(auto e : adj[indicador]) isBoring[e] = false ;
isBoring[ idx[V-1] ] = isBoring[indicador] = false ;
for(int i = 0 ; i < V ; i++ ) cnt += isBoring[i] ;
//for(int i = 0 ; i < V ; i++ ) cout << idx[i] << " " << deg[idx[i]] << " " << isBoring[idx[i]] << endl ;
int curLast ;
for(int i = 0 ; i < V-1 ; i++ )
if( idx[i] != indicador && !isBoring[idx[i]] )
{
curLast = idx[i] ;
break ;
}
for(int i = 0 ; i < V ; i++ ) mark[i] = false ;
mark[ idx[V-1] ] = mark[indicador] = true ;
int curBit = 9 ;
while(curLast != -1)
{
mark[curLast] = true ;
int nxt = -1 ;
for(auto e : adj[curLast])
{
if(isBoring[e])
soma[e] += (1<<curBit) ;
else if(!mark[e]) nxt = e ;
}
curBit--;
curLast = nxt ;
}
vector< pair<int,int> > edge ;
for(int i = 0 ; i < U ; i++ )
{
int a = C[i] ;
int b = D[i] ;
if( !isBoring[a] || !isBoring[b] ) continue ;
edge.push_back( make_pair( soma[a]-1, soma[b]-1 ) ) ;
}
//cout <<"edges" << endl ;
//for(auto e : edge ) cout << e.first << " " << e.second << endl ;
InitMap(cnt, sz(edge)) ;
for(auto e : edge ) MakeMap(e.first, e.second ) ;
}
