#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
const int MAXN = 120;
const int INF = 0x3f3f3f3f3f3f3f3f;
int dist[MAXN][MAXN];
int query(int a, int b) {
if (a == b) return 0;
if (a > b) swap(a, b);
if (dist[a][b]) return dist[a][b];
return (dist[a][b] = getDistance(a, b));
}
int32_t hubDistance(int32_t n, int32_t sub) {
memset(dist, 0, sizeof dist);
// achar diametro
pii mx = {0, 0};
for (int i = 1; i < n; i++) mx = max(mx, {query(1, i), i});
int p1 = mx.se;
mx = {0, 0};
for (int i = 0; i < n; i++) mx = max(mx, {query(p1, i), i});
int p2 = mx.se, diam = mx.fr;
// 2n - 1 queries
int mi = INF;
for (int i = 0; i < n; i++) {
int apc = query(i, p1);
int bpc = query(i, p2);
int amc = (apc - bpc);
int a = (amc + diam)/2, b = (diam - a);
mi = min(mi, max(a, b));
}
return mi;
}
