#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
//helper functions
#define sz(v) int(v.size())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r){
return uniform_int_distribution<int>(l, r)(rng);
}
int qry(int a, int b, int c) {
// cerr << "qry: " << a << ' ' << b << ' ' << c << endl;
assert(a != b && b != c && a != c);
return Query(a, b, c);
}
void upd(int a, int b) {
if (a >= b) swap(a, b);
// cerr << "upd: " << a << ' ' << b << endl;
Bridge(a, b);
}
//end helper functions
int n;
void rec(int root, vector<int> cand) {
if (sz(cand) == 0) return;
if (sz(cand) == 1) {
upd(root, cand[0]);
return;
}
int m = sz(cand);
int end = cand[rnd(0, m-1)];
// cerr << "root, end: " << root << ' ' << end << endl;
vector<int> repr(m), path;
for (int i = 0; i < m; i++) {
repr[i] = cand[i] == end ? end : qry(root, end, cand[i]);
if (repr[i] == cand[i] && cand[i] != end) { //on path
path.push_back(cand[i]);
}
}
sort(path.begin(), path.end(), [&](int a, int b){
return qry(root, a, b) == a;
});
path.insert(path.begin(), root);
path.push_back(end);
// cerr << "path: "; for (auto v : path) cerr << v << ' '; cerr << endl;
for (int i = 1; i < sz(path); i++)
upd(path[i-1], path[i]);
map<int, int> loc;
for (int i = 0; i < sz(path); i++) loc[path[i]] = i;
vector<vector<int>> nxt(sz(path));
for (int i = 0; i < m; i++) {
if (repr[i] != cand[i]) {
nxt[loc[repr[i]]].push_back(cand[i]);
}
}
for (int i = 0; i < sz(nxt); i++) {
rec(path[i], nxt[i]);
}
}
void Solve(int _n) {
n = _n;
vector<int> al(n); iota(al.begin(), al.end(), 0);
int root = rnd(0, n-1);
// cerr << root << endl;
al.erase(find(al.begin(), al.end(), root));
rec(root, al);
}
