#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 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];
}
int hubDistance(int n, int sub) {
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];
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;
chkmin(ans, max(x, y));
}
return ans;
}
