#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void Ans(int a, int b) {
if (a > b) swap(a, b);
Bridge(a, b);
}
void Solve(vector<int> v) {
if ((int)v.size() <= 2) {
Ans(v[0], v[1]);
return;
}
shuffle(v.begin(), v.end(), rng);
vector<int> path;
map<int, vector<int>> subtree;
int root = v[0];
int aux = v[1];
for (int i = 2; i < (int)v.size(); ++i) {
int ans = Query(root, aux, v[i]);
if (ans == v[i]) {
path.emplace_back(v[i]);
} else {
subtree[ans].emplace_back(v[i]);
}
}
sort(path.begin(), path.end(), [&](int a, int b) {
return Query(root, a, b) == a;
});
if (!path.empty()) {
Ans(root, path[0]);
for (int i = 0; i + 1 < (int)path.size(); ++i) {
Ans(path[i], path[i + 1]);
}
Ans(path.back(), aux);
} else {
Ans(root, aux);
}
for (auto p : subtree) {
p.second.emplace_back(p.first);
Solve(p.second);
}
}
void Solve(int n) {
vector<int> v(n);
iota(v.begin(), v.end(), 0);
Solve(v);
}
