#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;
}
int h[N + 10], col[N + 10];
vector<int> vec[N + 10], adj[N + 10];
int sel(vector<int> vec, int u) {
if (vec.size() == 1)
return vec[0];
int mid = (int) vec.size() / 2;
vector<int> vecL, vecR;
for (int i = 0; i < (int) vec.size(); i++)
if (i < mid)
vecL.push_back(vec[i]);
else
vecR.push_back(vec[i]);
mark.set();
for (auto x: vecL)
mark[x] = 0;
if (query(0, u))
return sel(vecR, u);
return sel(vecL, u);
}
void solveSub3() {
h[0] = 1;
col[0] = true;
for (int hi = 2; hi <= 9; hi++) {
for (int i = 0; i < n; i++)
mark[i] = col[i];
for (int i = 0; i < n; i++)
if (!col[i]) {
mark[i] = 1;
if (query(0, i)) {
h[i] = hi;
col[i] = true;
vec[hi].push_back(i);
//cout << i << " -> " << hi << endl;
}
mark[i] = 0;
}
}
for (int i = 0; i < n; i++)
if (!col[i]) {
h[i] = 10;
vec[10].push_back(i);
}
for (int hi = 2; hi <= 10; hi++)
for (auto u: vec[hi]) {
//cout << hi << ": " << u << endl;
int pnt = 0;
for (int tmp = 1; tmp != hi - 1; tmp++)
pnt = sel(adj[pnt], u);
//cout << pnt << endl;
write(u, pnt);
adj[pnt].push_back(u);
//cout << hi << endl;
}
}
void Detect(int T, int N) {
n = N;
if (T == 1)
solveSub1();
else if (T == 2)
solveSub2();
else if (T == 3)
solveSub3();
}
