#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MXN = 2005;
int n, root;
vector<int> subt[MXN];
set<int> st;
bool cmp(int u, int v){
return (Query(root, u, v) == u);
}
void get(int v){
int u = subt[v][rng() % subt[v].size()];
vector<int> path, cur_subt = subt[v];
subt[v].clear();
st.erase(v);
for (int x : cur_subt){
if (x == u) continue;
int cen = Query(u, x, v);
if (cen == x)
path.push_back(x);
else{
subt[cen].push_back(x);
st.insert(cen);
}
}
root = v;
sort(path.begin(), path.end(), cmp);
path.push_back(u);
for (int i = 0; i < path.size(); i ++){
if (root < path[i]) Bridge(root, path[i]);
else Bridge(path[i], root);
root = path[i];
}
}
void Solve(int nn) {
srand(time(0));
n = nn;
for (int i = 1; i < n; i ++)
subt[0].push_back(i);
st.insert(0);
while (!st.empty()){
int v = *st.begin();
get(v);
}
}
