#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
int nw,rt,num,sz[2009],vis[2009],mm[2009];
set<int> s[2009];
void fr(int x,int fa){
    sz[x]=1;
    mm[x]=0;
    for(auto i:s[x]){
        if(!vis[i]&&i!=fa){
            fr(i,x);
            sz[x]+=sz[i];
            mm[x]=max(mm[x],sz[i]);
        }
    }
    mm[x]=max(mm[x],num-mm[x]);
    if(mm[x]<mm[rt])rt=x;
}
void add(int x,int y,int z){
    s[x].erase(y);
    s[y].erase(x);
    s[x].insert(z);
    s[z].insert(x);
    s[y].insert(z);
    s[z].insert(y);
}
void solve(int x,int fa){
//    cout<<x<<" "<<fa<<" "<<nw<<endl;
    if(sz[x]==1){
        s[x].insert(nw);
        s[nw].insert(x);
        return;
    }
    vis[fa]=1;
    rt=0;
    num=sz[x];
    fr(x,fa);
    fr(rt,0);
    vector<pair<int,int> > p(s[rt].size());
    int num=0;
    for(auto j:s[rt]){
        if(!vis[j]){
            p[num++]=make_pair(sz[j],j);
        }
    }
    sort(p.begin(),p.begin()+num);
    for(int i=0;i<num;i+=2){
        if(i+1==num){
            int u=p[i].second;
            int tmp=Query(nw-1,u-1,rt-1)+1;
            if(tmp==nw)add(rt,u,nw);
            else if(tmp==u)solve(u,rt);
            else if(tmp==rt){
                s[rt].insert(nw);
                s[nw].insert(rt);
            }
            else{
                add(rt,u,tmp);
                s[tmp].insert(nw);
                s[nw].insert(tmp);
            }
            return;
        }
        else{
            int u=p[i].second,v=p[i+1].second;
//            cout<<"a "<<u<<" "<<v<<" "<<nw<<endl;
            int tmp=Query(nw-1,u-1,v-1)+1;
            if(tmp==nw){
                tmp=Query(nw-1,u-1,rt-1)+1;
                if(tmp==nw)add(rt,u,nw);
                else add(rt,v,nw);
                return;
            }
            else if(tmp==u){
                solve(u,rt);
                return;
            }
            else if(tmp==v){
                solve(v,rt);
                return;
            }
        }
    }
    s[rt].insert(nw);
    s[nw].insert(rt);
    return;
}
void Solve(int N) {
    s[2].insert(1);
    s[1].insert(2);
    mm[0]=0x3f3f3f3f;
    for(int i=3;i<=N;i++){
        if(s[i].empty()){
            nw=i;
            for(int j=1;j<=N;j++)vis[j]=0;
            sz[1]=i-1;
            solve(1,0);
        }
    }
    for(int i=1;i<=N;i++){
        for(auto j:s[i]){
            if(j>i)Bridge(i-1,j-1);
        }
    }
    return;
}