#include "park.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1505;
int f[MAXN];
int n;
static int p[MAXN];
vector<int> lst, nodes, vis(MAXN);
vector<vector<int>> v(MAXN);
void colect(int x) {
if (vis[x]) return;
nodes.push_back(x);
vis[x] = 1;
vector<int> children = v[x];
sort(children.begin(), children.end()); // deterministic traversal
for (auto to : children) {
if (f[to] && !vis[to]) colect(to);
}
}
void dfs(int x, int node) {
sort(v[x].begin(), v[x].end()); // deterministic
while (true) {
if (vis[x]) return;
nodes.clear();
for (int i = 0; i < n; ++i) vis[i] = 0;
colect(x);
if (nodes.empty()) return; // safety
for (int i = 0; i < n; i++) p[i] = 0;
for (auto to : nodes) p[to] = 1;
p[node] = p[x] = 1;
if (!Ask(min(node, x), max(node, x), p)) return;
int l = 0, r = (int)nodes.size() - 1;
int res = -1;
while (l <= r) {
int mid = (l + r) / 2;
for (int i = 0; i < n; ++i) p[i] = 0;
for (int i = 0; i <= mid; ++i) p[nodes[i]] = 1;
p[node] = p[x] = 1;
if (Ask(min(node, x), max(node, x), p)) {
res = nodes[mid];
r = mid - 1;
} else {
l = mid + 1;
}
}
if (res == -1) return; // safety
vis[res] = 1;
lst.push_back(res);
for (auto to : v[res]) {
dfs(to, node);
}
}
}
void explore(int x) {
if (f[x]) return;
for (int i = 0; i < n; i++) p[i] = f[i];
p[x] = 1;
p[0] = 1;
while (!Ask(0, x, p)) {
int l = 0, r = n - 1, res = -1;
while (l <= r) {
int mid = (l + r) / 2;
for (int i = 0; i < n; ++i)
p[i] = (f[i] || i <= mid) ? 1 : 0;
p[x] = 1;
p[0] = 1;
if (Ask(0, x, p)) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (res < 0 || res >= n) return; // safety
explore(res);
}
for (int i = 0; i < n; ++i) vis[i] = 0;
lst.clear();
dfs(0, x);
for (auto u : lst) {
Answer(min(u, x), max(u, x));
}
if (!lst.empty()) v[lst[0]].push_back(x);
f[x] = 1;
}
void Detect(int T, int N) {
n = N;
for (int i = 0; i < MAXN; i++) {
f[i] = 0;
p[i] = 0;
vis[i] = 0;
v[i].clear();
}
f[0] = 1;
for (int i = 0; i < n; i++) {
if (!f[i]) explore(i);
}
}
