#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int random(int l, int r) {
return uniform_int_distribution <int> (l, r)(rng);
}
vector <pair <int, int>> res;
void dnc(vector <int> node) {
if (node.size() == 1) return;
if (node.size() == 2) {
res.emplace_back(node[0], node[1]);
// cerr << "Path " << node[0] << ' ' << node[1] << endl;
return;
}
int l = random(0, node.size() - 2), r = random(l + 1, node.size() - 1);
int u = node[l], v = node[r];
// cerr << "Path " << u << ' ' << v << endl;
vector <int> path, ask(node.size());
for (int i = 0; i < node.size(); i++) if (i != l && i != r) {
int w = node[i]; ask[i] = Query(u, v, w);
if (ask[i] != u && ask[i] != v) path.emplace_back(ask[i]);
}
sort (path.begin(), path.end());
path.resize(unique(path.begin(), path.end()) - path.begin());
sort (path.begin(), path.end(), [&] (int x, int y) {
return Query(u, x, y) == x;
});
path.emplace_back(v);
for (int i = 0; i < path.size(); i++) {
if (i == 0) res.emplace_back(u, path[i]);
else res.emplace_back(path[i - 1], path[i]);
}
path.emplace_back(u); sort (path.begin(), path.end());
vector <vector <int>> group(path.size() + 1);
for (int i = 0; i < node.size(); i++) {
if (i == l) ask[i] = u;
if (i == r) ask[i] = v;
int id = lower_bound(path.begin(), path.end(), ask[i]) - path.begin();
group[id].emplace_back(node[i]);
}
for (int i = 0; i < path.size(); i++)
dnc(group[i]);
}
void Solve(int n) {
vector <int> init(n);
iota(init.begin(), init.end(), 0);
res.clear(); dnc(init);
for (auto &[u, v]: res) {
if (u > v) swap(u, v);
Bridge(u, v);
}
}
