#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
long long n,nn[2],dsu[169],od[169];
bitset<169> kd;
int ca[2][169];
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
void run(int on)
{
long long i,j,ii,k,c,c2,mk,mk2,e,e2,lh,rh,md,zz,z[2];
n=on;
for(i=1;i<=n;i++)
{
dsu[i]=i;
}
for(;1;)
{
c=0;
for(i=1;i<=n;i++)
{
if(fd(i)==i)
{
od[i]=c;
c++;
}
}
if(c==1)
{
break;
}
mk=0;
for(i=0;1ll<<i<c;i++)
{
for(ii=0;ii<2;ii++)
{
nn[ii]=0;
}
for(j=1;j<=n;j++)
{
kd[j]=od[fd(j)]>>i&1;
ca[kd[j]][nn[kd[j]]]=j;
nn[kd[j]]++;
}
k=query(nn[0],nn[1],ca[0],ca[1]);
mk|=k<<i;
if(k)
{
e=i;
}
}
for(ii=0;ii<2;ii++)
{
nn[ii]=0;
}
c2=0;
for(i=1;i<=n;i++)
{
kd[i]=od[fd(i)]>>e&1;
ca[kd[i]][nn[kd[i]]]=i;
nn[kd[i]]++;
c2+=!kd[i]&&fd(i)!=i;
}
e=n-c-c2>c2;
for(ii=0;ii<2;ii++)
{
e2=ii^e;
for(zz=nn[e2],lh=1,rh=nn[e2]-1;lh<=rh;)
{
md=(lh+rh)/2;
swap(nn[e2],md);
k=query(nn[0],nn[1],ca[0],ca[1]);
swap(nn[e2],md);
if(k)
{
zz=md;
rh=md-1;
}
else
{
lh=md+1;
}
}
z[ii]=ca[e2][zz-1];
if(!ii)
{
mk2=od[fd(z[ii])]^mk;
nn[!e2]=0;
for(i=1;i<=n;i++)
{
if(od[fd(i)]==mk2)
{
ca[!e2][nn[!e2]]=i;
nn[!e2]++;
}
}
}
}
setRoad(z[0],z[1]);
dsu[fd(z[1])]=fd(z[0]);
}
}
