#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
vector<vector<int>> stuff;
void calc(vector<int> v){
if((int)v.size()==1) return;
int n = v.size();
shuffle(v.begin(), v.end(), rng);
int a = v[0], b = v[1];
vector<int> path = {a, b};
for(int i = 2; i<n; ++i)
if(Query(a, b, v[i])==v[i])
path.push_back(v[i]);
sort(path.begin(), path.end(), [&](int x, int y){
if(a==x) return true;
if(a==y) return false;
return Query(a, x, y)==x;
});
for(int i = 0; i<(int)path.size()-1; ++i)
Bridge(min(path[i], path[i+1]), max(path[i], path[i+1]));
for(auto x : path)
stuff[x].clear();
stuff[a] = {a}; stuff[b] = {b};
for(int i = 2; i<n; ++i)
stuff[Query(a, b, v[i])].push_back(v[i]);
for(auto x : path)
calc(stuff[x]);
}
void Solve(int n){
vector<int> v(n);
iota(v.begin(), v.end(), 0);
stuff.resize(n); calc(v);
}
