#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;
}
