#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];
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){
for(int i=1;i<n;i++){
if(need[i].size()==0){
int r=n-2;
need[i].pb(i);
while(r>=0){
vector<int>v(n-1);
for(int j=0;j<n-1;j++){
v[j]=j+(j>=i);
}
int l=0;
while(l<r){
int mi=(l+r)/2;
for(int j=0;j<=mi;j++){
arr[v[j]]=1;
}
for(int j=mi+1;j<n-1;j++){
arr[v[j]]=0;
}
for(int j:need[i]){
arr[j]=1;
}
arr[i]=1;
if(ask(0,i))r=mi;
else l=mi+1;
}
if(need[v[r]].size()){
for(int j:need[v[r]]){
need[i].pb(j);
}
break;
}
need[i].pb(v[r]);
r--;
}
for(int j:need[i]){
need[j]=need[i];
}
}
for(int j:need[i]){
if(j==i)continue;
for(int l=0;l<n;l++){
arr[l]=0;
}
arr[i]=arr[j]=1;
if(ask(i,j))answer(i,j);
}
}
return;
}
}
