#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
#define vi vector<int>
#define vpii vector<pii>
#define fr(i,x,y) for(int i=x;i<=y;i++)
void Alice( int N, int M, int A[], int B[] )
{
//edge case n=1,2,3,4?
//c1 to all the n nodes + 2 extra
//all not connected to c1 is for degrees
//=> d1 : my logs => 0,1,2,...lgn-1
//=> in d1: connected to lgn-1 + 1/2n => is ok for larger numbers
//ok for when ur lg < 1/2 of u (ur>=4)
//0,1,2
//c1;
vector<pii>tbp;
int x=1,lgn=1;
while(x*2<=N)
{
x*=2;lgn++;
}
//c1;
//debu(lgn);
int ca=lgn;
for(int i=1;i<lgn;i++)
{
for(int ii=lgn;ii<=ca;ii++)
{
tbp.pb(mp(i,ii));
}
ca++;
}
//debu(ca);
for(int i=0;i<N;i++)
{
for(int ii=0;ii<lgn;ii++)
{
if((1<<ii)&i){tbp.pb(mp(ii,i+ca));}
}
}
//debu(ca);
for(int i=0;i<M;i++){tbp.pb(mp(A[i]+ca,B[i]+ca));}
//debu(tbp.size());
//for(pii xx:tbp){debu2(xx.ff,xx.ss);}
int mi=ca+N;
for(int i=ca;i<ca+N;i++)
{
tbp.pb(mp(ca+N,i));
}
ca+=(N+1);
vector<int>amt(ca,0);
for(pii xx:tbp)
{
amt[xx.ff]++;
amt[xx.ss]++;
}
int bi=0;
fr(i,0,ca-1){bi=max(bi,amt[i]);}
int curr=N;
while(curr<=bi){curr++;tbp.pb(mp(ca,mi));ca++;}
//c1;
InitG(ca,tbp.size());
int t1=0;
for(pii xx:tbp){MakeG(t1,xx.ff,xx.ss);t1++;}
//for(pii xx:tbp){debu2(xx.ff,xx.ss);}
//c2;
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
#define vi vector<int>
#define vpii vector<pii>
#define fr(i,x,y) for(int i=x;i<=y;i++)
void Bob(int V, int U, int C[], int D[])
{
//c1;
//for(int i=0;i<U;i++){debu2(C[i],D[i]);}
int mi,t1=0;
vector<vi>aj(V);
for(int i=0;i<U;i++)
{
aj[C[i]].pb(D[i]);
aj[D[i]].pb(C[i]);
}
for(int i=0;i<V;i++)
{
if(aj[i].size()>t1){t1=aj[i].size();mi=i;}
}
//debu(mi);
vector<bool>partof(V,false);
for(int to:aj[mi])partof[to]=true;
vector<int>mycorr(V,0);
for(int i=0;i<V;i++)
{
if(partof[i]||i==mi)continue;
t1=0;
for(int x:aj[i]){if(!partof[x])t1++;}
for(int x:aj[i])
{
if(partof[x]){mycorr[x]+=(1ll<<t1);}
}
}
//rangeout(mycorr,0,V);
vector<pii>tbp;
for(int i=0;i<V;i++)
{
if(!partof[i])continue;
//debu(i);
for(int to:aj[i])
{
if(partof[to]&&to<i){tbp.pb(mp(mycorr[i],mycorr[to]));}
//debu2(mycorr[i],mycorr[to]);}
}
}
int amt=0;
for(int x:mycorr){
amt=max(amt,x);
}
//debu(tbp.size());
InitMap(amt+1,tbp.size());
for(pii xx:tbp){MakeMap(xx.ff,xx.ss);}
//c2;
}
