#include <bits/stdc++.h>
#include "park.h"
// #include "grader.cpp"
using namespace std;
static int Place[1400];
const int MXN = 1405;
int n, par[MXN], h[MXN];
vector<int> g[MXN], lvl[MXN];
vector<pair<int, int>> edges;
int Query(int u, int v){
Place[u] = Place[v] = 1;
if (u > v) swap(u, v);
int res = Ask(u, v, Place);
memset(Place, 0, sizeof Place);
return res;
}
void get_path(int u, int v){
vector<int> nodes;
for (int x = 0; x < n; x ++){
if (x == u or x == v) continue;
nodes.push_back(x);
}
if (Query(u, v)){
g[u].push_back(v);
g[v].push_back(u);
edges.push_back({u, v});
par[v] = u;
return ;
}
int lo = -1;
int hi = nodes.size() - 1;
while (hi - lo > 1){
int mid = (lo + hi) / 2;
for (int i = 0; i <= mid; i ++)
Place[nodes[i]] = 1;
if (Query(u, v))
hi = mid;
else
lo = mid;
}
get_path(u, nodes[hi]);
get_path(nodes[hi], v);
}
int comp(int u, int v, vector<int> vec){
for (int i = 0; i < n; i ++)
Place[i] = 1;
for (int x : vec)
Place[x] = 0;
return Query(u, v);
}
void Detect(int T, int nn) {
n = nn;
memset(par, -1, sizeof par);
memset(Place, 0, sizeof Place);
if (n <= 250){
for (int u = 0; u < n; u ++){
for (int v = u + 1; v < n; v ++){
Place[u] = Place[v] = 1;
if (Ask(u, v, Place))
Answer(u, v);
Place[u] = Place[v] = 0;
}
}
return;
}
lvl[h[0]].push_back(0);
for (int v = 1; v < n; v ++){
if (g[v].size()) continue;
int lo = 0, hi = n;
while (hi - lo > 1){
int mid = (lo + hi) / 2;
if (lvl[mid].empty() or comp(0, v, lvl[mid]))
hi = mid;
else
lo = mid;
}
int anc_lvl = lo;
lo = -1, hi = lvl[anc_lvl].size() - 1;
while (hi - lo > 1){
int mid = (lo + hi) / 2;
vector<int> vec;
for (int i = 0; i <= mid; i ++)
vec.push_back(lvl[anc_lvl][i]);
if (comp(0, v, vec))
lo = mid;
else
hi = mid;
}
int anc = lvl[anc_lvl][hi];
get_path(anc, v);
int u = v;
vector<int> path;
while (u != anc){
path.push_back(u);
u = par[u];
}
while (path.size()){
u = path.back();
path.pop_back();
h[u] = h[par[u]] + 1;
lvl[h[u]].push_back(u);
}
}
for (auto [u, v] : edges)
Answer(min(u, v), max(u, v));
}
