#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define ins insert
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)
const int MOD = 1000000007;
const int mx = 2005;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
int N;
// set<int> below[mx];
// bool leaved[mx];
void bridge(int a, int b){
assert(a != b);
if(a > b) swap(a, b);
assert(0 <= a && b <= N-1);
//cout << a << " " << b << "\n";
Bridge(a, b);
}
int curR;
bool cmp(const int &a, const int &b){
int A = a;
int B = b;
if(Query(A, B, curR) == b) return 1;
return 0;
}
vi cSort(set<int> x){
vi v;
for(auto u: x){
v.pb(u);
}
sort(all(v), cmp);
return v;
}
void search(int R, vi nodes){
// cout << "search: " << R << ", ";
// for(auto u: nodes){
// cout << u << " ";
// }
// cout << "\n";
if(sz(nodes) == 0) return;
if(sz(nodes) == 1){
bridge(nodes[0], R);
return;
}
int cur = nodes[rng() % sz(nodes)];
//cout << "cur: " << cur << "\n";
map<int, vi> m;
set<int> path;
path.ins(R);
path.ins(cur);
for(auto u: nodes){
if(u == cur) continue;
int a = Query(R, cur, u);
path.ins(a);
if(a != u) m[a].pb(u);
}
curR = R;
// cout << "path: ";
// for(auto u: path) cout << u << " ";
// cout << "\n";
if(path.count(cur)) path.erase(cur);
if(path.count(R)) path.erase(R);
vi v = cSort(path); //lowest to highest in tree
vi newv;
newv.pb(cur);
for(auto u: v) newv.pb(u);
newv.pb(R);
swap(v, newv);
// cout << "v: ";
// for(auto u: v) cout << u << " ";
// cout << "\n";
for(int i = 0; i+1 < sz(v); i++){
bridge(v[i], v[i+1]);
}
for(auto u: m){
search(u.f, u.s);
}
}
void Solve(int _N) {
N = _N;
// for(int i = 1; i < N; i++){
// for(int j = i+1; j < N; j++){
// int a = Query(0, i, j);
// if(a != i) below[a].ins(i);
// if(a != j) below[a].ins(j);
// }
// }
// for(int i = 0; i < N-1; i++){
// //cout << "Phase " << i << "\n";
// int leaf;
// for(int j = 1; j < N; j++){
// if(leaved[j]) continue;
// if(sz(below[j]) == 0){
// leaf = j;
// break;
// }
// }
// //cout << leaf << "\n";
// leaved[leaf] = 1;
// pi cur = mp(MOD, -1);
// for(int j = 0; j < N; j++){
// if(leaved[j]) continue;
// if(below[j].count(leaf)) cur = min(cur, mp(sz(below[j]), j));
// }
// if(cur.s == -1) cur.s = 0;
// for(int j = 0; j < N; j++){
// if(below[j].count(leaf)) below[j].erase(leaf);
// }
// Bridge(min(leaf, cur.s), max(leaf, cur.s));
// }
vi init;
for(int i = 1; i < N; i++){
init.pb(i);
}
search(0, init);
}
