#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
#define rand rd
long long Rand(long long l, long long h) {
assert(l <= h);
return l + rd() * 1LL * rd() % (h - l + 1);
}
void cen(vector <int> &cur){
int n = cur.size(); if (n == 1) return;
int root = cur[Rand(0, n - 1)];
vector <vector <int>> sub;
int sz = 0;
for (auto u : cur){
if (u == root) continue;
bool used = false;
for (int i = 0; i < sz; ++ i){
int par = sub[i][0];
int lca = Query(root, par, u);
if (lca == root) continue;
sub[i].push_back(u);
if (lca == u) swap(sub[i][sub[i].size() - 1], sub[i][0]);
used = true;
}
if (!used) {
sub.push_back({u});
++ sz;
}
}
for (int i = 0; i < sz; ++ i){
Bridge(root, sub[i][0]);
cen(sub[i]);
}
}
void Solve(int N){
vector <int> cur = {};
for (int i = 0; i < N; ++ i) cur.push_back(i);
cen(cur);
}
