/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int getDistance(int i,int j);
#include"towns.h"
vector<vector<int>>d;
int g(int i,int j){
if(i>j)swap(i,j);
return (i!=j&&d[i][j]==0?(d[i][j]=getDistance(i,j)):d[i][j]);
}
vector<int>F,sz;
int find(int i){
return (F[i]==i?i:(F[i]=find(F[i])));
}
void uni(int x,int y){
x=find(x);y=find(y);
if(x!=y){
if(sz[x]<sz[y])swap(x,y);
sz[x]+=sz[y];
F[y]=x;
}
}
int hubDistance(int n,int sbt){
d.assign(n,vector<int>(n,0));
int a=0,b=0,mmx=0;
for(int i=0;i<n;i++){
if(g(i,a)>mmx){
mmx=g(i,a);
b=i;
}
}
set<vector<array<int,2>>>c;
int ans=1e6,f=0;
{
set<int>s;
for(int i=0;i<n;i++){
if(i==a||i==b)continue;
s.insert((g(a,i)+g(a,b)-g(i,b))/2);
}
for(auto&ds:s){
int mx=max(ds,g(a,b)-ds);
for(int k=0;k<n;k++){
if(k==a||k==b)continue;
int dd=(g(a,b)+g(a,k)-g(b,k))/2;
mx=max(mx,(g(a,k)+g(b,k)-g(a,b))/2+abs(dd-ds));
}
ans=min(ans,mx);
}
if(sbt<3)return ans;
for(auto&ds:s){
vector<array<int,2>>dds;
int mx=max(ds,g(a,b)-ds);
int sz[3]={1,1,0};
for(int k=0;k<n;k++){
if(k==a||k==b){
dds.push_back(k==a?array<int,2>{ds,a}:array<int,2>{d[a][b]-ds,b});
continue;
}
int dd=(g(a,b)+g(a,k)-g(b,k))/2;
mx=max(mx,(g(a,k)+g(b,k)-g(a,b))/2+abs(dd-ds));
dds.push_back({(g(a,k)+g(b,k)-g(a,b))/2+abs(dd-ds),k});
sz[(ds<dd?0:(ds>dd?1:2))]++;
}
if(ans==mx){
if(sbt==4&&(max({sz[0],sz[1],sz[2]})<=n/2))return ans;
if(sbt>2&&sbt!=4)c.insert(dds);
}
}
}
if(sbt==4)return -ans;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)d[j][i]=g(i,j);
f=0;
for(auto&s:c){
vector<int>dis(n);
for(auto&[i,j]:s)dis[j]=i;
F.resize(n);
iota(F.begin(),F.end(),0);
sz.assign(n,1);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(g(i,j)<dis[i]+dis[j]){
uni(i,j);
}
}
}
int mx=0;
for(int i=0;i<n;i++)mx=max(mx,sz[find(i)]);
if(mx<=n/2)return ans;
}
return -ans;
}
