#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int hubDistance(int N, int sub) {
int n=N;
int allcnt=0;
vector<vector<int>> rec(n,vector<int>(n,-1));
function<int(int,int)> get=[&](int a,int b){
if(a==b) return 0;
if(a>b) swap(a,b);
if(rec[a][b]!=-1) return rec[a][b];
else{
allcnt++;
if(allcnt>n*(n-1)/2) assert(false);
rec[a][b]=getDistance(a,b);
return rec[a][b];
}
};
vector<int> dis(n),dis2(n);
for(int i=0;i<n;i++){
dis2[i]=get(0,i);
}
int x=max_element(all(dis2))-dis2.begin();
for(int i=0;i<n;i++){
dis[i]=get(x,i);
}
int R=*max_element(all(dis));
int y=0;
vector<int> val1(n),val2(n);
vector<int> vec;
for(int i=0;i<n;i++){
vec.push_back(dis[i]-(dis[i]+dis2[i]-dis[y])/2);
val1[i]=dis[i]-(dis[i]+dis2[i]-dis[y])/2;
val2[i]=(dis[i]+dis2[i]-dis[y])/2;
}
sort(all(vec));
int ans=R;
for(auto v:vec){
ans=min(ans,max(v,R-v));
}
map<int,int> mp;
for(auto v:vec){
mp[v]++;
}
bool tf=false;
int pre=0;
for(auto v:mp){
if(max(v.f,R-v.f)==ans){
int mx=max({pre,v.s,n-pre-v.s});
if(mx<=n/2){
tf=true;
}
}
pre+=v.s;
}
function<bool(int,int)> same=[&](int a,int b){
int d=get(a,b);
return (d!=(val2[a]+val2[b]));
};
if(!tf){
pre=0;
for(auto v:mp){
if(max(v.f,R-v.f)==ans){
if(v.s>(n/2)){
vector<pair<int,int>> diaob,roy,tmp;
for(int i=0;i<n;i++){
if(val1[i]==v.f){
diaob.push_back({i,1});
}
}
while((int)diaob.size()>1){
for(int i=0;i<(int)diaob.size()-1;i+=2){
if(diaob[i].s<diaob[i+1].s) swap(diaob[i],diaob[i+1]);
if(same(diaob[i].f,diaob[i+1].f)){
tmp.push_back({diaob[i].f,diaob[i].s+diaob[i+1].s});
}
else{
roy.push_back({diaob[i].f,diaob[i+1].s});
roy.push_back(diaob[i+1]);
if(diaob[i].s>diaob[i+1].s){
tmp.push_back({diaob[i].f,diaob[i].s-diaob[i+1].s});
}
}
}
if((int)diaob.size()&1) tmp.push_back(diaob.back());
swap(diaob,tmp);
tmp.clear();
}
if(diaob.empty()){
tf=true;
}
else{
int cnt=diaob[0].s;
int node=diaob[0].f;
for(auto u:roy){
if(same(node,u.f)) cnt+=u.s;
}
if(cnt<=(n/2)){
tf=true;
}
else{
tf=false;
}
}
break;
}
}
pre+=v.s;
}
}
return (tf?ans:-ans);
}
