#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int hubDistance(int N, int sub) {
vector<int> d1(N, 0), d2(N, 0);
int bsf = 0, f1, f2;
for (int i=1; i<N; i++){
int d = getDistance(0, i);
if (d > bsf){
bsf = d;
f1 = i;
}
}
bsf = 0;
for (int i=0; i<N; i++){
if (i == f1) continue;
int d = getDistance(f1, i);
d1[i] = d;
if (d > bsf){
bsf = d;
f2 = i;
}
}
int R = pow(10, 9);
for (int i=0; i<N; i++){
if (i == f1 || i == f2) continue;
int d = getDistance(f2, i);
d2[i] = d;
int l = (d1[i]+d2[i]-bsf)/2;
R = min(R, max(d1[i], d2[i])-l);
}
return R;
}
