#include "park.h"
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
static const int N = 1500 + 10;
static int query(int a, int b, int tag[]) {
if (a > b) std::swap(a, b);
return Ask(a, b, tag);
}
static int n;
static int tag[N];
static std::vector<int> adj[N];
static void link(int a, int b) {
if (a > b) std::swap(a, b);
Answer(a, b);
adj[a].push_back(b);
adj[b].push_back(a);
}
static bool flag[N], mark[N];
static std::vector<int> res;
static std::vector<int> bfs(int s) {
std::vector<int> res;
res.push_back(s);
for (int i = 0; i < res.size(); ++i) {
int a = res[i];
mark[a] = false;
for (int j = 0; j < adj[a].size(); ++j) if (mark[adj[a][j]]) res.push_back(adj[a][j]);
}
return res;
}
static void connect(int a, std::vector<int> &cur) {
for (int i = 0; i < n; ++i) tag[i] = 0;
for (int i = 0; i < cur.size(); ++i) tag[cur[i]] = 1;
tag[a] = 1;
if (!query(a, cur[0], tag)) return;
int l = 0, r = cur.size();
while (l < r) {
int mid = (l + r) >> 1;
for (int i = 0; i < n; ++i) tag[i] = 0;
for (int i = 0; i <= mid; ++i) tag[cur[i]] = 1;
tag[a] = 1;
if (query(a, cur[0], tag)) r = mid; else l = mid + 1;
}
int b = cur[l];
link(a, b);
for (int i = 0; i < cur.size(); ++i) mark[cur[i]] = true;
mark[b] = false;
std::vector< std::vector<int> > pool;
for (int i = 0; i < cur.size(); ++i) if (mark[cur[i]]) pool.push_back(bfs(cur[i]));
for (int i = 0; i < pool.size(); ++i) connect(a, pool[i]);
}
static void solve(int a) {
for (int r = n;; solve(r)) {
for (int i = 0; i < n; ++i) tag[i] = flag[i];
tag[a] = 1;
if (query(0, a, tag)) break;
for (int l = 1; l < r;) {
int mid = (l + r) >> 1;
for (int i = 0; i < n; ++i) tag[i] = (i <= mid || flag[i]);
tag[a] = 1;
if (query(0, a, tag)) r = mid; else l = mid + 1;
}
}
memcpy(mark, flag, sizeof mark);
flag[a] = true;
std::vector<int> cur = bfs(0);
connect(a, cur);
}
void Detect(int _t, int _n) {
n = _n;
memset(flag, 0, sizeof flag);
flag[0] = true;
for (int i = 1; i < n; ++i) if (!flag[i]) solve(i);
}
