#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
const int N = 2005;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void cal(int root, vector<int> &cand) {
for (int i = 0; i < (int)cand.size(); i++) {
if (cand[i] == root) {
cand.erase(cand.begin() + i);
break;
}
}
if (cand.empty()) return;
shuffle(cand.begin(), cand.end(), rng);
vector<pii> vec;
vector<int> chain;
int u = cand[0];
chain.pb(u);
for (int i = 1; i < cand.size(); i++) {
int p = Query(root, u, cand[i]);
if (p == cand[i]) {
chain.pb(p);
}
else {
vec.pb({p, cand[i]});
}
}
sort(vec.begin(), vec.end());
for (int i = 0; i < (int)vec.size(); i++) {
vector<int> nxt;
int j = i;
nxt.pb(vec[i].F);
while(j < (int)vec.size() && vec[i].F == vec[j].F) {
nxt.pb(vec[j].S);
j++;
}
shuffle(nxt.begin(), nxt.end(), rng);
cal(nxt[0], nxt);
i = j - 1;
}
sort(chain.begin(), chain.end(), [&](const int &x, const int &y) {
return Query(root, x, y) == x;
});
for (int i = 0; i < (int)chain.size(); i++) {
int u = chain[i];
int v = (i == 0 ? root : chain[i - 1]);
if (u > v) swap(u, v);
Bridge(u, v);
}
}
void Solve(int n) {
vector<int> cand(n);
iota(cand.begin(), cand.end(), 0);
shuffle(cand.begin(), cand.end(), rng);
cal(cand[0], cand);
}
