#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 (u == P1) cur += 1;
else if (u == P2) cur += 2;
mark[u] = cur;
// cout << u << " " << cur << endl;
for (int v:adj[u]) if (exist[v] && v != fa[u]) {
fa[v] = u;
dfs2(v);
}
if (u == P1) cur -= 1;
else if (u == 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]) {
bool done = false;
for (int v:adj[ret]) if (v != add && Query(ret, v, add) == add) {
for (int &V:adj[ret]) if (V == v) V = add;
for (int &V:adj[v]) if (V == ret) V = add;
adj[add].push_back(ret); adj[add].push_back(v);
done = true;
break;
}
// cout << done << endl;
// for (int i:adj[add]) cout << i << " "; cout << endl;
if (!done) {adj[ret].push_back(add); adj[add].push_back(ret);}
// cout << "ADD " << add << " " << done << endl;
// cout << vec[0] << " " << vec[1] << endl;
// cout << "test " << add << " " << ret << endl;
// for (int i:adj[add]) cout << i << " "; cout << endl;
} 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]);
// cout << "add " << add << " " << vec[0] << " " << vec[1] << endl;
// cout << ret << endl;
if (ret != add) {
adj[ret].push_back(add);
adj[add].push_back(ret);
added.push_back(ret);
}
}
return;
} else if (sz == 1) {
int ret = vec[0];
bool done = false;
for (int v:adj[ret]) if (v != add && Query(ret, v, add) == add) {
// cout << v << endl;
for (int &V:adj[ret]) if (V == v) V = add;
for (int &V:adj[v]) if (V == ret) V = add;
adj[add].push_back(ret);
adj[add].push_back(v);
done = true;
break;
}
// cout << adj[add].size() << endl;
if (!done) {adj[ret].push_back(add); adj[add].push_back(ret);}
// cout << adj[add].size() << endl;
// cout << "add. " << add << " " << vec[0] << " " << done << endl;
// cout << adj[add].size() << endl;
return;
}
int RT = vec[0];
fa[RT] = -1;
dfs(RT);
for (int u:vec) {
vector<pair<int,int>> child;
for (int v:adj[u]) if (exist[v]) {
if (v == fa[u]) child.push_back({sz - sub[u], v});
else child.push_back({sub[v], v});
// cout << u << " " << v << endl;
}
sort(child.rbegin(), child.rend());
// if (u == 1) cout << "child " << child[0].first << " " << child[0].second << " " << child[1].first << endl;
if (child[0].first <= sz/2) {
cent = u;
P1 = child[0].second, P2 = child[1].second;
}
}
// cout << "TEST\n";
// cout << add << endl;
// for (int i:vec) cout << i << " "; cout << endl;
// cout << cent << " " << P1 << " " << P2 << endl;
fa[cent] = -1;
dfs2(cent);
int ret = Query(add, P1, P2);
// cout << ret << endl;
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;
}
solve(add, nxt);
}
void Solve(int N) {
n = N;
for (int i=0;i<n;i++) adj[i].clear();
for (int i=0;i<n;i++) exist[i] = false;
adj[0].push_back(1), adj[1].push_back(0);
added = {0, 1};
for (int i=2;i<n;i++) {
// cout << "CHECK " << i << endl;
// for (int u=0;u<n;u++) {for (int v:adj[u]) cout << v << " "; cout << endl;}
// for (int j:added) cout << j << " "; cout << endl;
for (int j:added) exist[j] = true;
if (!exist[i]) {
solve(i, added);
added.push_back(i);
}
// cout << "test\n";
}
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) {
// cout << u << " " << v << endl;
Bridge(u, v);
}
}
