#include "meeting.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rd(14685413);
vector<int> b[2009];
void solve(int rt,vector<int> vec){
b[rt].clear();
if(!vec.size()) return;
if(vec.size()==1){ Bridge(rt,vec[0]); return; }
random(vec.begin(),vec.end());
int nd=vec.back(); vec.pop_back();
vector<int> sta;
int v,w;
for(int i=0;i<vec.size();i++){
v=vec[i]; w=Query(rt,nd,v);
if(w==v){ sta.push_back(v); }
else{ b[w].push_back(v); }
}
int l,r,mid,re;
for(int i=1;i<sta.size();i++){
l=0,r=i-1,re=i;
while(l<=r){
mid=(l+r)/2;
if(Query(rt,sta[mid],sta[i])==sta[i]) re=mid,l=mid-1;
else r=mid+1;
}
for(int j=i;j>re;j--)
swap(sta[j],sta[j-1]);
}
for(int i=1;i<sta.size();i++)
Bridge(sta[i-1],sta[i]);
Bridge(rt,sta[0]); Bridge(sta.back(),nd);
for(int i=0;i<sta.size();i++)
Solve(sta[i],b[sta[i]]);
return;
}
void solve(int N){
int rt=rd()%N;
for(int i=0;i<N;i++)
if(i!=rt)
b[rt].push_back(i);
solve(rt,b[rt]);
return;
}