#include "meetings.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define fir first
#define sec second
const int mxN=2020;
vector <int> v[mxN], g[mxN];
int msub[mxN];
bool Chk[mxN];
bool used[mxN];
int sub[mxN];
int par[mxN][mxN];
int findpar(int a, int b)
{
if(par[a][b]==b) return b;
return par[a][b]=findpar(a, par[a][b]);
}
bool cmp1(int a, int b)
{
return sub[a]>sub[b];
}
void dfs1(int now, int pre)
{
//printf("now=%d\n", now);
g[now].clear();
sub[now]=1;
msub[now]=-1;
for(int pnxt : v[now])
{
int nxt=findpar(now, pnxt);
if(Chk[nxt] || nxt==pre) continue;
dfs1(nxt, now);
sub[now]+=sub[nxt];
if(msub[now]==-1) msub[now]=nxt;
else if(sub[msub[now]]<sub[nxt]) msub[now]=nxt;
}
}
void dfs2(int now, int pre)
{
//printf("2now=%d\n", now);
g[now].clear();
sub[now]=1;
for(int pnxt : v[now])
{
int nxt=findpar(now, pnxt);
if(Chk[nxt] || nxt==pre) continue;
dfs2(nxt, now);
sub[now]+=sub[nxt];
g[now].push_back(nxt);
}
}
void Solve(int N) {
v[0].push_back(1);
v[1].push_back(0);
for(int i=0;i<N;i++) for(int j=0;j<N;j++) par[i][j]=j;
for(int i=2;i<N;i++)
{
if(used[i]) continue;
int root=i-1;
for(int j=0;j<N;j++) Chk[j]=false;
int cnt=0;
while(true)
{
dfs1(root, -1);
int cent=root;
while(!g[cent].empty() && sub[msub[cent]]*2>sub[cent]) cent=g[cent][0];
dfs2(cent, -1);
//printf("cent=%d\n", cent);
//for(int j=0;j<i;j++) printf("Chk[%d]=%d\n", j, Chk[j]);
/*for(int j=0;j<i;j++)
{
printf("%d: ", j);
for(int nxt : g[j]) printf("%d ", nxt);
printf("\n");
}*/
if(g[cent].empty())
{
v[cent].push_back(i);
v[i].push_back(cent);
break;
}
bool ispar=true;
bool flag=false;
sort(g[cent].begin(), g[cent].end(), cmp1);
for(int j=0;j<g[cent].size();j++)
{
int nxt=g[cent][j];
int res=Query(cent, nxt, i);
if(res!=cent)
{
ispar=false;
if(res==i)
{
//printf("s1");
par[cent][nxt]=i;
par[nxt][cent]=i;
v[i].push_back(cent);
v[i].push_back(nxt);
flag=true;
}
else if(res==nxt)
{
//printf("s2");
root=nxt;
Chk[cent]=true;
//assert(cent!=nxt);
}
else
{
//printf("s3");
par[cent][nxt]=res;
par[nxt][cent]=res;
v[res].push_back(cent);
v[res].push_back(nxt);
v[i].push_back(res);
v[res].push_back(i);
used[res]=true;
flag=true;
}
break;
}
}
if(flag) break;
if(ispar)
{
v[cent].push_back(i);
v[i].push_back(cent);
break;
}
}
}
for(int i=0;i<N;i++)
{
for(int pnxt : v[i])
{
int nxt=findpar(i, pnxt);
if(nxt>i) Bridge(i, nxt);
}
}
}
