#include "park.h"
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
#include <iostream>
using namespace std;
int n;
vector<int> graph, pend;
vector<pair<int, int> > edge;
void ans(pair<int, int> i){
int u = i.first, v = i.second;
if(u > v) swap(u, v);
Answer(u, v);
}
vector<int> subarray(int l, int r, vector<int> a){
vector<int> rs;
for(int i = l; i <= r; i ++)
rs.push_back(a[i]);
return rs;
}
bool is_con(int nw, vector<int> g){
vector<int> que(n, 0);
for(int i : g) que[i] = 1;
que[nw] = 1;
return Ask(min(g[0], nw), max(g[0], nw), que.data());
}
bool is_con_via(int nw, vector<int> g, vector<int> p){
vector<int> que(n, 0);
for(int i : g) que[i] = 1;
for(int i : p) que[i] = 1;
que[nw] = 1;
return Ask(min(g[0], nw), max(g[0], nw), que.data());
}
void connect(int nd, vector<int> g){
if(g.empty()) return;
vector<vector<int> > adj(n);
vector<bool> active(n, 0);
for(int i : g) active[i] = 1;
for(auto e : edge){
if(active[e.first] && active[e.second]){
adj[e.first].push_back(e.second);
adj[e.second].push_back(e.first);
}
}
vector<int> ord;
vector<bool> vis(n, 0);
ord.push_back(g[0]); vis[g[0]] = 1;
queue<int> bfs; bfs.push(g[0]);
for(; bfs.size(); bfs.pop()){
int nw = bfs.front();
for(int nx : adj[nw]) if(!vis[nx]){
vis[nx] = 1;
bfs.push(nx);
ord.push_back(nx);
}
}
if(ord.size() != g.size()){
vector<int> g1, g2;
for(int i : g)
if(vis[i]) g1.push_back(i);
else g2.push_back(i);
connect(nd, g1);
connect(nd, g2);
return;
}
if(!is_con(nd, subarray(0, (int)ord.size() - 1, ord)))
return;
int id = (int)ord.size() - 1;
for(int lf = 0, rg = id, md; lf <= rg;){
md = (lf + rg) / 2;
if(is_con(nd, subarray(0, md, ord))){
id = md;
rg = md - 1;
}
else
lf = md + 1;
}
edge.push_back({nd, ord[id]});
g.erase(find(g.begin(), g.end(), ord[id]));
connect(nd, g);
}
vector<int> path;
void find_path(int l, int r){
vector<int> c;
if(l == 0) c = graph;
else c = {l};
if(is_con(r, c)) path.push_back(r);
else{
int id = (int)pend.size() - 1;
for(int lf = 0, rg = id, md; lf <= rg;){
md = (lf + rg) / 2;
if(is_con_via(r, c, subarray(0, md, pend))){
id = md;
rg = md - 1;
}else
lf = md + 1;
}
find_path(l, pend[id]);
find_path(pend[id], r);
}
}
void Detect(int T, int N){
n = N;
graph.push_back(0);
pend.resize(N - 1);
iota(pend.begin(), pend.end(), 1);
for(; pend.size();){
int nw = pend.back();
path.clear();
find_path(0, nw);
for(int u : path){
connect(u, graph);
graph.push_back(u);
pend.erase(find(pend.begin(), pend.end(), u));
}
}
for(pair<int, int> i : edge) ans(i);
return;
}
