#include"meetings.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2025;
set<int> st[MAXN];
bool ck[MAXN],kc[MAXN];
pair<int,int> mx;
int root[MAXN];
void dfs(int i,int pre,int d)
{
root[i]=pre,mx=max(mx,{d,i});
for(auto v:st[i]) if(v!=pre&&kc[v]) dfs(v,i,d+1);
}
void addedge(int l,int r)
{
if(l!=r) st[l].insert(r),st[r].insert(l);
}
void deledge(int l,int r)
{
st[l].erase(r),st[r].erase(l);
}
void Solve(int N)
{
addedge(0,1);
ck[0]=ck[1]=true;
for(int i=2;i<N;i++) if(!ck[i])
{
for(int j=0;j<N;j++) kc[j]=ck[j];
int rt=0;
while(true)
{
mx={-1,-1};
dfs(rt,rt,0);
int pos=mx.second;
mx={-1,-1};
dfs(pos,pos,0);
int pos2=mx.second;
if(pos==pos2)
{
addedge(i,pos);
break;
}
int res=Query(pos,pos2,i);
vector<int> chain;
while(pos2!=pos) chain.push_back(pos2),kc[pos2]=false,pos2=root[pos2];
kc[pos]=false,pos2=mx.second,chain.push_back(pos);
if(ck[res]) kc[res]=true,rt=res;
else
{
ck[res]=true;
int l=1,r=chain.size()-1,p=0;
while(l<=r)
{
int mid=(l+r)/2,v=Query(chain[0],chain[mid],res);
if(v!=res) l=mid+1;
else r=mid-1,p=mid;
}
deledge(chain[p-1],chain[p]);
addedge(chain[p-1],res);
addedge(chain[p],res);
addedge(i,res);
break;
}
}
ck[i]=true;
}
for(int i=0;i<N;i++) for(auto v:st[i]) if(i<v) Bridge(i,v);
}
