#include "park.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

namespace {
  const int N=1509;
  int n,P[N],vst[N],in[N],rt,m,sz[N],msz[N],tot,f[N],qe,qr,qt[2],deg;
  map<int,int>ed[N];
  vi e[N],p;
}

void clear() {rep(i,0,n-1) P[i]=0;}
bool query_edge(int x,int y) {
  clear(); P[x]=P[y]=1; if(x>y) swap(x,y); ++qe;
  return Ask(x,y,P);
}
bool query_route(int x,int y,int m) {
  clear(); P[x]=P[y]=1; if(x>y) swap(x,y); ++qr;
  rep(i,m,n) if(!in[i]) P[i]=1;
  return Ask(x,y,P);
}
bool query_tree(int x,int y,bool flag=0) {
  clear(); P[x]=P[y]=1; if(x>y) swap(x,y); ++qt[flag];
  for(int u:p) P[u]=1;
  if(flag) rep(i,0,n-1) if(!in[i]) P[i]=1;
  return Ask(x,y,P);
}
void adde(int x,int y) {
  if(x>y) swap(x,y); Answer(x,y);
}

void dfs1(int u,int fa) {
  sz[u]=1; f[u]=fa;
  for(int v:e[u]) if(v!=fa&&!vst[v])
    dfs1(v,u), sz[u]+=sz[v];
  msz[u]=max(sz[u],m-sz[u]);
  if(sz[u]!=m&&(rt==-1||msz[u]<msz[rt])) rt=u;
}
void dfs2(int u,int fa) {
  sz[u]=1, p.eb(u);
  for(int v:e[u]) if(v!=fa&&!vst[v])
    dfs2(v,u), sz[u]+=sz[v];
}
int work1(int u,int z) {
  m=sz[u]; rt=-1; dfs1(u,-1); if(rt==-1) return u;
  p.clear(); dfs2(rt,f[rt]);
  if(query_tree(rt,z,1)) return vst[f[rt]]=1, work1(rt,z);
  else return vst[rt]=1, work1(f[rt],z);
}
bool work2(int u,int z,bool b=0) {
  m=sz[u]; rt=-1; dfs1(u,-1); bool flag=0;
  if(rt==-1) rt=u, flag=1;
  else assert(f[rt]!=-1);
  int ru=rt, ff=f[rt], su=sz[rt], sf=m-sz[rt];
  p.clear(); dfs2(rt,-1);
  if(b==0&&!query_tree(rt,z)) return 0;
  if(flag) {adde(u,z); deg++; return 1;}
  vst[ff]=1, vst[ru]=0; sz[ru]=su; b=work2(ru,z);
  vst[ff]=0, vst[ru]=1; sz[ff]=sf; work2(ff,z,!b);
  return 1;
}

void work(int l0,int x,int y) {
  if(query_edge(x,y)) {
    rep(i,0,n-1) vst[i]=0; in[y]=1; deg=0;
    sz[0]=tot; work2(0,y); ++tot;
    e[x].eb(y),e[y].eb(x); return;
  }
  int l=l0, r=n-1, w=0;
  while(l<=r) {
    int mid=l+r>>1;
    if(query_route(x,y,mid)) w=mid, l=mid+1;
    else r=mid-1;
  }
  work(w+1,x,w), work(w+1,w,y);
}

void Detect(int _t,int _n) {
  n=_n; in[0]=1; tot=1;
  rep(i,0,n-1) if(!in[i]) {
    sz[0]=tot;
    rep(i,0,n-1) vst[i]=0;
    int y=work1(0,i);
    work(0,y,i);
  }
}