#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)
{
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);
while(pos2!=pos) kc[pos2]=false,pos2=root[pos2];
kc[pos]=false,pos2=mx.second;
if(ck[res]) kc[res]=true,rt=res;
else
{
ck[res]=true;
deledge(pos,pos2);
addedge(pos,res);
addedge(pos2,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);
}
