#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#include "park.h"
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
int rint(int a,int b){
int ans=0;
ans=a+(rng()%(b-a+1));
return ans;
}
int n;
static int arr[1400];
vector<int>need[1400];
int pri[1400];
set<pair<int,int>>soruldu;
void answer(int x,int y){
if(x>y)swap(x,y);
if(soruldu.count({x,y}))return;
soruldu.insert({x,y});
Answer(x,y);
}
bool ask(int x,int y){
if(x>y)swap(x,y);
return Ask(x,y,arr);
}
vector<int> fastsort(vector<int>v,int left){
if(!v.size())return v;
int x=rint(0,v.size()-1);
vector<int>a,b;
for(int i=0;i<v.size();i++){
if(i==x)continue;
for(int j=0;j<n;j++){
arr[j]=0;
}
for(int j=0;j<v.size();j++){
arr[v[j]]=1;
}
arr[v[i]]=0;
arr[left]=1;
if(ask(left,v[x])){
b.pb(v[i]);
}
else{
a.pb(v[i]);
}
}
a=fastsort(a,left);
b=fastsort(b,v[x]);
x=v[x];
v.clear();
if(a.size())answer(a.back(),x);
if(b.size())answer(b[0],x);
for(int y:a){
v.pb(y);
}
v.pb(x);
for(int y:b){
v.pb(y);
}
return v;
}
void Detect(int T, int N) {
n=N;
if(T==1){
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
for(int l=0;l<n;l++){
arr[l]=0;
}
arr[i]=arr[j]=1;
if(ask(i,j))answer(i,j);
}
}
return;
}
if(T==2){
vector<int>v(n-2);
iota(v.begin(),v.end(),1);
v=fastsort(v,0);
if(n==2){
answer(0,1);
return;
}
answer(0,v[0]);
answer(v.back(),n-1);
return;
}
if(true){
vector<int>perm,temp={0};
while(perm.size()+temp.size()!=n){
vector<int>nex;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
arr[j]=0;
}
for(int x:perm){
arr[x]=1;
}
for(int x:temp){
arr[x]=1;
}
while(i<n&&arr[i])i++;
if(i>=n)break;
arr[i]=1;
if(ask(0,i))nex.pb(i);
}
for(int i:nex){
int l=0,r=temp.size()-1;
while(l<r){
int mi=(l+r)/2;
for(int j=0;j<n;j++){
arr[j]=0;
}
for(int x:perm){
arr[x]=1;
}
for(int j=0;j<=mi;j++){
arr[temp[j]]=1;
}
arr[i]=1;
if(ask(0,i))r=mi;
else l=mi+1;
}
answer(i,temp[l]);
}
while(temp.size()){
perm.pb(temp.back());
temp.pop_back();
}
swap(nex,temp);
}
return;
}
}
