#include "meetings.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,inline,unroll-loops")
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define per(a,b,c) for(ll a=b;a>=c;--a)
#define ll long long
#define ff first
#define ss second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
static mt19937 rng((ll)time(nullptr));
const ll N=2005,inf=1e18;
ll n;
void bridge(ll u,ll v){
if(u>v) swap(u,v);
Bridge(u,v);
}
void DC(ll root,vector<ll> &T){
if(T.empty()) return ;
if(T.size()==1) return bridge(root,T[0]),void();
vector<ll> sub[20];
ll ptr=0;
sub[0].push_back(T.back());
T.pop_back();
while(!T.empty()){
ll u=T.back();T.pop_back();
bool ok=false;
rep(i,0,ptr){
ll res=Query(root,sub[i].back(),u);
if(res!=root){
ok=true;
sub[i].push_back(u);
break;
}
}
if(!ok){
ptr++;
sub[ptr].push_back(u);
}
}
vector<ll>().swap(T);
rep(i,0,ptr){
ll nr=0,Nr;
rep(j,1,(ll)sub[i].size()-1){
ll u=sub[i][j];
ll res=Query(root,sub[i][nr],u);
if(res!=sub[i][nr]) nr=j;
}
Nr=sub[i][nr];
bridge(root,Nr);
sub[i].erase(sub[i].begin()+nr);
DC(Nr,sub[i]);
}
}
void Solve(int NN){
n=NN;
vector<ll> T;
ll root=rng()%n;
rep(i,0,n-1) if(i!=root) T.push_back(i);
DC(root,T);
}
