#include "towns.h"
#include <bits/stdc++.h>
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;
int hubDistance(int N, int sub)
{
vector<int> dis(N,0),a(N,0),b(N,0);
int x,y,R=INF,RR;
for(int i=1;i<N;++i)
dis[i]=getDistance(0,i);
x=max_element(ALL(dis))-dis.begin();
for(int i=0;i<N;++i)
if(i!=x)
a[i]=getDistance(x,i);
y=max_element(ALL(a))-a.begin();
for(int i=0;i<N;++i)
if(i!=y)
b[i]=getDistance(y,i);
for(int i=0;i<N;++i)
R=min(R,abs(a[i]-b[i]));
RR=(a[y]+R)/2;
if(sub==1||sub==2||sub==4)
{
int cnt[3]={};
for(int i=0;i<N;++i)
if(abs(a[i]-b[i])==R) ++cnt[0];
else if(a[i]<b[i]) ++cnt[1];
else ++cnt[2];
if(cnt[0]<=N/2&&cnt[1]<=N/2&&cnt[2]<=N/2) return RR;
return -RR;
}
else
{
vector<int> chk[2];
int cnt[2]={};
for(int i=0;i<N;++i)
if(abs(a[i]-b[i])==R)
if(a[i]<b[i]) chk[0].pb(i);
else chk[1].pb(i);
else if(a[i]<b[i]) ++cnt[0];
else ++cnt[1];
if(chk[0].empty())
chk[0].swap(chk[1]),swap(cnt[0],cnt[1]);
if(chk[1].empty())
if(cnt[0]>N/2||cnt[1]>N/2) return -RR;
else;
else if(cnt[0]+chk[0].size()>N/2||cnt[1]+chk[1].size()>N/2)
return -RR;
while(chk[0].size())
{
int t=0;
vector<int> nxt;
for(int i:chk[0])
if(getDistance(i,chk[0][0])<max(a[chk[0][0]],b[chk[0][0]])-RR+max(a[i],b[i])-RR)
++t;
else
nxt.pb(i);
if(t>N/2) return -RR;
nxt.swap(chk[0]);
}
while(chk[1].size())
{
int t=0;
vector<int> nxt;
for(int i:chk[1])
if(getDistance(i,chk[1][0])<max(a[chk[1][0]],b[chk[1][0]])-RR+max(a[i],b[i])-RR)
++t;
else
nxt.pb(i);
if(t>N/2) return -RR;
nxt.swap(chk[1]);
}
return RR;
}
}
