#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int hubDistance(int n, int sub){
vector<int> dist(n, 0), dista(n, 0), distb(n, 0);
for (int i=1; i<n; ++i)dist[i]=getDistance(0, i);
int mx=-1, a=-1, b=-1, ans=INT_MAX/2;
for (int i=0; i<n; ++i)if (dist[i]>mx)mx=dist[i], a=i;
for (int i=0; i<n; ++i)if (i!=a)dista[i]=getDistance(a, i);
mx=-1;
for (int i=0; i<n; ++i)if (dista[i]>mx)mx=dista[i], b=i;
for (int i=0; i<n; ++i)if (i!=b)distb[i]=getDistance(b, i);
for (int i=0; i<n; ++i)ans=min(ans, max(dista[i]-(dista[i]+distb[i]-dista[b])/2, distb[i]-(dista[i]+distb[i]-dista[b])/2));
return ans;
}
