#include "meetings.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_shuffle(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;
}