#include "park.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pii pair<int,int>
#define vii vector<pair<int,int>>
#define vi vector<int>
#define pll pair<ll, ll>
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define count_bits(x) __builtin_popcountll((x))
const ll M = 1e9+7;
const ll INF = 1e9;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int MAXN = 1405;
vii ans;
int n;
vi P;
set<int> lft;
vi znal;
int ison[MAXN];
vi graf[MAXN];
int sajz[MAXN];
int parent[MAXN];
void sciezka(int a, int b){
int pusta[n];
for(int i = 0; i < n; ++i){
pusta[i] = 0;
}
lft.erase(b);
// cout << a << " " << b << " nowa\n";
pusta[a] = 1;
pusta[b] = 1;
if(Ask(a, b, pusta)){
ans.push_back({a, b});
graf[a].push_back(b);
graf[b].push_back(a);
znal.push_back(b);
return;
}
vi subs;
for(auto u : lft){
subs.push_back(u);
}
vi def;
while(subs.size() > 1){
// cout << subs.size() << " S\n";
int pol = siz(subs) / 2;
vi tmp;
for(int i = 0; i < pol; ++i){
pusta[subs[i]] = 1;
tmp.push_back(subs[i]);
}
int v = Ask(a, b, pusta);
for(int i = 0; i < pol; ++i){
pusta[subs[i]] = 0;
}
if(v){
subs = tmp;
}
else{
for(auto u : tmp){
pusta[u] = 1;
def.push_back(u);
}
tmp.clear();
for(int i = pol; i < siz(subs); ++i){
tmp.push_back(subs[i]);
}
subs = tmp;
}
}
sciezka(a, subs[0]);
sciezka(subs[0], b);
return;
}
void dfs(int v, int p){
sajz[v] = 1;
parent[v] = p;
for(auto u : graf[v]){
if(u == p or ison[u] == 0) continue;
dfs(u, v);
sajz[v] += sajz[u];
}
return;
}
vi pod;
void dfs2(int v, int p){
pod.push_back(v);
for(auto u : graf[v]){
if(u == p or ison[u] == 0) continue;
dfs2(u, v);
}
return;
}
void znajdz(int V, vi K){
if(K.size() == 1){
sciezka(K[0], V);
return;
}
for(auto u : K){
ison[u] = 1;
}
dfs(K[0], -1);
int mid = K.size() / 2;
ll roz = INF;
int x = -1;
for(auto u : K){
ll tmp = abs(mid - sajz[u]);
if(tmp < roz){
roz = tmp;
x = u;
}
}
pod.clear();
dfs2(x, parent[x]);
int pusta[n];
pusta[V] = 1;
for(int i = 0; i < n; ++i){
pusta[i] = 0;
}
for(auto u : lft){
pusta[u] = 1;
}
for(auto u : pod){
pusta[u] = 1;
}
int w = Ask(x, V, pusta);
vi nw;
if(w){
nw = pod;
}
else{
pod.clear();
dfs2(parent[x], x);
nw = pod;
}
for(auto u : K){
sajz[u] = 0;
parent[u] = 0;
}
znajdz(V, pod);
return;
}
void Detect(int T, int N) {
n = N;
if(T == 1 or T == 5) return;
for(int i = 0; i < n; ++i){
P.push_back(i);
lft.insert(i);
}
mt19937 rng(T * 69 + rand() % 10000);
shuffle(all(P), rng);
lft.erase(0);
lft.erase(n-1);
znal.push_back(0);
sciezka(0, n-1);
// for(int i = 0; i < n-1; ++i){
// if(i == 0){
// lft.erase(P[0]);
// lft.erase(P[1]);
// znal.push_back(P[0]);
// sciezka(P[0], P[1]);
// continue;
// }
// lft.erase(P[i+1]);
// znajdz(P[i+1], znal);
// }
for(auto u: ans){
Answer(u.first, u.second);
}
return;
}
