#include "meetings.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int gn(int a, int b) {
uniform_int_distribution<> dist(a,b);
return dist(rng);
}
int n;
int query(int a, int b, int c) {
if(a==b) return a;
if(b==c) return b;
if(a==c) return a;
return Query(a,b,c);
}
void bridge(int a, int b){
if(a>b)swap(a,b);
Bridge(a,b);
}
int mR;
bool comp(int a, int b) {
if(query(mR, a, b)==a) return 1;
return 0;
}
void rek(int root, vector<int> S) {
if(S.size()==1) return;
int v = S[gn(0, S.size()-1)];
vector<vector<int>> res(n);
vector<int> P;
for(auto u : S) {
int q = query(root, v, u);
if(q==u) P.push_back(u);
res[q].push_back(u);
}
mR = root;
sort(P.begin(), P.end(), comp);
for(int i=0; i<P.size()-1; ++i) bridge(P[i], P[i+1]);
for(auto x : P) rek(x, res[x]);
}
void Solve(int N) {
n=N;
vector<int> p;
for(int i=0; i<N; ++i) p.push_back(i);
int R = p[gn(0,N-1)];
rek(R, p);
}
