#include"meetings.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(67);
vector<pair<int,int>> odp;
void guess(vector<int> &ind) {
vector<int> L,R; int n = ind.size();
if (n == 1)
return;
if (n == 2)
odp.push_back({ind[0],ind[1]});
else if (n == 3) {
int ans = Query(ind[0],ind[1],ind[2]);
for (int i = 0; i < 3; i++)
if (ind[i] != ans)
odp.push_back({ans,ind[i]});
}
else {
shuffle(ind.begin(),ind.end(),rnd);
int r = ind.back(); ind.pop_back(), L.push_back(r);
int x = ind.back(); ind.pop_back(), R.push_back(x);
while (!ind.empty()) {
int y = ind.back(); ind.pop_back();
int ans = Query(r,x,y);
if (ans == r)
L.push_back(y);
else if (ans == x)
R.push_back(y);
else
x = y, R.push_back(y);
}
guess(L), guess(R);
}
}
void Solve(int n) {
vector<int> ind;
for (int i = 0; i < n; i++)
ind.push_back(i);
guess(ind);
for (auto [x,y] : odp)
Bridge(min(x,y),max(x,y));
}
