#include "towns.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 105;
int dist[MAX_N][MAX_N];
int n;
int Dist(int v, int u) {
if (u == v) return 0;
if (dist[v][u] == -1) {
dist[v][u] = dist[u][v] = getDistance(u, v);
}
return dist[v][u];
}
struct Dsu{
vi par, sz;
Dsu(int n) {
par.resize(n), sz.resize(n, 1);
iota(all(par), 0);
}
int Find(int i) {
return par[i] == i ? i : par[i] = Find(par[i]);
}
void Union(int a, int b) {
int pa = Find(a), pb = Find(b);
if (pa == pb) return;
if (sz[pa] < sz[pb]) swap(pa, pb);
par[pb] = pa;
sz[pa] += sz[pb];
}
};
bool CheckCentroid(int v, int d1, int u, int d2) {
vi dist_center(n);
dist_center[v] = d1, dist_center[u] = d2;
for (int i = 0; i < n; i++) {
if (i == v || i == u) continue;
int a1 = Dist(v, u), a2 = Dist(v, i), a3 = Dist(u, i);
int x, y, z;
z = (a2 + a3 - a1) >> 1;
x = a2 - z, y = a3 - z;
if (x <= d1) {
dist_center[i] = z + d1 - x;
} else {
dist_center[i] = z + d2 - y;
}
}
Dsu dsu(n);
vi nodes = {u, v};
for (int i : nodes) {
for (int j = 0; j < n; j++) {
if (j == i) continue;
if (Dist(i, j) < dist_center[i] + dist_center[j]) {
dsu.Union(i, j);
}
}
}
int sz1 = dsu.sz[dsu.Find(v)], sz2 = dsu.sz[dsu.Find(u)];
int sz3 = n - sz1 - sz2;
return max({sz1, sz2, sz3}) <= n / 2;
}
int hubDistance(int N, int sub) {
n = N;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = -1;
}
}
pii p1 = {0, 0}, p2 = {0, 0}, q;
for (int i = 1; i < n; i++) {
q = {Dist(0, i), i};
chkmax(p1, q);
}
int v = p1.y;
for (int i = 0; i < n; i++) {
q = {Dist(v, i), i};
chkmax(p2, q);
}
int u = p2.y;
int ans = dist[v][u];
vii dists;
for (int k = 0; k < n; k++) {
if (k == v || k == u) continue;
int a1 = Dist(v, u), a2 = Dist(v, k), a3 = Dist(u, k);
int x, y, z;
z = (a2 + a3 - a1) >> 1;
x = a2 - z, y = a3 - z;
dists.push_back({x, y});
chkmin(ans, max(x, y));
}
if (sub <= 2) return ans;
vii hubs;
for (pii p : dists) {
if (max(p.x, p.y) == ans) hubs.push_back(p);
}
for (pii p : hubs) {
if (CheckCentroid(v, p.x, u, p.y)) return ans;
}
return -ans;
}
