#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define eb emplace_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 2e3 + 5, MAXN = 1e7 + 5;
const long long oo = 1e9 + 7, mod = 1e9 + 7;
vector<int> vis[N];
int sz[N];
//vector<ii> bridge;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
temp = (temp + (r - l + 1)) % (r - l + 1);
return temp + l;
}
int query(int a, int b, int c){
//cout << a << " " << b << " " << c << "\n";
return Query(a - 1, b - 1, c - 1) + 1;
}
void bridge(int a, int b){
Bridge(min(a, b) - 1, max(a, b) - 1);
}
void solve(vector<int> x){
if(x.size() <= 1) return;
if(x.size() == 2){
bridge(x[0], x[1]);
return;
}
int temp = rnd(1, x.size() - 1);
int node = x[temp];
int node2 = x[0];
//cout << temp << " " << node << " " << node2 << "\n";
//assert(node != node2);
for(auto it : x){
if(it == node || it == node2) continue;
int temp = query(node, node2, it);
if(temp == node) continue;
node2 = temp;
}
//cout << node << " " << node2 << "\n";
bridge(node, node2);
vector<int> x1, x2;
x1.pb(node), x2.pb(node2);
for(auto it : x){
if(it == node || it == node2) continue;
int temp = query(node, node2, it);
assert(temp == node || temp == node2);
if(temp == node) x1.pb(it);
else x2.pb(it);
}
solve(x1), solve(x2);
}
void Solve(int n){
vector<int> str;
for(int i = 1; i <= n; i++) str.pb(i);
solve(str);
}
/*
5
0 1
0 2
1 3
1 4
*/
