#include <bits/stdc++.h>
#include "meetings.h"
//~ #include "grader.cpp"
using namespace std;
const int maxn = 2001;
int n, dep[maxn];
vector <int> p, pans, v[maxn];
int asked = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void dfsz(int node){
for(auto &i : v[node]){
dep[i] = dep[node] + 1;
dfsz(i);
}
}
int LCA(int a, int b){
if(a == b) return a;
if(a == 0 || b == 0) return 0;
return Query(0, a, b);
}
void solve(vector <int> a){
if(a.size() <= 1) return;
shuffle(a.begin(), a.end(), rng);
int leaf = -1;
for(auto &i : a){
leaf = i;
break;
}
if(leaf == -1) return;
vector <int> q(n + 1);
vector <int> anc;
for(auto &i : a){
q[i] = LCA(i, leaf);
anc.push_back(q[i]);
}
sort(anc.begin(), anc.end());
anc.resize(unique(anc.begin(), anc.end()) - anc.begin());
sort(anc.begin(), anc.end(), [&](int a, int b){
return LCA(a, b) == a;
});
for(int i = 1 ; i < (int)anc.size() ; i++)
pans[anc[i]] = anc[i - 1];
for(auto &i : anc){
vector <int> c;
for(auto &j : a){
if(q[j] == i && i != j){
c.push_back(j);
pans[j] = i;
}
}
solve(c);
}
}
void bridge(int a, int b){
if(b < a) swap(a, b);
Bridge(a, b);
}
void go(){
asked = 0;
for(int i = 0 ; i < n ; i++){
v[i].clear();
}
p.assign(n + 1, -1);
int root = -1;
for(int i = 0 ; i < n ; i++){
if(p[i] == -1) root = i;
else v[p[i]].push_back(i);
}
dfsz(root);
pans.assign(n + 1, -1);
vector <int> all;
for(int i = 0 ; i < n ; i++){
all.push_back(i);
}
solve(all);
for(int i = 1 ; i < n ; i++){
bridge(i, pans[i]);
}
}
void Solve(int N) {
n = N;
go();
}
