#include <bits/stdc++.h>
#include "meetings.h"
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
int rand(int l , int r)
{
return uniform_int_distribution<int>(l , r)(rng) ;
}
const int MAX = 2004 ;
int n ;
vector< pair<int , int> >ans ;
int mark[MAX] ;
void solve(int root , vector<int>v)
{
if(!v.size())
return ;
shuffle(v.begin() , v.end() , rng) ;
for(auto &node : v)
mark[node] = 0 ;
vector< vector<int> >subtrees = {{v.back()}} ;
v.pop_back() ;
for(auto &node : v)
{
if(mark[node])
continue ;
shuffle(subtrees.begin() , subtrees.end() , rng) ;
mark[node] = 1 ;
bool flag = false ;
for(auto &v2 : subtrees)
{
int lca = Query(root , node , v2.back()) ;
if(lca == root)
continue ;
flag = true , mark[lca] = 1 ;
v2.push_back(node) ;
int sz = v2.size() ;
if(lca != v2[sz-1])
swap(v2[sz-1] , v2[sz-2]) ;
if(lca != v2[sz-1])
v2.push_back(lca) ;
break ;
}
if(!flag)
subtrees.push_back({node}) ;
}
for(auto &v2 : subtrees)
{
int root2 = v2.back() ;
ans.emplace_back(min(root , root2) , max(root , root2)) ;
v2.pop_back() ;
solve(root2 , v2) ;
}
}
void Solve(int N)
{
n = N ;
int root = rand(0 , n-1) ;
vector<int>v ;
for(int i = 0 ; i < n ; ++i)
{
if(i != root)
v.push_back(i) ;
}
solve(root , v) ;
for(auto &p : ans)
Bridge(p.first , p.second) ;
}
