#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int n,inf=1e9;
map<pair<int,int>,int>mp;
int pors(int u,int v){
if(u>v){
swap(u,v);
}
if(mp.count(make_pair(u,v))==0){
mp[make_pair(u,v)]=getDistance(u,v);
}
return mp[make_pair(u,v)];
}
pair<int,int>getdia(){
vector<pair<int,int>>allv;
for(int i=1;i<n;i++){
allv.push_back(make_pair(pors(0,i),i));
}
sort(allv.begin(),allv.end());
int u=allv.back().second;
return make_pair(u,0);
}
int hubDistance(int N,int sub) {
mp.clear();
n=N;
//sub=sub;
//cout<<"salam"<<endl;
pair<int,int>di=getdia();
int mn=pors(di.first,di.second);
int ted1=0,ted2=0;
vector<pair<int,int>>allv;
for(int i=0;i<n;i++){
if(i!=di.first&&i!=di.second){
int fake1=pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second),fake2=pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first),fake3=pors(i,di.first)+pors(i,di.second)-pors(di.first,di.second);
fake1/=2;
fake2/=2;
fake3/=2;
if(max(fake1,max(fake2,fake3))==mn){
allv.push_back(make_pair(fake1,i));
}else if(max(fake1,max(fake2,fake3))<mn){
allv.clear();
allv.push_back(make_pair(fake1,i));
}
mn=min(mn,max(fake1,max(fake2,fake3)));
if(fake1<fake2){
ted1++;
}else{
ted2++;
}
}
}
sort(allv.begin(),allv.end());
int wh=allv[0].second,tol=allv[0].first;
if(allv[0].first!=allv.back().first){
if(max(ted1,ted2)*2<=n){
return mn;
}else if(ted2*2>n){
wh=allv.back().second;
tol=allv.back().first;
}
}
int cntnow=0,last=di.second,komak=di.first;
for(int i=0;i<n;i++){
if(i==di.first||i==di.second){
continue;
}
int z=(pors(komak,last)+pors(komak,i)-pors(i,last))/2;
if(z>tol){
cntnow++;
continue;
}else if(cntnow>0){
cntnow--;
continue;
}
cntnow++;
last=i;
if(z!=tol){
komak=(di.first^di.second^komak);
tol=pors(di.first,di.second)-tol;
}
}
int cnt=1;
for(int i=0;i<n;i++){
if(i==last||i==komak){
continue;
}
if((pors(last,komak)+pors(komak,i)-pors(last,i))/2>tol){
cnt++;
}
}
if(cnt*2>n){
return -mn;
}
return mn;
}
