#include "park.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1400;
static int Place[1400];
int n;
bitset<N + 1> mark;
bool query(int u, int v) {
if (u > v)
swap(u, v);
for (int i = 0; i < n; i++)
Place[i] = mark[i];
return Ask(u, v, Place);
}
void write(int u, int v) {
//cout << u << ' ' << v << endl;
if (u > v)
swap(u, v);
Answer(u, v);
}
bool isAdj(int u, int v) {
mark.reset();
mark[u] = mark[v] = 1;
return query(u, v);
}
void solveSub1() {
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (isAdj(i, j))
write(i, j);
}
int cmpU, cmpV;
bool cmp(int u, int v) {
mark.set();
mark[v] = 0;
return query(cmpU, u);
}
void solveSub2() {
vector<int> vec;
for (int i = 1; i < n - 1; i++)
vec.push_back(i);
cmpU = 0;
cmpV = n - 1;
sort(vec.begin(), vec.end(), cmp);
if (vec.size()) {
write(0, vec[0]);
write(vec.back(), n - 1);
}
for (int i = 0; i + 1 < vec.size(); i++)
write(vec[i], vec[i + 1]);
}
mt19937 rng(123);
bool isMiddle(int u, int w, int v) {
mark.set();
mark[w] = 0;
return query(u, v) == false;
}
void solveTree(vector<int> vec) {
/*cout << "hi " << ": ";
for (auto x: vec)
cout << x << ' ';
cout << endl;*/
if (vec.size() <= 2) {
if (vec.size() == 2)
write(vec[0], vec[1]);
return;
}
int idx1 = rng() % (int) vec.size();
int idx2 = rng() % ((int) vec.size() - 1);
if (idx2 >= idx1)
idx2++;
int u = vec[idx1], v = vec[idx2];
vector<int> vecU = {u}, vecV = {v}, vecMid;
shuffle(vec.begin(), vec.end(), rng);
for (auto x: vec)
if (x != u && x != v) {
if (isMiddle(x, u, v))
vecU.push_back(x);
else if (isMiddle(x, v, u))
vecV.push_back(x);
else
vecMid.push_back(x);
}
if (vecMid.empty())
write(u, v);
else {
shuffle(vecMid.begin(), vecMid.end(), rng);
bool findU = false, findV = true;
for (auto x: vecMid) {
if (!findU && isAdj(x, u)) {
write(x, u);
findU = true;
}
if (!findV && isAdj(x, v)) {
write(x, v);
findV = true;
}
}
}
solveTree(vecU);
solveTree(vecV);
solveTree(vecMid);
}
void solveSubTree() {
vector<int> vec;
for (int i = 0; i < n; i++)
vec.push_back(i);
solveTree(vec);
}
void Detect(int T, int N) {
n = N;
if (T == 1)
solveSub1();
else if (T != 5)
solveSubTree();
}
