#include "park.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static int Place[1400];
int a[1400];
int ask(int x, int y){return Ask(min(x, y), max(x, y), Place);}
void answer(int x, int y){Answer(min(x, y), max(x, y));}
void _sort(int n){
vector<int> ans = {0};
for (int i=1;i<n;i++){
fill(Place, Place+1400, 1);
int l = 1, r = (int)ans.size()-1, idx = 0;
while(l<=r){
int m = (l+r)>>1;
for (int j=0;j<m;j++) Place[ans[j]] = 1;
for (int j=m;j<(int)ans.size();j++) Place[ans[j]] = 0;
if (ask(0, i)) r = m-1;
else l = m+1, idx = m;
}
ans.insert(ans.begin()+idx+1, i);
}
for (int i=0;i<n;i++) a[i] = ans[i];
}
vector<int> adj[1400], C, W;
int visited[1400];
void dfs(int s){
if (visited[s]) return;
visited[s] = 1;
W.push_back(s);
for (auto &v:adj[s]) if (Place[v]) dfs(v);
}
void solve(vector<int> V, int x){
fill(Place, Place+1400, 0);
fill(visited, visited+1400, 0);
Place[x] = 1;
for (auto &v:V) Place[v] = 1;
if (!ask(x, V[0])) return;
W.clear();
dfs(V[0]);
int l = 0, r = (int)V.size()-1, idx = (int)V.size()-1;
while(l<=r){
int m = (l+r)>>1;
for (int i=0;i<=m;i++) Place[W[i]] = 1;
for (int i=m+1;i<(int)V.size();i++) Place[W[i]] = 0;
if (ask(W[0], x)) idx = m, r = m-1;
else l = m+1;
}
answer(W[idx], x);
adj[W[idx]].push_back(x);
adj[x].push_back(W[idx]);
fill(Place, Place+1400, 0);
fill(visited, visited+1400, 0);
for (auto &v:V) Place[v] = 1;
Place[W[idx]] = 0;
vector<int> N;
for (auto &v:adj[W[idx]]) if (Place[v]) N.push_back(v);
vector<vector<int>> nxt_comp;
for (auto &nxt:N){
W.clear();
dfs(nxt);
if (!W.empty()) nxt_comp.push_back(W);
}
for (auto &nV:nxt_comp){
solve(nV, x);
}
}
void Detect(int T, int N) {
for (int i=1;i<N;i++) a[i] = i;
_sort(N);
C.push_back(0);
for (int i=1;i<N;i++){
solve(C, a[i]);
C.push_back(a[i]);
}
}
