#include "park.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=1405;
int n;
vector<vector<int>> al(maxn);
vector<bool> found(maxn, 0);
vector<int> tin(maxn), tintoind(maxn);
vector<int> nw;
int head=-1;
int Query(int a, int b, int place[]){
if(a>b)swap(a,b);
return Ask(a, b, place);
}
void nwpath(int x, int y){
if(x==y)return;
//printf("nwpath x %d to y %d\n", x, y);
int place[1400];
int hi=n-1, lo=-1, ans=-1, m;
while(hi>=lo){
m=(hi+lo)/2;
fill(place,place+1400,0);
place[x]=1, place[y]=1;
for(int i=0;i<=m;i++)place[i]=1;
for(int i=0;i<=n;i++)if(found[i])place[i]=1;
int can=Query(x, y, place);
if(can){
ans=m;
hi=m-1;
}
else lo=m+1;
}
if(ans==-1){ // direct edge.
//printf("direct edge from %d to %d\n", x, y);
nw.pb(x);
nw.pb(y);
if(x==0){
head=y;
}
else {
al[x].pb(y);
al[y].pb(x);
}
}
else{
nwpath(x, ans);
nwpath(ans, y);
}
}
void Detect(int T, int N) {
n=N;
found[0]=1;
for(int i=1; i<N;i++){
if(found[i])continue;
nw.clear();
head=-1;
nwpath(0, i);
assert(head != -1);
for(auto it : nw)found[it]=1;
// attach nwpath to the tree via bsta again.
int t=0;
auto dfs=[&](auto && dfs, int x, int p)->void{
tin[x]=t;
tintoind[t]=x;
t++;
for(auto it : al[x])if(it != p)dfs(dfs, it, x);
};
dfs(dfs, 0, 0);
// bsta 0 to t-1;
int hi=t-1, lo=0, m, ans=-1;
while(hi >= lo){
m=(hi+lo)/2;
int place[1400];fill(place,place+1400,0);
place[head]=1;
for(int i=0;i<=m;i++){
place[tintoind[i]]=1;
}
int c=Query(0, head, place);
if(c){
ans=m;
hi=m-1;
}
else {
lo=m+1;
}
}
//printf("connecting head %d to tree node %d\n", head, tintoind[ans]);
assert(ans != -1);
al[tintoind[ans]].pb(head);
al[head].pb(tintoind[ans]);
}
auto dfs=[&](auto && dfs, int x, int p)->void{
for(auto it : al[x])if(it != p){
Answer(min(it, x), max(it, x));
dfs(dfs, it, x);
}
};
dfs(dfs, 0, 0);
}
