#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 2005;
vector<int> g[maxn];
int cur_anc[maxn];
int n;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void calc(int root, int prev, vector<int> &cand) {
for (int i = 0; i < (int)cand.size(); ++i) {
if (cand[i] == root) {
cand.erase(cand.begin() + i);
break;
}
}
// debug(root, cand);
if (cand.empty()) return;
shuffle(cand.begin(), cand.end(), rng);
vector<pair<int, int>> subtree;
vector<int> chain;
int x = cand[0];
for (int i = 1; i < (int)cand.size(); ++i) {
int p = Query(root, x, cand[i]);
if (p == cand[i]) {
chain.push_back(p);
} else {
subtree.emplace_back(p, cand[i]);
}
}
sort(subtree.begin(), subtree.end());
for (int i = 0; i < (int)subtree.size(); ++i) {
vector<int> niu;
int cur = 0;
while (i + cur < (int)subtree.size() and subtree[i].first == subtree[i + cur].first) {
niu.push_back(subtree[i + cur].second);
++cur;
}
niu.push_back(subtree[i].first);
shuffle(niu.begin(), niu.end(), rng);
calc(niu[0], root, niu);
i = i + cur - 1;
}
sort(chain.begin(), chain.end());
chain.erase(unique(chain.begin(), chain.end()), chain.end());
sort(chain.begin(), chain.end(), [&](const int &x, const int &y) -> bool {
return Query(root, x, y) == x;
});
chain.push_back(x);
for (int i = 0; i < (int)chain.size(); ++i) {
int u = chain[i], v = (i == 0 ? root : chain[i - 1]);
if (u > v) swap(u, v);
Bridge(u, v);
}
}
void Solve(int N) {
n = N;
vector<int> cand;
for (int i = 0; i < n; ++i) {
cand.push_back(i);
}
calc(0, -1, cand);
}
