#include "park.h"
#include <bits/stdc++.h>
using namespace std;
void Detect(int T, int N) {
vector<int> graph;
vector<int> candidate;
vector<pair<int, int>> edges;
graph.emplace_back(0);
for (int i = 1; i < N; i++) {
candidate.emplace_back(i);
}
const auto CreateVector = [&](int l, int r, vector<int> a) {
vector<int> res;
for (int i = l; i <= r; i++) {
res.emplace_back(a[i]);
}
return res;
};
const auto IsConnected = [&](int node, vector<int> g) -> bool {
vector<int> query(N, 0);
for (auto i : g) {
query[i] = 1;
}
query[node] = 1;
return Ask(min(g[0], node), max(g[0], node), query.data());
};
const auto IsConnectedTrough = [&](int node, vector<int> g, vector<int> add) -> bool {
vector<int> query(N, 0);
for (auto i : g) {
query[i] = 1;
}
for (auto i : add) {
query[i] = 1;
}
query[node] = 1;
return Ask(min(g[0], node), max(g[0], node), query.data());
};
function<void(int, vector<int>)> Connect = [&](int node, vector<int> g) -> void {
if (g.empty()) return;
vector<vector<int>> adj(N);
vector<int> active(N);
for (auto i : g) {
active[i] = 1;
}
for (auto e : edges) {
if (active[e.first] && active[e.second]) {
adj[e.first].emplace_back(e.second);
adj[e.second].emplace_back(e.first);
}
}
vector<int> vis;
vector<int> invis(N, 0);
vis.emplace_back(g[0]);
invis[g[0]] = 1;
for (int ptr = 0; ptr < (int) vis.size(); ptr++) {
int u = vis[ptr];
for (auto v : adj[u]) {
if (!invis[v]) {
invis[v] = 1;
vis.emplace_back(v);
}
}
}
if (vis.size() != g.size()) {
vector<int> p1, p2;
for (auto i : g) {
if (invis[i]) {
p1.emplace_back(i);
} else {
p2.emplace_back(i);
}
}
Connect(node, p1);
Connect(node, p2);
return;
}
if (!IsConnected(node, CreateVector(0, int(vis.size()) - 1, vis))) {
return;
}
int lo = 0, hi = int(vis.size()) - 1;
while (lo < hi) {
int md = (lo + hi) / 2;
if (IsConnected(node, CreateVector(0, md, vis))) {
hi = md;
} else {
lo = md + 1;
}
}
edges.emplace_back(node, vis[lo]);
g.erase(find(begin(g), end(g), vis[lo]));
return Connect(node, g);
};
while (!candidate.empty()) {
int node = candidate.back();
vector<int> path;
function<void(int, int)> FindPath = [&](int l, int r) {
vector<int> c;
if (l == 0) {
c = graph;
} else {
c = {l};
}
if (IsConnected(r, c)) {
path.emplace_back(r);
} else {
// Find a node on path from l to r
int lo = 0, hi = int(candidate.size()) - 1;
while (lo < hi) {
int md = (lo + hi) / 2;
if (IsConnectedTrough(r, c, CreateVector(0, md, candidate))) {
hi = md;
} else {
lo = md + 1;
}
}
FindPath(l, candidate[lo]);
FindPath(candidate[lo], r);
}
};
FindPath(0, node);
for (auto u : path) {
Connect(u, graph);
graph.emplace_back(u);
candidate.erase(find(begin(candidate), end(candidate), u));
}
}
for (auto e : edges) {
Answer(min(e.first, e.second), max(e.first, e.second));
}
}
