#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
int crt;
bool cmp(int i, int j) {
return (Query(crt, i, j) == i);
}
void rec(int root, vector<int>& vec) {
if (vec.empty()) return;
crt = root;
map<int, vector<int>> newvec;
int v = vec[rand() % vec.size()];
vector<int> onpath = {root, v};
for (int u : vec) {
if (u != v) {
int q = Query(root, v, u);
if (q == u) {
onpath.push_back(u);
} else {
newvec[q].push_back(u);
}
}
}
sort(onpath.begin() + 1, onpath.end(), cmp);
for (int i = 1; i < (int) onpath.size(); ++i) {
int x = onpath[i - 1], y = onpath[i];
if (x > y) swap(x, y);
Bridge(x, y);
}
for (int u : onpath) {
rec(u, newvec[u]);
}
}
void Solve(int N) {
int root = rand() % N;
vector<int> vec;
for (int i = 0; i < N; ++i) {
if (i != root) {
vec.push_back(i);
}
}
rec(root, vec);
}
