#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);
}