#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) {
nodes.push_back(x);
for (auto to:v[x]) {
if (!vis[to]) colect(to);
}
}
void dfs(int x, int node) {
while (true) {
if (vis[x]) return;
nodes.clear();
colect(x);
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; int 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;
}
}
vis[res] = 1;
lst.push_back(res);
for (auto to:v[res]) {
dfs(to,node);
}
}
}
void explore(int x) {
if (f[x]) {
return;
}
if (x <= 0) 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; int r = n-1;
int res = -1;
while (l <= r) {
int mid = (l+r)/2;
for (int i = 0; i < n; i++) {
if (f[i] || (i <= mid)) {
p[i] = 1;
} else {
p[i] = 0;
}
}
p[x] = 1;
p[0] = 1;
if (Ask(0,x,p)) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
explore(res);
for (int i = 0; i < n; i++) {
p[i] = f[i];
}
p[x] = 1;
}
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 < 1500; i++) {
f[i] = 0;
p[i] = 0;
vis[i] = 0;
v[i].clear();
}
f[0] = 1;
lst.clear();
for (int i = 0; i < n; i++) {
explore(i);
}
}
