#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
void SolvePath(int root, int endpoint, vector<int> &path) { // sorting algorithm to solve path subproblem
stable_sort(begin(path), end(path), [&](int l, int r) {
if (l == root) return true;
if (l == endpoint) return false;
if (r == root) return false;
if (r == endpoint) return true;
return Query(root, l, r) == l; // l is the nearer one to root
});
for (int i = 1; i < (int) path.size(); i++) {
Bridge(min(path[i - 1], path[i]), max(path[i - 1], path[i]));
}
}
void SolveTree(int root, vector<int> &nodes) {
if (nodes.empty()) return;
shuffle(begin(nodes), end(nodes), rnd);
int endpoint = nodes.back();
nodes.pop_back();
map<int, vector<int>> S;
vector<int> path = {root, endpoint};
for (auto &v : nodes) {
int q = Query(root, endpoint, v);
if (v == q) {
path.emplace_back(v);
} else {
S[q].emplace_back(v);
}
}
nodes.clear();
nodes.shrink_to_fit();
SolvePath(root, endpoint, path);
for (auto &v : path) {
SolveTree(v, S[v]);
}
}
void Solve(int N) {
int root = rnd() % N;
vector<int> nodes;
for (int i = 0; i < N; i++) {
if (i == root) continue;
nodes.emplace_back(i);
}
return SolveTree(root, nodes);
}
