#include "towns.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
map<pii, int> memo;
int dist(int u, int v) {
if (!memo[{u, v}]) {
memo[{u, v}] = memo[{v, u}] = getDistance(u, v);
}
return memo[{u, v}];
}
int hubDistance(int n, int sub) {
int res = 1000000000;
int furthest = 1, maxdist = dist(0, 1);
ffor(i, 2, n) {
if (dist(0, i) > maxdist) {
maxdist = dist(0, i);
furthest = i;
}
}
int furthest2 = 0;
maxdist = dist(furthest, 0);
ffor(i, 1, n) {
if (i != furthest && dist(furthest, i) > maxdist) {
maxdist = dist(furthest, i);
furthest2 = i;
}
}
map<int, int> xs;
ffor(j, 1, n) {
if (j == furthest2) {
continue;
}
int a = dist(furthest, furthest2), b = dist(furthest2, j), c = dist(furthest, j);
int x = (a + c - b) / 2, y = (b + c - a) / 2;
xs[x] = max(xs[x], y);
}
forin(p, xs) {
int curr = max(max(p.second, p.first), dist(furthest, furthest2) - p.first);
forin(p2, xs) {
if (p != p2) {
curr = max(curr, abs(p2.first - p.first) + p2.second);
}
}
res = min(res, curr);
}
return res;
}
