#include "towns.h"
#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
using namespace std;
int hubDistance(int N, int sub) {
int a = -1;
int maxd = -1;
//dist a 0
for (int i = 0; i < N; i++) {
int kkk = getDistance(0, i);
if (kkk > maxd) {
a = i;
maxd = kkk;
}
}
int b = -1;
maxd = -1;
//dist al dist de 0
vector<int> dist1(N, -1);
for (int i = 0; i < N; i++) {
dist1[i] = getDistance(a, i);
if (dist1[i] > maxd) {
b = i;
maxd = dist1[i];
}
}
//dist al dist del dist del 0
vector<int> dist2(N, -1);
for (int i = 0; i < N; i++) {
dist2[i] = getDistance(b, i);
}
int dia = dist1[b];
int ans = 1e9;
//centro
//cota machin, en como 3 n
for (int i = 0; i < N; i++) {
int s = (dia + abs(dist1[i] - dist2[i])) / 2;
ans = min(ans, s);
}
return ans;
}
