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