#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int ll
#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
using ti = array<int, 3>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int hubDistance(int n, int sub) {
pi maxi{-1, -1};
for (int i = 1; i < n; ++i) {
maxi = max(maxi, pi{getDistance(0, i), i});
}
int u = maxi[1];
maxi = {-1, -1};
vector<int> dist_u(n), dist_v(n);
for (int i = 0; i < n; ++i) {
dist_u[i] = getDistance(u, i);
maxi = max(maxi, pi{dist_u[i], i});
}
int v = maxi[1];
for (int i = 0; i < n; ++i) {
dist_v[i] = getDistance(v, i);
}
int d = dist_u[v], R = 1e9;
for (int i = 0; i < n; ++i) {
int here = dist_u[i] + dist_v[i];
here -= d;
here /= 2;
here = max(dist_u[i] - here, dist_v[i] - here);
R = min(R, here);
}
return R;
}
/*
*/
