#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
#include "park.h"
const int N = 1505;
int place[N];
bool vis[N], blk[N];
int n;
vector<int> tree[N];
int check (int S, int E, vector<int> &O) {
for(int i = 0; i < n; i++) place[i] = 0;
for(auto &T : O) place[T] = 1;
place[S] = 1;
place[E] = 1;
return Ask(min(S, E), max(S, E), place);
}
int Find (int A, int B, vector<int> &O) {
int S = 0, E = O.size();
while(S < E) {
int M = (S + E) / 2;
vector<int> V;
for(int i = 0; i < M; i++) {
V.push_back(O[i]);
}
check(A, B, V) ? E = M : S = M + 1;
}
return (S ? O[S - 1] : A);
}
void preorder (int C, int P, vector<int> &O) {
O.push_back(C);
for(auto &T : tree[C]) {
if(T == P || blk[T]) continue;
preorder(T, C, O);
}
}
void construct (int S, int E, vector<int> &O) {
vis[E] = true;
int M = Find(S, E, O);
if(M == S) {
tree[S].push_back(E);
tree[E].push_back(S);
Answer(min(S, E), max(S, E));
} else {
construct(S, M, O);
construct(M, E, O);
}
}
void Try (int P, int I) {
vector<int> V;
preorder(I, -1, V);
if(!check(I, P, V)) return;
int J = Find(I, P, V);
Answer(min(P, J), max(P, J));
blk[J] = true;
for(auto &T : tree[J]) {
if(!blk[T]) Try(P, T);
}
}
void Detect (int T, int N) {
n = N;
for(int i = 1; i < n; i++) {
if(vis[i]) continue;
vector<int> V;
for(int j = 1; j < n; j++) {
if(tree[j].empty()) V.push_back(j);
}
preorder(0, -1, V);
int M = Find(0, i, V);
if(tree[M].empty()) M = 0;
V.clear();
for(int j = 1; j < n; j++) {
if(tree[j].empty()) V.push_back(j);
}
construct(M, i, V);
}
vector<int> X;
preorder(0, -1, X);
for(int i = (int)X.size() - 1; i > 0; i--) {
for(int j = 0; j < X.size(); j++) {
blk[X[j]] = (j >= i);
}
int I;
for(auto &T : tree[X[i]]) {
if(!blk[T]) {
I = T;
break;
}
}
blk[I] = true;
for(auto &T : tree[I]) {
if(!blk[T]) Try(X[i], T);
}
}
}
