#include "park.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
static int Place[1400];
const int N = 1405;
int Query(int u, int v){
if(u > v) swap(u, v);
return Ask(u, v, Place);
}
int n;
int added[N];
vector<int> ord, rem;
void Add(int u){
if(added[u])
return;
rem = {u};
for(int i = 0; i < n; i++)
if(!added[i] && i != u)
rem.pb(i);
int L = 0, R = rem.size();
while(L + 1 < R){
int mid = (L + R) >> 1;
memset(Place, 0, sizeof Place);
for(auto x : ord)
Place[x] = 1;
for(int i = 0; i < mid; i++)
Place[rem[i]] = 1;
if(Query(ord[0], rem[0])) R = mid;
else L = mid;
}
if(R == 1){
added[u] = 1;
ord.pb(u);
return ;
}
int v = rem[L];
Add(v);
Add(u);
}
vector<int> G[N];
void Add_Edge(int u, int v){
if(u > v) swap(u, v);
Answer(u, v);
// cerr << "!! " << u << ' ' << v << '\n';
G[u].pb(v);
G[v].pb(u);
}
vector<int> dfs;
int mk[N];
void DFS(int u){
mk[u] = 1;
dfs.pb(u);
for(auto adj : G[u])
if(!mk[adj])
DFS(adj);
}
void Find_Edges(vector<int> V, int u){
if(V.empty())
return ;
memset(Place, 0, sizeof Place);
for(auto x : V)
Place[x] = 1;
Place[u] = 1;
if(!Query(V[0], u)) return ;
memset(mk, 1, sizeof mk);
for(auto x : V)
mk[x] = 0;
dfs.clear();
DFS(V[0]);
assert(dfs.size() == V.size());
int L = 0, R = V.size();
while(L + 1 < R){
int mid = (L + R) >> 1;
for(int i = 0; i < (int) V.size(); i++)
Place[dfs[i]] = (i < mid);
if(Query(dfs[0], u))
R = mid;
else
L = mid;
}
Add_Edge(u, dfs[L]);
for(auto x : V)
mk[x] = 0;
mk[dfs[L]] = 1;
vector< vector<int> > com;
for(auto x : V){
if(mk[x]) continue;
dfs.clear();
DFS(x);
com.pb(dfs);
}
for(auto cm : com)
Find_Edges(cm, u);
}
void Detect(int T, int _n) {
assert(T < 6);
n = _n;
ord.pb(0); added[0] = 1;
for(int i = 1; i < n; i++)
Add(i);
vector<int> nw = {0};
for(int i = 1; i < n; i++){
Find_Edges(nw, ord[i]);
nw.pb(ord[i]);
}
}
