#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[2005], tmp[2005], tmp2[2005], vec, vec2, path;
int dp[2005], done[2005];
void createEdge(int u, int v)
{
//cout << "createEdge " << u << ' ' << v << '\n';
adj[u].push_back(v);
adj[v].push_back(u);
}
void deleteEdge(int u, int v)
{
//cout << "deleteEdge " << u << ' ' << v << '\n';
adj[u].erase(find(adj[u].begin(), adj[u].end(), v));
adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
}
void dfs(int u, int p)
{
dp[u]=tmp[u].size();
for (int v:tmp[u])
{
if (v==p)
continue;
dfs(v, u);
dp[u]=max(dp[u], dp[v]);
}
}
void dfs2(int u, int p)
{
path.push_back(u);
int node=-1;
for (int v:tmp[u])
{
if (v==p)
continue;
if (node==-1 || dp[node]<dp[v])
node=v;
}
if (node!=-1)
dfs2(node, u);
}
void dfs3(int u, int p1, int p2)
{
vec2.push_back(u);
for (int v:tmp[u])
{
if (v==p1 || v==p2)
continue;
tmp2[u].push_back(v);
tmp2[v].push_back(u);
dfs3(v, u, u);
}
}
void Solve(int n)
{
createEdge(0, 1);
done[0]=done[1]=1;
for (int i=2; i<n; i++)
{
if (done[i])
continue;
vec.clear();
for (int j=0; j<n; j++)
{
if (done[j])
{
vec.push_back(j);
tmp[j].clear();
for (int u:adj[j])
tmp[j].push_back(u);
}
}
done[i]=1;
while (1)
{
if (vec.size()==1)
{
createEdge(vec[0], i);
break;
}
int root=-1;
for (int u:vec)
if (root==-1 || tmp[root].size()<tmp[u].size())
root=u;
dfs(root, -1);
int node1=-1, node2=-1;
for (int u:tmp[root])
{
if (node1==-1 || dp[node1]<dp[u])
{
node2=node1;
node1=u;
}
else if (node2==-1 || dp[node2]<dp[u])
node2=u;
}
path.clear();
path.push_back(root);
dfs2(node1, root);
if (node2!=-1)
{
reverse(path.begin(), path.end());
dfs2(node2, root);
}
int res=Query(path.front(), path.back(), i);
if (res==i)
{
int l=0, r=path.size()-1;
while (l+2<=r)
{
int mid=(l+r)/2;
res=Query(path[l], path[mid], i);
if (res==i)
r=mid;
else
l=mid;
}
deleteEdge(path[l], path[r]);
createEdge(path[l], i);
createEdge(path[r], i);
break;
}
int ind=-1;
for (int j=0; j<path.size(); j++)
{
if (path[j]==res)
{
ind=j;
break;
}
}
if (ind==-1)
{
int l=0, r=path.size()-1;
while (l+2<=r)
{
int mid=(l+r)/2, newres=Query(path[l], path[mid], i);
if (newres==res)
r=mid;
else
l=mid;
}
deleteEdge(path[l], path[r]);
createEdge(path[l], res);
createEdge(path[r], res);
createEdge(i, res);
done[res]=1;
break;
}
vec2.clear();
for (int u:vec)
tmp2[u].clear();
dfs3(path[ind], ind?path[ind-1]:-1, ind+2<=path.size()?path[ind+1]:-1);
vec=vec2;
for (int u:vec)
{
tmp[u].clear();
for (int v:tmp2[u])
tmp[u].push_back(v);
}
}
}
for (int i=0; i<n; i++)
for (int u:adj[i])
if (u>i)
Bridge(i, u);
}
