#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
int n;
vector<int> adj[maxn];
vector<int> added;
bool exist[maxn];
int sub[maxn], fa[maxn];
void dfs(int u) {
sub[u] = 1;
for (int v:adj[u]) if (exist[v] && v != fa[u]) {
fa[v] = u;
dfs(v);
sub[u] += sub[v];
}
}
int cent, P1, P2, cur = 0;
int mark[maxn];
void dfs2(int u) {
if (cur == P1) cur += 1;
else if (cur == P2) cur += 2;
mark[u] = cur;
for (int v:adj[u]) if (exist[v] && v != fa[u]) {
fa[v] = u;
dfs2(v);
}
if (cur == P1) cur -= 1;
else if (cur == P2) cur -= 2;
}
void solve(int add, vector<int> vec) {
int sz = vec.size();
if (sz == 2) {
int ret = Query(vec[0], vec[1], add);
if (ret == vec[0] || ret == vec[1]) {
adj[ret].push_back(add); adj[add].push_back(ret);
} else {
for (int &v:adj[vec[0]]) if (v == vec[1]) v = ret;
for (int &v:adj[vec[1]]) if (v == vec[0]) v = ret;
adj[ret].push_back(vec[0]); adj[ret].push_back(vec[1]);
if (ret != add) {
adj[ret].push_back(add);
adj[add].push_back(ret);
added.push_back(ret);
}
}
return;
} else if (sz == 1) {
adj[vec[0]].push_back(add); adj[add].push_back(vec[0]);
return;
}
int RT = vec[0];
fa[RT] = -1;
dfs(RT);
for (int u:vec) {
vector<pair<int,int>> child;
if (u != RT) child.push_back({sz - sub[u], fa[u]});
for (int v:adj[u]) child.push_back({sub[v], v});
sort(child.rbegin(), child.rend());
if (child[0].first <= sz/2) {
cent = u;
P1 = child[0].second, P2 = child[1].second;
}
}
dfs(cent);
int ret = Query(add, P1, P2);
if (ret == P1) ret = 1;
else if (ret == P2) ret = 2;
else ret = 0;
vector<int> nxt;
for (int i:vec) {
if (mark[i] == ret) nxt.push_back(i);
else exist[i] = false;
}
if (ret == 0) {
nxt.push_back(P1); nxt.push_back(P2);
exist[P1] = exist[P2] = true;
}
solve(add, nxt);
}
void Solve(int N) {
n = N;
adj[0].push_back(1), adj[1].push_back(0);
added = {0, 1};
for (int i=2;i<n;i++) {
for (int j:added) exist[j] = true;
solve(i, added);
}
set<pair<int,int>> ans;
for (int i=0;i<n;i++) {
for (int v:adj[i]) if (i < v) ans.insert({i, v});
}
for (auto [u, v]:ans) Bridge(u, v);
}
