#include "meetings.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;
int total = 0;
int findSubSize(int u, int p, vector<vector<int>> &G, vector<int> &subSize, vector<bool> &dead)
{
subSize[u] = 1;
for (int v : G[u]) {
if (v == p || dead[v]) continue;
subSize[u] += findSubSize(v, u, G, subSize, dead);
}
return subSize[u];
}
int findCentroid(int u, int p, vector<vector<int>> &G, int treeSize, vector<int> &subSize, vector<bool> &dead)
{
// cerr << u << ' ' << p << ' ' << treeSize << endl;
bool isCentroid = 1;
for (int v : G[u]) {
if (v == p || dead[v]) continue;
if (subSize[v] > treeSize / 2) isCentroid = 0;
}
if (treeSize - subSize[u] > treeSize / 2) isCentroid = 0;
if (isCentroid) return u;
for (int v : G[u]) {
if (v == p || dead[v]) continue;
int cand = findCentroid(v, u, G, treeSize, subSize, dead);
if (cand) return cand;
}
return 0;
}
void addBetween(int u, int v, int w, vector<vector<int>> &G)
{
*find(G[u].begin(), G[u].end(), v) = w;
*find(G[v].begin(), G[v].end(), u) = w;
G[w] = {u, v};
}
void addVertex(int nxt, vector<vector<int>> &G, vector<bool> &found, vector<bool> &dead, vector<int> &subSize)
{
int N = (int) G.size();
fill(dead.begin(), dead.end(), 0);
int root = 0;
while (!found[nxt]) {
int curSize = findSubSize(root, -1, G, subSize, dead);
int centroid = findCentroid(root, -1, G, curSize, subSize, dead);
if (curSize == 1) {
G[centroid].push_back(nxt);
G[nxt].push_back(centroid);
found[nxt] = 1;
return;
}
findSubSize(centroid, -1, G, subSize, dead);
vector<int> cands;
for (int v : G[centroid]) {
if (!dead[v]) cands.push_back(v);
}
sort(cands.begin(), cands.end(), [&](int u, int v) { return subSize[u] > subSize[v]; });
for (int candRoot : cands) {
int mid = Query(centroid, candRoot, nxt); // guaranteed all arguments are distinct
if (mid == centroid) {
continue;
} else if (mid == candRoot) {
root = candRoot, dead[centroid] = 1;
break;
} else if (mid == nxt) {
addBetween(centroid, candRoot, nxt, G);
found[nxt] = 1;
return;
} else {
addBetween(centroid, candRoot, mid, G);
G[mid].push_back(nxt);
G[nxt].push_back(mid);
found[mid] = found[nxt] = 1;
return;
}
}
if (!dead[centroid]) {
G[centroid].push_back(nxt);
G[nxt].push_back(centroid);
found[nxt] = 1;
return;
}
}
}
void Solve(int N)
{
vector<vector<int>> G(N);
G[1].push_back(0);
G[0].push_back(1);
vector<bool> found(N, 0);
found[1] = found[0] = 1;
vector<int> subSize(N);
vector<bool> dead(N);
for (int nxt = 2; nxt < N; ++nxt) {
if (!found[nxt]) {
addVertex(nxt, G, found, dead, subSize);
}
}
// std::cerr << "total " << total << std::endl;
for (int u = 0; u < N; ++u) {
for (int v : G[u]) {
if (u < v) {
Bridge(u, v);
}
}
}
}
