#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int hubDistance (int n, int sub) {
int x = -1, v = 0;
for (int i = 1; i < n; i++) {
int s = getDistance(0, i);
if (s > v) {
v = s; x = i;
}
}
int y = -1, u = 0;
vector <int> dist_x(n, 0);
for (int i = 0; i < n; i++) {
if (i != x) {
int s = getDistance(x, i);
dist_x[i] = s;
if (s > u) {
u = s; y = i;
}
}
}
int w = 1e9;
for (int i = 0; i < n; i++) {
if (i != x && i != y) {
int s = dist_x[i];
int t = getDistance(y, i);
w = min(w, abs(s - t));
}
}
//x + y = u
//x - y = w
//x = (u + w) / 2;
return (u + w) / 2;
}
