#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
mt19937_64 rn(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rn(4);
void answer(int a, int b) {
Bridge(min(a, b), max(a, b));
}
int n;
void go(int l, int r, vector<int> b, vector<int> &pt) {
if (b.size() == 0) {
pt.push_back(r);
return;
}
if (b.size() == 1) {
pt.push_back(b[0]);
pt.push_back(r);
return;
}
shuffle(b.begin(), b.end(), rn);
int v = b.back();
b.pop_back();
vector<int> L, R;
for (auto x: b) {
if (Query(l, x, v) == x) L.push_back(x);
else R.push_back(x);
}
go(l, v, L, pt);
go(v, r, R, pt);
}
void go(int v, vector<int> a) {
shuffle(a.begin(), a.end(), rn);
int u = a.back();
a.pop_back();
vector<int> pt{v};
vector<int> b;
map<int, vector<int>> ma;
for (auto x: a) {
int w = Query(v, x, u);
if (w == x) b.push_back(x);
else ma[w].push_back(x);
}
for (auto x: b) a.erase(find(a.begin(), a.end(), x));
go(v, u, b, pt);
for (int i = 1; i < pt.size(); i++) answer(pt[i - 1], pt[i]);
for (auto [w, c]: ma) go(w, c);
}
void Solve(int _n) {
n = _n;
vector<int> a(n);
iota(a.begin(), a.end(), 0);
shuffle(a.begin(), a.end(), rn);
int v = a.back();
a.pop_back();
go(v, a);
}
