#include "park.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
static int Place[1400];
const int mxN = 1405;
vector<int> solved, rem, stk, al[mxN];
int N, ban[mxN], vis[mxN];
void myans(int i, int j) {
//TRACE("ANSWER" _ i _ j);
if (i > j) swap(i,j);
al[i].push_back(j);
al[j].push_back(i);
Answer(i,j);
}
bool myask(int i, int j, vector<int> v) {
if (i > j) swap(i,j);
v.push_back(i);
v.push_back(j);
for (int& x : v) Place[x] = 1;
int ret = Ask(i,j,Place);
for (int& x : v) Place[x] = 0;
return ret;
}
void solveLine(int l, int r) {
//TRACE("LINE" _ l _ r);
vector<int> line;
line.push_back(l);
line.push_back(r);
while (l != r) {
int u = *(++find(ALL(line),l));
while (true) {
//TRACE("CHECK" _ l _ u);
if (myask(l,u,solved)) {
l = u;
break;
}
int lo = -1, hi = SZ(rem);
while (hi-lo > 1) {
int mid = (lo+hi)/2;
vector<int> v2(solved);
FOR(i,0,mid) v2.push_back(rem[i]);
if (myask(l,u,v2)) hi = mid;
else lo = mid;
}
u = rem[hi];
assert(find(ALL(rem),u) != rem.end());
rem.erase(find(ALL(rem),u));
line.insert(find(ALL(line),l)+1,u);
}
}
//cerr << "line: "; for (int& x : line) { cerr << x << ' '; } cerr << endl;
//cerr << "rem: "; for (int& x : rem) { cerr << x << ' '; } cerr << endl;
line.pop_back();
for (int& x : line) stk.push_back(x);
}
void dfs(int u, vector<int>& cc) {
vis[u] = 1; cc.push_back(u);
for (int& v : al[u]) if (!ban[v] && !vis[v]) dfs(v,cc);
}
void solveComp(int u, vector<int> cc) {
//TRACE("COMP" _ u _ SZ(cc));
//for (int& x : cc){ cout << x << ' '; } cout << endl;
int lo = -1, hi = SZ(cc);
while (hi-lo > 1) {
int mid = (lo+hi)/2;
vector<int> v2;
FOR(i,0,mid) v2.push_back(cc[i]);
if (myask(u,cc[0],v2)) hi = mid;
else lo = mid;
}
int v = cc[hi];
myans(u,v);
ban[v] = 1;
fill_n(vis,N,0);
vector<vector<int>> vcc;
for (int& x : cc) if (!ban[x] && !vis[x]) {
vector<int> comp; dfs(x,comp);
if (myask(u,comp[0],comp)) vcc.push_back(comp);
}
for (auto& comp : vcc) solveComp(u,comp);
}
void Detect(int T, int _N) {
N = _N;
solved.push_back(0);
FOR(i,1,N-1) rem.push_back(i);
while (SZ(solved) < N) {
if (!SZ(stk)) stk.push_back(rem.back()), rem.pop_back();
int u = stk.back(); stk.pop_back();
//TRACE("CHECK" _ u _ solved[0]);
//for (int& x : solved){ cout << x << ' '; } cout << endl;
if (!myask(u,solved[0],solved)) {
solveLine(u,solved[0]);
} else {
fill_n(ban,N,0);
solveComp(u,solved);
solved.push_back(u);
}
//TRACE("OK");
}
}
