#include "park.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int,int>,bool> mp;
bool comp(int a,int b)
{
if (!mp.count({a,b}))
{
int on[1400]={};
for (int i=0;i<1400;i++)
on[i]=1;
on[a]=0;
if (Ask(0,b,on))
mp[{a,b}]=0,mp[{b,a}]=1;
else
mp[{a,b}]=1,mp[{b,a}]=0;
}
return mp[{a,b}];
}
void Detect(int T, int n){
int on[1400]={};
if (T==1)
{
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
{
on[i]=on[j]=1;
if (Ask(i,j,on))
Answer(i,j);
on[i]=on[j]=0;
}
return;
}
else if(T==2)
{
if (n==2)
{
Answer(0,1);
return;
}
vector<int> v;
for (int i=1;i<n-1;i++)
v.push_back(i);
sort(v.begin(),v.end(),comp);
Answer(0,v[0]);
Answer(v.back(),n-1);
for (int i=0;i+1<v.size();i++)
Answer(min(v[i],v[i+1]),max(v[i],v[i+1]));
}
vector<int> dep[9];
dep[0]={0};
int par[n];
bool vis[n]={};
for (int d=1;d<=9;d++)
{
for (int j=d-1;j>=0;j--)
for (int u:dep[j])
on[u]=1;
for (int i=1;i<n;i++)
if (!vis[i])
{
on[i]=1;
if (Ask(0,i,on))
dep[d].push_back(i),vis[i]=1;
on[i]=0;
}
for (int i=0;i<n;i++) on[i]=0;
for (int u:dep[d])
{
int s=-1,e=dep[d-1].size()-1;
while (s+1<e)
{
int mid=(s+e)/2;
on[0]=on[u]=1;
for (int j=0;j<=mid;j++)
{
int v=dep[d-1][j];
while (v)
on[v]=1,v=par[v];
}
if (Ask(0,u,on))
e=mid;
else
s=mid;
for (int i=0;i<n;i++) on[i]=0;
}
par[u]=dep[d-1][e];
Answer(min(par[u],u),max(par[u],u));
}
}
}
