#include "meetings.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353
#define POT 4194304
#define INF 1000000019
#define INFL 1000000000000000099LL
random_device rd;
mt19937 g(rd());
vector<ll>dzieci[2007];
ll sz[2007];
void Solve(int n){
vector<ll>dodod;
for(ll i=1;i<n;i++){
dodod.pb(i);
}
shuffle(dodod.begin(),dodod.end(),rd);
sz[0]=1;
while(dodod.size()){
ll pom=dodod.back();
dodod.pop_back();
if(sz[pom]){
// /ak=2006;
continue;
}
ll ak=0;
sz[ak]++;
vector<ll>odw;
while(dzieci[ak].size()){
vector<pair<ll,ll>>v;
for(ll i=0;i<dzieci[ak].size();i++){
v.pb({sz[dzieci[ak][i]],dzieci[ak][i]});
}
sort(v.begin(),v.end());
for(ll j=0;j<=v.size();j++){
if(j==v.size()){
sz[ak]++;
dzieci[ak].pb(pom);
sz[pom]=1;
ak=2006;
break;
}
ll ans=Query(pom,v[j].ss,ak);
if(ans==pom){
ll pom2=v[j].ss;
dzieci[ak].erase(find(dzieci[ak].begin(),dzieci[ak].end(),v[j].ss));
dzieci[ak].pb(pom);
dzieci[pom].pb(pom2);
sz[pom]=sz[pom2]+1;
sz[ak]++;
ak=2006;
break;
}
if(ans==ak)
continue;
if(ans==v[j].ss){
sz[ak]++;
ak=v[j].ss;
break;
}
ll pom2=v[j].ss;
dzieci[ak].erase(find(dzieci[ak].begin(),dzieci[ak].end(),v[j].ss));
dzieci[ak].pb(ans);
dzieci[ans].pb(pom);
dzieci[ans].pb(pom2);
sz[ans]=sz[pom2]+2;
sz[pom]=1;
sz[ak]+=2;
for(ll k : odw)
sz[k]++;
ak=2006;
break;
}
odw.pb(ak);
}
if(ak!=2006)
dzieci[ak].pb(pom);
}
for(ll i=0;i<n;i++){
for(ll j : dzieci[i])
Bridge(i,j);
}
}
