#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
int przewodnik[200];
vector<int> spojne[200];
vector<int> mam;
int n;
int aaa[200],bbb[200];
int Query(int a1,int b1,vector<int> a,vector<int> b)
{
for(int i=0;i<a1;i++)
aaa[i]=a[i];
for(int i=0;i<b1;i++)
bbb[i]=b[i];
return query(a1,b1,aaa,bbb);
}
void dodaj(int x,int y)
{
setRoad(x,y);
x=przewodnik[x];
y=przewodnik[y];
for(int i=0;i<spojne[x].size();i++)
spojne[y].push_back(spojne[x][i]),przewodnik[spojne[x][i]]=y;
spojne[x].clear();
mam.clear();
for(int i=1;i<=n;i++)
if(spojne[i].size())
mam.push_back(i);
}
void pytaj(vector<pair<int,int>> przedzialy)
{
vector<int> a[2];
for(int i=0;i<przedzialy.size();i++)
for(int j=przedzialy[i].first;j<=przedzialy[i].second;j++)
for(int b=0;b<spojne[mam[j]].size();b++)
a[i%2].push_back(spojne[mam[j]][b]);
int co=Query(a[0].size(),a[1].size(),a[0],a[1]);
if(co==0)
{
vector<pair<int,int> > jazda;
for(int i=0;i<przedzialy.size();i++)
{
if(przedzialy[i].first==przedzialy[i].second)
continue;
jazda.push_back({przedzialy[i].first,(przedzialy[i].first+przedzialy[i].second)/2});
jazda.push_back({(przedzialy[i].first+przedzialy[i].second)/2+1,przedzialy[i].second});
}
pytaj(jazda);
return;
}
int pocz=0,kon=a[0].size(),sre,ostd;
while(pocz<kon)
{
sre=(pocz+kon)/2;
vector<int> pytanko;
for(int i=pocz;i<=sre;i++)
pytanko.push_back(a[0][i]);
int co=Query(pytanko.size(),a[1].size(),pytanko,a[1]);
if(co)
{
ostd=sre;
kon=sre;
}
else pocz=sre+1;
}
int pocz1=0,kon1=a[1].size(),sre1,ostd1;
while(pocz1<kon1)
{
sre1=(pocz1+kon1)/2;
vector<int> pytanko;
for(int i=pocz1;i<=sre1;i++)
pytanko.push_back(a[1][i]);
int co=Query(pytanko.size(),a[0].size(),pytanko,a[0]);
if(co)
{
ostd1=sre1;
kon1=sre1;
}
else pocz1=sre1+1;
}
dodaj(a[0][ostd],a[1][ostd1]);
return;
}
void run(int N)
{
n=N;
for(int i=1;i<=n;i++)
spojne[i].push_back(i),mam.push_back(i),przewodnik[i]=i;
for(int i=1;i<n;i++)
{
vector<pair<int,int> > przedzialy;
przedzialy.push_back({0,mam.size()/2-1});
przedzialy.push_back({mam.size()/2,mam.size()-1});
pytaj(przedzialy);
}
}
