#include "towns.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
int hubDistance(int N, int sub)
{
ll D;
vector<ll> d0; d0.pb(0); REP(i,1,N) {d0.pb(getDistance(0,i));}
ll A = (ll) (max_element(whole(d0)) - d0.begin());
vector<ll> d1,d2;
REP(i,0,N) {if(i==A) {d1.pb(0);} else {d1.pb(getDistance(A,i));}}
ll B = (ll) (max_element(whole(d1)) - d1.begin());
D = *max_element(whole(d1));
REP(i,0,N) {if(i==B) {d2.pb(0);} else {d2.pb(getDistance(B,i));}}
set<ll> s;
REP(i,0,N) {s.insert((d1[i]-d2[i]+D)/2LL);}
unordered_map<ll,ll> m; set<ll>::iterator it = s.begin(); ll ind=0LL;
ll R=D; vector<ll> poss_ind;
while(it!=s.end())
{
R=min(R,max(*it,D-*it));
m[*it]=ind; ind++; it++;
}
it=s.begin(); ind=0;
while(it!=s.end())
{
if(max(*it,D-*it)==R) {poss_ind.pb(ind);}
ind++; it++;
}
vector<pl> p; //pairs {diameter projection index, distance to projection}
REP(i,0,N)
{
ll val1 = m[(d1[i]-d2[i]+D)/2LL];
ll val2 = (d1[i]+d2[i]-D)/2LL;
p.pb({val1,val2});
}
vector<ll> oc; REP(i,0,s.size()) {oc.pb(0LL);}
REP(i,0,N) {oc[p[i].ff]++;}
ll hub = poss_ind[0];
ll S = s.size();
ll sum1,sum2;
if(poss_ind.size()==2)
{
sum1=0LL;sum2=0LL;
REP(i,poss_ind[0]+1,S) {sum1+=oc[i];}
REP(i,0,poss_ind[1]) {sum2+=oc[i];}
if(2*sum1==N) {return R;}
else if(2*sum1>N) {hub=poss_ind[1];}
}
sum1=0LL;sum2=0LL;
REP(i,0,hub) {sum1+=oc[i];} REP(i,hub+1,S) {sum2+=oc[i];}
if(2*sum1>N || 2*sum2>N || 2*oc[hub]>N) {return -R;}
return R;
}
