#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double dd;
typedef pair<ll , ll> ii;
typedef tuple < ll, ll, ll > tp;
#define ff first
#define ss second
#define pb push_back
#define in insert
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const ll N = 2005;
vector < ll > v[N];
void solve(vector < ll > a){
if(a.size() == 1) return;
if(a.size() == 2){
v[a[0]].pb(a[1]);
v[a[1]].pb(a[0]);
//cout << a[0] << ' ' << a[1] << " <- double" << '\n';
return;
}
ll n = a.size();
ll x = rng() % n, y = rng() % n;
while(x == y){
x = rng() % n;
y = rng() % n;
}
x = a[x];
y = a[y];
vector < ll > X, mid, Y;
for(auto u : a){
if(u - x && u - y){
ll z = Query(x, y, u);
if(z == x) X.pb(u);
if(z == y) Y.pb(u);
if(z != x && z != y) mid.pb(u);
}
}
shuffle(X.begin(), X.end(), rng);
shuffle(Y.begin(), Y.end(), rng);
// for x nodes
vector < vector < ll > > F;
for(auto u : X){
bool ok = 0;
for(ll i = 0; i < F.size(); i++){
if(Query(u, F[i][0], x) != x){
F[i].pb(u);
ok = 1;
break;
}
}
if(!ok){
F.pb({u});
}
}
F.pb(mid);
for(auto vec : F){
if(vec.size() == 0) continue;
solve(vec);
//cout << vec.size() << '\n';
vector < ll > potential_cands;
for(auto u : vec){
potential_cands.pb(u);
}
shuffle(potential_cands.begin(), potential_cands.end(), rng);
ll node = potential_cands[0];
for(ll i = 0; i < potential_cands.size(); i++){
if(node == potential_cands[i]) continue;
node = Query(potential_cands[i], node, x);
}
v[x].pb(node);
v[node].pb(x);
//cout << node << ' ' << x << " <- x" << '\n';
}
if(mid.size() == 0){
v[x].pb(y);
v[y].pb(x);
//cout << y << ' ' << x << " <- m" << '\n';
}
F.clear();
F.shrink_to_fit();
// for y nodes
for(auto u : Y){
bool ok = 0;
for(ll i = 0; i < F.size(); i++){
if(Query(u, F[i][0], y) != y){
F[i].pb(u);
ok = 1;
break;
}
}
if(!ok){
F.pb({u});
}
}
F.pb(mid);
for(auto vec : F){
if(vec.size() == 0) continue;
if(vec != mid) solve(vec);
vector < ll > potential_cands;
for(auto u : vec){
potential_cands.pb(u);
}
shuffle(potential_cands.begin(), potential_cands.end(), rng);
ll node = potential_cands[0];
for(ll i = 0; i < potential_cands.size(); i++){
if(node == potential_cands[i]) continue;
node = Query(potential_cands[i], node, y);
}
v[y].pb(node);
v[node].pb(y);
//cout << node << ' ' << y << " <- y" << '\n';
}
return;
}
void Solve(int n) {
vector < ll > a;
for(ll i = 0; i < n; i++) a.pb(i);
solve(a);
for(ll i = 0; i < n; i++){
for(auto u : v[i]){
if(u > i) Bridge(i, u);
}
}
return;
}
