#include<bits/stdc++.h>
#include "towns.h"
using namespace std;
#define ll long long
struct DSU{
vector<ll>fa,siz;
void init(ll n){
fa.resize(n+5); siz.resize(n=5);
}
ll root(ll x){
if(fa[x]==x)return x;
return fa[x]=root(fa[x]);
}
void unite(ll u, ll v){
u=root(u); v=root(v);
if(siz[u]<siz[v])swap(u,v);
siz[u]+=siz[v]; fa[v]=u;
}
};
bool asked[150][150];
ll dist[150][150];
int get(int i, int j){
if(i==j){
dist[i][j]=0; asked[i][j]=1;
return dist[i][j];
}
if(asked[i][j]){
return dist[i][j];
}
dist[i][j]=dist[j][i]=getDistance(i,j);
asked[i][j]=asked[j][i]=1;
return dist[i][j];
}
int hubDistance(int N, int sub){
// getDistance(i, j)
for(int i=0;i<150;i++){
for(int j=0;j<150;j++){
asked[i][j]=0;
}
}
ll initial[150];
for(int i=0;i<N;i++){
initial[i]=get(0,i);
}
ll fur=-1,nd=-1;
for(int i=0;i<N;i++){
if(initial[i]>fur){
fur=initial[i]; nd=i;
}
}
ll dia[150];
for(int i=0;i<N;i++){
dia[i]=get(nd,i);
}
ll fur2=-1,nd2=-1;
for(int i=0;i<N;i++){
if(dia[i]>fur2){
fur2=dia[i]; nd2=i;
}
}
// nd,nd2 forms the diameter
// how far away from nd
ll dep[155];
dep[nd]=0; dep[nd2]=0;
ll diameter=get(nd,nd2);
dep[0]=get(0,nd)+get(0,nd2)-diameter;
dep[0]/=2;
ll fromnd=get(0,nd)-dep[0];
ll fromnd2=get(0,nd2)-dep[0];
for(int i=1;i<N;i++){
ll diff=get(0,i)+get(i,nd)-get(0,nd);
ll req=(diff+2*fromnd);
if(req==2*get(nd,i)){
// closer to nd2
dep[i]=(get(nd2,i)+get(nd,i)-diameter)/2;
}
else{
ll tryy=diff/2;
ll chn=get(i,nd)-tryy;
if(chn>fromnd){
chn=get(0,nd)-dep[0];
dep[i]=get(i,nd)-chn;
}
else{
dep[i]=tryy;
}
}
// dep[i]=(get(nd2,i)+get(nd,i)-diameter)/2;
}
vector<ll>dists;
for(int i=0;i<N;i++){
dists.push_back(get(nd,i)-dep[i]);
}
sort(dists.begin(),dists.end());
dists.erase(unique(dists.begin(),dists.end()),dists.end());
ll ans=1e18; vector<ll>cand;
for(int i=0;i<dists.size();i++){
ll val=max(dists[i],diameter-dists[i]);
if(val<ans){
cand.clear();
ans=val;
cand.push_back(dists[i]);
}
else if(val==ans){
cand.push_back(dists[i]);
}
}
bool ok=0;
for(auto& u: cand){
ll cnt=0;
for(int i=0;i<N;i++){
if(dists[i]==u){
cnt++;
}
}
ll smol=0,lar=0;
if(cnt<=N/2){
// no checking
for(int i=0;i<N;i++){
if(dists[i]<u)smol++;
else if(dists[i]>u)lar++;
}
if(smol<=N/2&&lar<=N/2)ok=1;
}
else{
// since cnt > N/2 others <= N/2
vector<ll>req;
req.push_back(0);
for(int i=0;i<N;i++){
if(dists[i]==u)req.push_back(i);
}
DSU d;
d.init(req.size());
bool used[req.size()+5];
for(int i=0;i<req.size()+5;i++)used[i]=0;
ll ptrl=1,ptrr=1;
while(ptrr<req.size()){
if(ptrl==ptrr){ptrr++; continue;}
if(used[ptrr]){ptrr++; continue;}
if(used[ptrl]){ptrl++; continue;}
ll dt=get(req[ptrl],req[ptrr]);
ll real=dep[req[ptrl]]+dep[req[ptrr]];
if(real==dt){
used[ptrl]=used[ptrr]=1; ptrl++; ptrr++;
}
else{
d.unite(used[ptrl],used[ptrr]); ptrr++;
}
}
ll id=-1;
for(int i=1;i<req.size();i++){
if(!used[i]){
id=i; break;
}
}
if(id==-1)continue;
for(int i=1;i<req.size();i++){
if(d.root(i)!=d.root(id)&&d.root(i)==i){
ll dt=get(req[i],req[id]);
ll real=dep[req[id]]+dep[req[i]];
if(dt!=real){
d.unite(i,id);
}
}
}
if(d.siz[d.root(id)]<=N/2)ok=1;
}
}
if(ok)return ans;
else return -ans;
}
