#include <bits/stdc++.h> #include "towns.h" using namespace std; using ll = long long; using pii = pair<int, int>; const int MOD = 1e9+7; int hubDistance(int n, int s) { int idx=0, mx=0; for (int i=1; i<n; i++) { int dis = getDistance(0, i); if (dis > mx) { mx = dis; idx = i; } } int l = idx; int r=l; mx=0; vector<int> disl(n, 0); for (int i=0; i<n; i++) { int dis = getDistance(i, l); disl[i] = dis; if (dis > mx) { r = i; mx = dis; } } vector<int> disr(n, 0); for (int i=0; i<n; i++) { int dis = getDistance(i, r); disr[i] = dis; } int R = 1e9+1; for (int i=0; i<n; i++) { if (i==l || i==r) continue; int lca = disl[i]+disr[i]-disl[r]; lca /= 2; int dissl = disl[i]-lca; int dissr = disr[i]-lca; R = min(R, max(dissl, dissr)); } return R; }