#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int MAX = 2e3;
int sz[MAX];
bool del[MAX];
vector<int> g[MAX];
void add(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
void ers(int u, int v) {
g[u].erase(find(g[u].begin(), g[u].end(), v));
g[v].erase(find(g[v].begin(), g[v].end(), u));
}
void split(int p, int u, int z, int x) {
ers(p, u);
add(p, z);
add(z, u);
if (z != x) {
add(z, x);
}
}
void dfs(int u, int p) {
sz[u] = 1;
for (int v : g[u]) {
if (!del[v] && v != p) {
dfs(v, u);
sz[u] += sz[v];
}
}
}
int findCen(int u, int p, int tot) {
for (int v : g[u]) {
if (!del[v] && v != p && sz[v] * 2 > tot) {
return findCen(v, u, tot);
}
}
return u;
}
void solve(int u, int x) {
dfs(u, u);
u = findCen(u, u, sz[u]);
dfs(u, u);
del[u] = 1;
vector<int> cands;
for (auto v : g[u]) {
if (!del[v]) {
cands.push_back(v);
}
}
sort(cands.begin(), cands.end(), [&](int u, int v) {
return sz[u] > sz[v];
});
for (int i = 0; i + 1 < cands.size(); i += 2) {
int a = cands[i], b = cands[i + 1], z = Query(x, a, b);
if (z == a || z == b) {
solve(z, x);
return;
}
if (z ^ u) {
int y = Query(u, x, a) == u ? b : a;
split(u, y, z, x);
return;
}
}
if (cands.size() & 1) {
int v = cands.back(), z = Query(x, v, u);
if (z == v) {
solve(z, x);
return;
} else if (z ^ u) {
split(u, v, z, x);
return;
}
}
add(u, x);
}
void Solve(int N) {
add(0, 1);
for (int i = 2; i < N; ++i) {
if (!g[i].size()) {
fill(del, del + N, 0);
solve(0, i);
}
}
for (int i = 0; i < N; ++i) {
for (int j : g[i]) {
if (i < j) {
Bridge(i, j);
}
}
}
}
