#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int n,inf=1e9;
map<pair<int,int>,int>mp;
map<int,int>mpa,tof;
int pors(int u,int v){
if(u==v){
return 0;
}
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(0,u);
}
int hubDistance(int N,int sub) {
mp.clear();
tof.clear();
mpa.clear();
n=N;
//sub=sub;
//cout<<"salam"<<endl;
pair<int,int>di=getdia();
int mn=inf;
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(mpa[fake1]>=fake3){
tof[fake1]=i;
}
mpa[fake1]=max(mpa[fake1],fake3);
if(fake1<fake2){
ted1++;
}else{
ted2++;
}
// if(fake1==6){
// cout<<di.first<<" "<<di.second<<" "<<i<<" "<<fake1<<" "<<fake2<<" "<<fake3<<endl;
// }
}
}
mpa[0]=0;
mpa[pors(di.first,di.second)]=0;
tof[0]=di.first;
tof[pors(di.first,di.second)]=di.second;
vector<pair<int,int>>allt;
vector<int>suf,ps,wsuf,wps;
int sz=0;
suf.push_back(0);
ps.push_back(0);
allt.push_back(make_pair(0,0));
for(auto x:mpa){
allt.push_back(make_pair(x.first,x.second));
suf.push_back(0);
ps.push_back(0);
sz++;
}
suf.push_back(0);
ps.push_back(0);
suf.push_back(0);
ps.push_back(0);
allt.push_back(make_pair(0,0));
wsuf.resize((int)suf.size());
wps.resize((int)ps.size());
for(int i=1;i<=sz;i++){
ps[i]=max(ps[i-1]-allt[i-1].first+allt[i].first,allt[i].second);
if(allt[i].second<ps[i]){
wps[i]=wps[i-1];
}else{
wps[i]=tof[allt[i].first];
}
}
for(int i=sz;i>=1;i--){
suf[i]=max(suf[i+1]-allt[i].first+allt[i+1].first,allt[i].second);
if(allt[i].second<suf[i]){
wsuf[i]=wsuf[i+1];
}else{
wsuf[i]=tof[allt[i].first];
}
}
ted1=ted2=0;
for(int i=1;i<=sz;i++){
if(suf[i]>ps[i]){
tof[allt[i].first]=wsuf[i];
mpa[allt[i].first]=suf[i];
}else{
tof[allt[i].first]=wps[i];
mpa[allt[i].first]=ps[i];
}
}
int lena=-1;
for(auto x:mpa){
if(x.second==mn){
allv.push_back(make_pair(x.first,tof[x.first]));
}else if(x.second<mn){
lena=x.first;
allv.clear();
allv.push_back(make_pair(x.first,tof[x.first]));
}
mn=min(mn,x.second);
}
for(int i=0;i<n;i++){
if(pors(di.first,i)+pors(di.first,di.second)-pors(di.first,di.second)<=lena*2){
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;
vector<vector<int>>allver,allezaf;
allver.push_back({di.first,di.second});
allezaf.push_back({1,-1});
allver.push_back({});
allezaf.push_back({});
for(int i=0;i<n;i++){
if(i==di.first||i==di.second){
continue;
}
if(allver.back().size()==0){
allver.back().push_back(i);
allezaf.back().push_back(1);
cntnow=1;
last=i;
continue;
}
int z=(pors(komak,last)+pors(komak,i)-pors(i,last))/2;
if(z>tol){
allver.back().push_back(i);
allezaf.back().push_back(1);
cntnow++;
continue;
}else if(cntnow>0){
allver.back().push_back(i);
allezaf.back().push_back(-1);
cntnow--;
if(cntnow==0&&i!=n-1){
if(z!=tol){
komak=(di.first^di.second^komak);
tol=pors(di.first,di.second)-tol;
}
allver.push_back({});
allezaf.push_back({});
}
continue;
}
}
int cnt=0;
for(int i=0;i<(int)allver.size();i++){
if((int)allver[i].size()==0){
continue;
}
int z=(pors(komak,last)+pors(komak,allver[i][0])-pors(allver[i][0],last))/2;
if(z>tol){
for(auto x:allezaf[i]){
if(x==1){
cnt++;
}
}
}else{
for(int j=0;j<(int)allver[i].size();j++){
if(allezaf[i][j]==-1){
z=(pors(komak,last)+pors(komak,allver[i][j])-pors(allver[i][j],last))/2;
if(z>tol){
cnt++;
}
}
}
}
}
if(cnt*2>n){
return -mn;
}
return mn;
}
