#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int RAND(int l, int r, mt19937& rng) {
return uniform_int_distribution<int>(l, r)(rng);
}
void solve(vector<int>& v, mt19937& rng) {
if((int)v.size()<=1) return;
if((int)v.size()==2) {
//cerr<<"bridge: "<<v[0]<<' '<<v[1]<<'\n';
Bridge(min(v[0], v[1]), max(v[0], v[1]));
return;
}
int sz = v.size();
int v1 = RAND(0, sz-1, rng), v2 = RAND(0, sz-2, rng);
if(v2>=v1) v2++;
//cerr<<"solve [";
/*for(int i=0; i<sz; ++i) {
cerr<<v[i];
if(i<sz-1) cerr<<' ';
else cerr<<"] ";
}
cerr<<v[v1]<<' '<<v[v2]<<" "<<n<<'\n';
*/
vector<vector<int>> vec(n);
vec[v[v1]].push_back(v[v1]);
vec[v[v2]].push_back(v[v2]);
vector<int> path = {v[v1], v[v2]};
for(int i=0; i<sz; ++i) {
if(i == v1 || i==v2) continue;
int u = Query(v[v1], v[v2], v[i]);
//cerr<<v[i]<<": "<<u<<'\n';
if(u == v[i]) {
path.push_back(v[i]);
}
vec[u].push_back(v[i]);
}
if((int)path.size() == 3) {
//cerr<<"Bridge: "<<v[0]<<' '<<path[2]<<'\n';
//cerr<<"Bridge: "<<v[1]<<' '<<path[2]<<'\n';
Bridge(min(v[v1], path[2]), max(v[v1], path[2]));
Bridge(min(v[v2], path[2]), max(v[v2], path[2]));
}
else {
solve(path, rng);
}
for(int i=0; i<n; ++i) {
//cerr<<' '<<i<<" - "<<vec[i].size()<<'\n';
solve(vec[i], rng);
}
}
void Solve(int N) {
n = N;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> v;
for(int i=0; i<N; ++i) {
v.push_back(i);
}
solve(v, rng);
}
