#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) {
vector<vector<int>> grid(n, vector<int>(n, 0));
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
int dis = getDistance(i, j);
grid[i][j] = dis;
grid[j][i] = dis;
}
}
int l=0, r=0;
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
if (grid[i][j] > grid[l][r]) {
l=i, r=j;
}
}
}
int R = 1e9+1;
for (int i=0; i<n; i++) {
if (i==l || i==r) continue;
int lca = grid[i][l]+grid[i][r]-grid[l][r];
lca /= 2;
int disl = grid[i][l]-lca;
int disr = grid[i][r]-lca;
R = min(R, max(disl, disr));
}
return R;
}
