#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int ll
#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
using ti = array<int, 3>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct DSU {
int n;
vector<int> par, sz;
DSU(int n) {
this->n = n;
par.assign(n, 0);
iota(par.begin(), par.end(), 0);
sz.assign(n, 1);
}
int find(int a) {
if (par[par[a]] != par[a]) {
par[a] = find(par[a]);
}
return par[a];
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) {
return;
}
if (sz[a] < sz[b]) {
swap(a, b);
}
sz[a] += sz[b];
par[b] = a;
}
};
int hubDistance(int n, int sub) {
vector<int> dist0(n);
pi maxi{-1, -1};
for (int i = 0; i < n; ++i) {
dist0[i] = getDistance(0, i);
maxi = max(maxi, {dist0[i], i});
}
int u = maxi[1];
maxi = {-1, -1};
vector<int> distu(n);
for (int i = 0; i < n; ++i) {
distu[i] = getDistance(u, i);
maxi = max(maxi, {distu[i], i});
}
auto [diam, v] = maxi;
int pos0 = dist0[u] - (dist0[u] + dist0[v] - diam) / 2;
int R = pos0;
map<int, vector<int>> where;
for (int i = 0; i < n; ++i) {
// u ----|--0-- v
// daca pos[i] >= pos[0] atunci chestia asta va da pozitia gresita dar va fi mereu >=pos[0] deci nu ne pasa pt R
// ok de fapt asta e un lca
int pos = distu[i] - (dist0[i] + distu[i] - distu[0]) / 2;
if (pos < pos0) {
R = min(R, max(pos, diam - pos));
where[pos].pb(i);
} else { // sunt in dreapta sau in subarborele ala
where[pos0].pb(i);
}
}
int cand = -1; // va fi maxim 1
for (auto& [pos, v] : where) {
if (max(pos, diam - pos) == R) {
// se intampla maxim de 2 ori
int left = 0, here = 0, right = 0;
for (auto& [pos2, v2] : where) {
if (pos2 < pos) {
left += v2.size();
} else if (pos2 == pos) {
here += v2.size();
} else if (pos2 > pos) {
right += v2.size();
}
}
if (left <= n / 2 && here <= n / 2 && right <= n / 2) {
return R;
}
if (left <= n / 2 && right <= n / 2) {
assert(cand == -1);
cand = pos;
}
}
}
if (cand == -1) {
return -R;
}
vector<int> rel = where[cand];
int k = rel.size();
DSU dsu(k);
auto query = [&](int i, int j) -> bool { // true if lca != cand
return (distu[i] + distu[j] - 2 * cand != getDistance(rel[i], rel[j]));
};
int now = -1, cnt = 0;
for (int i = 0; i < k; ++i) {
if (now == -1) {
now = i;
cnt = 1;
} else {
if (query(now, i)) {
dsu.unite(i, now);
++cnt;
} else {
--cnt;
if (cnt == 0) {
now = -1;
}
}
}
}
if (now == -1) {
return R;
}
vector<bool> vis(k);
now = dsu.find(now);
vis[now] = true;
int sz = dsu.sz[now];
for (int i = 0; i < k; ++i) {
int p = dsu.find(i);
if (vis[p]) {
continue;
}
vis[p] = true;
if (query(now, p)) {
sz += dsu.sz[p];
}
}
if (sz <= n / 2) {
return R;
} else {
return -R;
}
}
/*
*/
