#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=2000;
int n;
vector<int>adj[maxn+2];
int sub[maxn+2];
bool vis[maxn+2],msk[maxn+2];
void dfs(int cur,int par){
sub[cur]=1;
for(auto x : adj[cur]){
if(x==par || vis[x])continue;
dfs(x,cur);
sub[cur]+=sub[x];
}
}
int centro(int cur,int par,int sz){
for(auto x : adj[cur]){
if(x==par || vis[x])continue;
if(sub[x]>=sz/2){
return centro(x,cur,sz);
}
}
return cur;
}
void add(int cur,int targ){
dfs(cur,-1);
int root=centro(cur,-1,sub[cur]);
dfs(root,-1);
vis[root]=true;
vector<ii>sblh;
for(auto x : adj[root]){
if(vis[x])continue;
sblh.pb({sub[x],x});
}
if(sblh.size()%2==1)sblh.pb({0,root});
sort(sblh.rbegin(),sblh.rend());
for(int q=0;q<sblh.size();q+=2){
int a=sblh[q].sec,b=sblh[q+1].sec;
int nd=Query(a,b,targ);
if(a==nd || b==nd){
if(b==nd && b==root)continue;
add(nd,targ);
return;
}
else if(nd!=root){
int piv;
if(Query(a,root,nd)==nd){
piv=a;
}
else{
piv=b;
}
adj[piv].erase(find(adj[piv].begin(),adj[piv].end(),root));
adj[root].erase(find(adj[root].begin(),adj[root].end(),piv));
adj[root].pb(nd),adj[nd].pb(root);
adj[piv].pb(nd),adj[nd].pb(piv);
if(piv!=targ){
adj[piv].pb(targ),adj[targ].pb(piv);
}
msk[piv]=true;
return;
}
}
adj[targ].pb(root),adj[root].pb(targ);
}
void Solve(int N) {
n=N;
adj[0].push_back(1);
adj[1].push_back(0);
msk[0]=msk[1]=true;
for(int q=2;q<n;q++){
if(msk[q])continue;
memset(vis,false,sizeof vis);
add(0,q);
msk[q]=true;
}
for(int q=0;q<N;q++){
for(auto x : adj[q]){
if(x>q)Bridge(q,x);
}
}
}
