// 官解作法
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define fs first
#define sc second
int n;
vector<int> e[2010];
int invt[2010] = {0}; // whether in virtual tree yet
bool block[2010] = {0};
int sz[2010];
void deledge (int i, int j) {
e[i].erase(find(e[i].begin(), e[i].end(), j));
e[j].erase(find(e[j].begin(), e[j].end(), i));
}
void addedge (int i, int j) {
// if (i == j) {
// cout << "wtf\n";
// exit(0);
// }
e[i].push_back(j);
e[j].push_back(i);
}
int tt = 0;
int dfs (int i, int par) {
if (block[i]) return sz[i] = 0;
sz[i] = 1;
for (int j : e[i]) if (j != par) sz[i] += dfs(j, i);
return sz[i];
}
int dfs2 (int i, int par, int tsz) {
if (block[i]) return -1;
bool y = 1;
for (int j : e[i]) {
if (j == par) continue;
int q = dfs2(j, i, tsz);
if (q != -1) return q;
if (sz[j] > tsz/2) y = 0;
}
if (!y or tsz - sz[i] > tsz/2) return -1;
return i;
}
void add (int rt, int ni) {
int tsz = dfs(rt, rt);
tt++;
if (tt > 1000) exit(0);
if (tsz == 1) {
invt[ni] = 1;
addedge(rt, ni);
return;
}
else if (tsz == 2) {
invt[ni] = 1;
int j = -1;
for (int cj : e[rt]) if (!block[cj]) j = cj;
int q = Query(j, ni, rt);
if (q == j or q == rt) {
addedge(q, ni);
return;
}
deledge(j, rt);
addedge(j, q);
addedge(rt, q);
if (q != ni) {
invt[q] = 1;
addedge(q, ni);
}
return;
}
int g = dfs2(rt, rt, tsz);
dfs(g, -1);
vector<pii> sons;
for (int j : e[g]) if (!block[j]) sons.push_back({sz[j], j});
sort(sons.begin(), sons.end()); reverse(sons.begin(), sons.end());
for (int i = 0; i < sons.size(); i+=2) {
if (i == sons.size()-1) {
add(sons[i].sc, ni);
return;
}
int s = sons[i].sc, t = sons[i+1].sc;
int q = Query(s,t,ni);
if (q == s or q == t) {
invt[ni] = 1;
block[g] = 1;
add(q, ni);
return;
}
if (q == g) {
block[s] = block[t] = 1;
continue; // 可能在別的子樹、也可能在還沒出現過的子樹
}
if (Query(s, q, g) == q) {
deledge(s, g);
addedge(s, q);
addedge(g, q);
invt[ni] = invt[q] = 1;
if (q != ni) {
addedge(ni, q);
}
return;
}
else {
deledge(t, g);
addedge(t, q);
addedge(g, q);
invt[ni] = invt[q] = 1;
if (q != ni) {
addedge(ni, q);
}
return;
}
}
addedge(g, ni);
invt[ni] = 1;
return;
}
void Solve(int N) {
n = N;
for (int i = 0; i <= n; i++) {
invt[i] = 0, block[i] = 0;
e[i].clear();
}
invt[0] = invt[1] = 1;
addedge(0,1);
for (int i = 2; i < n; i++) {
if (!invt[i]) {
for (int j = 0; j < n; j++) block[j] = 0;
add(0, i);
}
}
for (int i = 0; i < n; i++) for (int j : e[i]) if (i < j) Bridge(i, j);
}
