#include "park.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1407;
static int Place[1400];
vector<int>V[LIM], pos, ord;
int odw[LIM], oc[LIM], usun[LIM], n, ile;
void DFS(int x, int o) {
for(auto i : V[x]) if(i!=o) DFS(i, x);
pos.pb(x);
}
int znajdz_ojca(int x) {
pos.clear();
DFS(0, 0);
reverse(all(pos));
int po=0, ko=(int)pos.size()-1;
while(po<ko) {
int sr=(po+ko)/2;
rep(i, n) Place[i]=0;
rep(i, sr+1) Place[pos[i]]=1;
rep(i, n) if(!odw[i]) Place[i]=1;
if(Ask(0, x, Place)) ko=sr; else po=sr+1;
}
return pos[po];
}
void sciezka(int a, int b) {
rep(i, n) Place[i]=0;
Place[a]=Place[b]=1;
if(Ask(min(a, b), max(a, b), Place)) {
odw[b]=1; ++ile;
V[a].pb(b);
V[b].pb(a);
Answer(min(a, b), max(a, b));
return;
}
vector<int>T;
rep(i, n) if(!odw[i] && i!=b) T.pb(i);
int po=0, ko=(int)T.size()-1;
while(po<ko) {
int sr=(po+ko)/2;
rep(i, n) Place[i]=0;
rep(i, sr+1) Place[T[i]]=1;
Place[a]=Place[b]=1;
if(Ask(min(a, b), max(a, b), Place)) ko=sr; else po=sr+1;
}
sciezka(a, T[po]);
sciezka(T[po], b);
}
void DFS2(int x, int o) {
oc[x]=o;
for(auto i : V[x]) if(i!=o) DFS2(i, x);
}
void DFS4(int x) {
if(usun[x]) return;
ord.pb(x);
for(auto i : V[x]) if(i!=oc[x]) DFS4(i);
}
void DFS3(int x, int p) {
for(auto i : V[x]) if(i!=oc[x]) {
while(true) {
ord.clear();
DFS4(i);
if(ord.size()==0) break;
rep(j, n) Place[j]=0;
Place[p]=1;
for(auto j : ord) Place[j]=1;
if(!Ask(min(p, ord[0]), max(p, ord[0]), Place)) break;
int po=0, ko=ord.size()-1;
while(po<ko) {
int sr=(po+ko)/2;
rep(j, n) Place[j]=0;
Place[p]=1;
rep(j, sr+1) Place[ord[j]]=1;
if(Ask(min(p, ord[0]), max(p, ord[0]), Place)) ko=sr; else po=sr+1;
}
usun[ord[po]]=1;
if(p<ord[po]) Answer(p, ord[po]);
DFS3(ord[po], p);
}
}
}
void Detect(int T, int N) {
n=N;
odw[0]=ile=1;
while(ile<n) {
int x=-1;
rep(i, n) if(!odw[i]) {
x=i;
break;
}
int p=znajdz_ojca(x);
sciezka(p, x);
}
rep(a, n) {
a=1;
DFS2(a, a);
rep(b, n) usun[b]=0;
for(auto b : V[a]) usun[b]=1;
for(auto b : V[a]) DFS3(b, a);
break;
}
}
