#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++)
//didn't add lgn to the vertices pushed into xtra
void Alice(int N, int M, int A[], int B[])
{
vector<pii>tbp;
int lgn=10;
for(int i=0;i<(lgn-1);i++){tbp.pb(mp(i,i+1));}
vector<int>xtra,deg(N,0);
for(int i=0;i<M;i++){deg[A[i]]++;deg[B[i]]++;}
for(int i=0;i<N;i++)
{
if(deg[i]==0){xtra.pb(i);continue;}
for(int ii=0;ii<lgn;ii++)
{
if((1ll<<ii)&(i+1)){tbp.pb(mp(ii,lgn+i));}
}
}
for(int i=0;i<M;i++){tbp.pb(mp(A[i]+lgn,B[i]+lgn));}
int pang=N+lgn;
for(int i=0;i<lgn;i++)
{
tbp.pb(mp(pang,i));
}
tbp.pb(mp(pang,pang+1));
if(xtra.size()>=2){tbp.pb(mp(xtra[0]+lgn,0));tbp.pb(mp(xtra[1]+lgn,0));}
InitG(N+12,tbp.size());
int t1=0;
for(pii xx:tbp){MakeG(t1,xx.ff,xx.ss);t1++;}
}
#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++)
//mixing up U and V...
void Bob(int V, int U, int C[], int D[])
{
vector<int>deg(V);
vector<vi>aj(V);
for(int i=0;i<U;i++)
{
deg[C[i]]++;deg[D[i]]++;
aj[C[i]].pb(D[i]);
aj[D[i]].pb(C[i]);
}
vector<int>leafno(V,0);
for(int i=0;i<V;i++)
{
if(deg[i]==1){leafno[aj[i][0]]++;}
}
int star=-1,pang;
for(int i=0;i<V;i++){if(leafno[i]==1)pang=i;if(leafno[i]==2)star=i;}
vector<bool>isgraph(V,true);
for(int to:aj[pang])isgraph[to]=false;
vector<int>mycorr(V,0);
int t1=0,t2=0;
if(star==-1)
{
for(int i=0;i<V;i++)
{
if(isgraph[i])continue;
t1=0;for(int to:aj[i]){t1+=(!isgraph[to]);}
if(t1==1&&aj[i].size()>t2){t2=aj[i].size();star=i;}
}
}
vector<bool>vis(V,false);
t1=0;
while(true)
{
vis[star]=true;
for(int to:aj[star]){mycorr[to]+=(1ll<<t1);}
for(int to:aj[star]){if(!isgraph[to]&&!vis[to])star=to;}
t1++;
if(vis[star])break;
}
isgraph[pang]=false;
//for(int i=0;i<V;i++){if(deg[i]==1)isgraph[i]=false;}
vector<pii>tbp;
for(int i=0;i<U;i++)
{
if(isgraph[C[i]]&&isgraph[D[i]])
tbp.pb(mp(mycorr[C[i]]-1,mycorr[D[i]]-1));
}
InitMap(V-12,tbp.size());
for(pii xx:tbp){MakeMap(xx.ff,xx.ss);}
}
