#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int hubDistance(int n, int sub){
int best=0, id=0;
for(int i=1;i<n;i++){
int at=getDistance(0,i);
if(at>best){
best=at;
id=i;
}
}
vector<int>d1(n), d2(n);
for(int i=0;i<n;i++) d1[i]=getDistance(id,i);
int f1=id, f2=0; best=0;
for(int i=0;i<n;i++){
if(d1[i]>best){
best=d1[i];
f2=i;
}
}
for(int i=0;i<n;i++) d2[i]=getDistance(f2,i);
int r=inf;
for(int i=0;i<n;i++){
int x=abs(d1[i]-d2[i])+best;
r=min(r,x/2);
}
auto solve4_1=[&](){
int e=1, m=0, d=1;
for(int i=0;i<n;i++){
if(i==f1||i==f2) continue;
int x=(d1[i]-d2[i])+best; x/=2;
if(x<r) e++;
if(x==r) m++;
if(x>r) d++;
}
if(max({e,m,d})<=(n/2)) return r;
return -r;
};
auto solve4_2=[&](){
int e=1, m=0, d=1;
for(int i=0;i<n;i++){
if(i==f1||i==f2) continue;
int x=(d2[i]-d1[i])+best; x/=2;
if(x<r) e++;
if(x==r) m++;
if(x>r) d++;
}
if(max({e,m,d})<=(n/2)) return r;
return -r;
};
return max(solve4_1(),solve4_2());
}
