/* Author : Mychecksdead */
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int hubDistance(int n, int sub) {
int x = 0, best = 0;
for(int i = 1; i < n; ++i){
int d = getDistance(0, i);
if(d > best){
best = d;
x = i;
}
}
vi X(n), Y(n);
for(int i = 0; i < n; ++i){
if(i != x){
X[i] = getDistance(x, i);
}
}
int y = max_element(all(X)) - X.begin();
for(int i = 0; i < n; ++i){
if(i != y){
Y[i] = getDistance(y, i);
}
}
int R = MOD, D = X[y];
for(int w = 0; w < n; ++w){
if(w != x && w != y){
int a = X[w], b = Y[w];
R = min(R, max(D + a - b, D + b - a) / 2);
}
}
return R;
}
