#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#include "meetings.h"
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
int rint(int a,int b){
int ans=0;
ans=a+(rng()%(b-a+1));
return ans;
}
int n;
int root;
vector<int>v[2023];
int f(int left,vector<int>path){
if(path.size()==0)return left;
if(path.size()==1){
int x=*path.begin();
Bridge(min(x,left),max(x,left));
return x;
}
int x=path[rint(0,path.size()-1)];
vector<int>a,b;
for(int y:path){
if(x==y)continue;
int z=Query(left,x,y);
if(z==y)a.pb(y);
else b.pb(y);
}
int y=f(left,a);
Bridge(min(x,y),max(x,y));
y=f(x,b);
return y;
}
void dfs(int pos){
if(v[pos].size()==0)return;
if(v[pos].size()==1){
Bridge(min(pos,v[pos][0]),max(pos,v[pos][0]));
return;
}
int las=v[pos][rint(0,v[pos].size()-1)];
vector<int>can=v[pos];
v[pos].clear();
set<int>path={pos,las};
for(int x:can){
if(x==las)continue;
int ara=Query(pos,las,x);
path.insert(ara);
if(ara==x)continue;
v[ara].pb(x);
}
for(int x:path){
dfs(x);
}
path.erase(las);
path.erase(pos);
vector<int>v2;
for(int x:path){
v2.pb(x);
}
int x=f(pos,v2);
Bridge(min(x,las),max(x,las));
}
void Solve(int N){
n=N;
root=rint(0,n-1);
for(int i=0;i<n;i++){
if(i==root)continue;
v[root].pb(i);
}
dfs(root);
}
