#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int N;
mt19937 gen(time(NULL));
int rand(int l, int r)
{
uniform_int_distribution<> dis(l, r);
return dis(gen);
}
void answer(int a, int b)
{
if(a>b) swap(a, b);
Bridge(a, b);
}
void solve(vector<int> cand)
{
if(cand.size()==1) return;
int i, j;
int u, v;
u=rand(0, cand.size()-1);
v=rand(0, cand.size()-1);
while(u==v) v=rand(0, cand.size()-1);
u=cand[u]; v=cand[v];
map<int, vector<int>> M;
vector<int> V;
M[u].push_back(u);
M[v].push_back(v);
//for(auto it : cand) printf("%d ", it); printf(" : %d %d\n", u, v);
for(auto now : cand)
{
if(now==u || now==v) continue;
int t=Query(u, v, now);
M[t].push_back(now);
if(t!=u && t!=v) V.push_back(t);
}
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
stable_sort(V.begin(), V.end(), [&](const int &p, const int &q)
{
return Query(u, p, q)==q;
});
V.insert(V.begin(), u);
V.push_back(v);
for(i=1; i<V.size(); i++) answer(V[i], V[i-1]);
for(auto it : M) solve(it.second);
}
void Solve(int _N)
{
int i, j;
N=_N;
vector<int> V;
for(i=0; i<N; i++) V.push_back(i);
solve(V);
}
