#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
const long mxN = 2e3 + 7;
int n, sz[mxN];
bool ers[mxN], vis[mxN];
set<int> w[mxN];
void Del(int u, int v)
{
w[u].erase(v);
w[v].erase(u);
}
void Add(int u, int v)
{
if (u == v)
return;
w[u].insert(v);
w[v].insert(u);
}
void DFS(int j, int par)
{
sz[j] = 1;
for (int i : w[j])
{
if (i == par || ers[i])
continue;
DFS(i, j);
sz[j] += sz[i];
}
}
int Find(int j, int par, int num)
{
for (int i : w[j])
{
if (i == par || ers[i])
continue;
if (sz[i] * 2 > num)
return Find(i, j, num);
}
return j;
}
void Centroid(int root, int nw)
{
DFS(root, -1);
if (sz[root] == 1)
{
Add(root, nw);
return;
}
root = Find(root, -1, sz[root]);
DFS(root, -1);
ers[root] = 1;
vector<ii> child;
for (int i : w[root])
child.push_back({sz[i], i});
sort(child.begin(), child.end(), less<ii>());
if (child.size() % 2)
child.push_back({0, root});
for (int i = 0; i < child.size(); i += 2)
{
int u = child[i].se;
int v = child[i + 1].se;
int res = Query(u, v, nw);
if (res == root)
continue;
if (res == u)
{
Centroid(u, nw);
return;
}
if (res == v)
{
Centroid(v, nw);
return;
}
int tmp = Query(u, res, root);
if (tmp != res)
u = v;
Del(u, root);
Add(u, res);
Add(root, res);
Add(nw, res);
vis[res] = 1;
return;
}
Add(root, nw);
}
void Solve(int n)
{
Add(0, 1);
for (int i = 2; i < n; i++)
{
if (vis[i])
continue;
for (int j = 0; j <= n; j++)
ers[j] = 0;
Centroid(0, i);
}
for (int i = 0; i < n; i++)
{
for (int j : w[i])
{
if (j > i)
Bridge(i, j);
}
}
}
