#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int hubDistance(int N, int sub) {
vector<int> q(N);
for(int i=1;i<N;i++){
q[i]=getDistance(0,i);
}
int a=max_element(q.begin(), q.end())-q.begin();
vector<int> w(N);
for(int i=0;i<N;i++){
if(i==a)continue;
w[i]=getDistance(a,i);
}
int b=max_element(w.begin(), w.end())-w.begin();
vector<int> e(N);
// Tengo el diametro, ahora necesito computar para cada nodo su distancia a uno de ellos
for(int i=0;i<N;i++){
if(i==b)continue;
e[i]=getDistance(b,i);
}
vector<int> r(N, 1e9);
for(int i=0;i<N;i++){
if(i==a||i==b)continue;
int d1=((e[a]+e[i])-w[i])/2;
int d2=((e[a]+w[i])-e[i])/2;
r[i]=max(d1, d2);
}
return *min_element(r.begin(), r.end());
}
