#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];
int gl[MAXN];
int spytaj(int a, int b, int* T){
if(a > b) swap(a, b);
return Ask(a, b, T);
}
void sciezka(int a, int b){
int pusta[n];
for(int i = 0; i < n; ++i){
pusta[i] = 0;
}
// cout << a << " " << b << " XD\n";
if(lft.find(b) != lft.end()) lft.erase(b);
pusta[a] = 1;
pusta[b] = 1;
if(spytaj(a, b, pusta)){
// cout << a << " " << b << " kr\n";
ans.push_back({min(a,b), max(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 = spytaj(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;
gl[u] = gl[v] + 1;
dfs(u, v);
sajz[v] += sajz[u];
}
return;
}
int sajz2[MAXN];
int parent2[MAXN];
void dfs3(int v, int p){
sajz2[v] = 1;
parent2[v] = p;
for(auto u : graf[v]){
if(u == p or ison[u] == 0) continue;
dfs3(u, v);
sajz2[v] += sajz2[u];
}
return;
}
vi pod;
void dfs2(int v, int p){
pod.push_back(v);
// cout << v << " " << p << " vp\n";
for(auto u : graf[v]){
// cout << v << " " << u << " " << ison[u] << " u\n";
if(u == p or ison[u] == 0) continue;
dfs2(u, v);
}
return;
}
void znajdz(int V, vi K){
// cout << V << " V\n";
// for(auto u : K){
// cout << u << " ";
// }
// cout << "K\n";
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];
for(int i = 0; i < n; ++i){
pusta[i] = 0;
}
pusta[V] = 1;
for(auto u : lft){
pusta[u] = 1;
}
for(auto u : pod){
// cout << u << " ";
pusta[u] = 1;
}
// cout << "PODDDD\n";
// for(auto u : pusta){
// cout << u << " ";
// }
// cout << "PUSTA\n";
// cout << x << " " << V << " ABBBB\n";
int w = spytaj(x, V, pusta);
// cout << w << " W\n";
vi nw;
if(w){
nw = pod;
pod.clear();
dfs2(parent[x], x);
for(auto u : pod){
ison[u] = 0;
}
}
else{
for(auto u : pod){
ison[u] = 0;
}
pod.clear();
dfs2(parent[x], x);
nw = pod;
}
for(auto u : K){
sajz[u] = 0;
parent[u] = 0;
}
znajdz(V, nw);
return;
}
void znajdz2(int V, vi K){
int pusta[n];
for(int i = 0; i < n; ++i){
pusta[i] = 0;
}
for(auto u : K){
pusta[u] = 1;
}
pusta[V] = 1;
int w = spytaj(V, K[0], pusta);
for(auto u : K){
pusta[u] = 0;
}
if(w == 0) return;
if(K.size() == 1){
ans.push_back({min(V, K[0]), max(V, K[0])});
return;
}
for(auto u : K){
ison[u] = 1;
}
dfs3(K[0], -1);
int mid = K.size() / 2;
ll roz = INF;
int x = -1;
for(auto u : K){
ll tmp = abs(mid - sajz2[u]);
if(tmp < roz){
roz = tmp;
x = u;
}
}
pod.clear();
dfs2(x, parent2[x]);
vi p1 = pod;
pod.clear();
dfs2(parent2[x], x);
vi p2 = pod;
// for(auto u : p2){
// cout << u << " ";
// }
// cout << "P1\n";
for(auto u : K){
ison[u] = 0;
}
for(auto u : p1){
pusta[u] = 1;
}
w = spytaj(V, p1[0], pusta);
for(auto u : p1){
pusta[u] = 0;
}
if(w){
znajdz2(V, p1);
}
for(auto u : p2){
pusta[u] = 1;
}
w = spytaj(V, p2[0], pusta);
for(auto u : p2){
pusta[u] = 0;
}
if(w){
znajdz2(V, p2);
}
return;
}
void Detect(int T, int N) {
n = N;
for(int i = 0; i < n; ++i){
P.push_back(i);
lft.insert(i);
}
mt19937 rng(T * 69 + rand() % 10000);
shuffle(all(P), rng);
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]);
// cout << P[0] << " " << P[1] << " sciezka\n";
continue;
}
// cout << i+1 << " " << znal.size() << " ktory\n";
if(lft.find(P[i+1]) == lft.end()) continue;
// cout << P[i+1] << " nowy\n";
lft.erase(P[i+1]);
znajdz(P[i+1], znal);
if(P[i+1] == 6) break;
}
for(int i = 0; i < n; ++i){
ison[i] = 1;
}
gl[0] = 0;
dfs(0, -1);
int pusta[n];
for(int i = 0; i < n; ++i){
pusta[i] = 0;
}
for(int i = 0; i < n; ++i){
ison[i] = 0;
// cout << i << " " << parent[i] << " P\n";
}
for(int i = 0; i < n; ++i){
vi prv;
for(auto u : graf[i]){
// if(u == parent[i]) continue;
for(auto t : prv){
pusta[u] = 1;
pusta[t] = 1;
if(spytaj(u, t, pusta)){
ans.push_back({min(u,t), max(u, t)});
}
pusta[u] = 0;
pusta[t] = 0;
}
prv.push_back(u);
}
}
for(int i = 0; i < n; ++i){
if(gl[i] <= 1) continue;
pod.clear();
for(int j = 0; j < n; ++j){
ison[j] = 1;
}
dfs2(parent[parent[i]], parent[i]);
for(int j = 0; j < n; ++j){
ison[j] = 0;
}
vi K = pod;
pod.clear();
znajdz2(i, K);
}
set<pii> tmp;
for(auto u : ans){
tmp.insert(u);
}
for(auto u: tmp){
// cout << u.first << " " << u.second << " U\n";
Answer(u.first, u.second);
}
return;
}
