#include "park.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)
using namespace std;
using ll=long long;
const char en='\n';
static int Place[1400];
int n,de[1400],par[1400];
vi im[1400],sv,cur;
bool bio[1400];
int rmq(int a,int b) //max
{
int lo=-1,hi=n-1;
while (lo<hi)
{
int mid=(lo+hi+2)/2-1;
for (int i=0;i<=mid;++i) Place[i]=1;
for (int i=mid+1;i<n;++i) Place[i]=0;
Place[a]=1;
Place[b]=1;
if (Ask(min(a,b),max(a,b),Place)) hi=mid;
else lo=mid+1;
}
return lo;
}
void cons(int l,int r)
{
int a=rmq(l,r);
if (a==-1) return;
cons(l,a);
cur.pb(a);
cons(a,r);
}
mt19937 rng(177);
void Detect(int T, int N) {
if (T==1)
{
for (int i=0;i<N;++i)
{
for (int j=i+1;j<N;++j)
{
Place[i]=Place[j]=1;
if (Ask(i,j,Place)) Answer(i,j);
Place[i]=Place[j]=0;
}
}
return;
}
n=N;
vi ord;
for (int i=1;i<n;++i) ord.pb(i);
shuffle(all(ord),rng);
im[0].pb(0);
bio[0]=1;
sv.pb(0);
int mad=0;
for (auto i: ord)
{
if (bio[i]) continue;
int lo=0,hi=mad;
while (lo<hi)
{
int mid=(lo+hi+1)/2;
for (int i=0;i<n;++i) Place[i]=1;
for (auto a: sv) if (de[a]>=mid) Place[a]=0;
if (Ask(0,i,Place)) hi=mid-1;
else lo=mid;
}
int dd=lo;
lo=0;
hi=im[dd].size()-1;
while (lo<hi)
{
int mid=(lo+hi)/2;
for (int i=0;i<n;++i) Place[i]=1;
for (int i=0;i<=mid;++i) Place[im[dd][i]]=0;
if (Ask(0,i,Place)) lo=mid+1;
else hi=mid;
}
int no=im[dd][lo];
//cout<<i<<' '<<no<<endl;
cur.clear();
cur.pb(no);
cons(no,i);
cur.pb(i);
for (int i=1;i<cur.size();++i)
{
par[cur[i]]=cur[i-1];
de[cur[i]]=de[cur[i-1]]+1;
im[de[cur[i]]].pb(cur[i]);
bio[cur[i]]=1;
sv.pb(cur[i]);
mad=max(mad,de[cur[i]]);
//cout<<cur[i]<<' '<<par[cur[i]]<<' '<<de[cur[i]]<<endl;
Answer(min(cur[i-1],cur[i]),max(cur[i-1],cur[i]));
}
}
}
