#include <bits/stdc++.h>
#include "towns.h"
#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define vec vector
using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
map<pii,int> mp;
int dist(int i,int j){
if(i==j || mp.count({i,j}))
return mp[{i,j}];
mp[{i,j}]=mp[{j,i}]=getDistance(i,j);
return mp[{i,j}];
}
int n;
int getcnt(int sub){
if(sub==5)
return 2;
if(sub==1 || sub==3)
return n;
return 0;
}
int hubDistance(int n, int sub){
int v,u;
::n=n;
mp.clear();
srand(n*sub);
int ft=rand()%n;
vec<int> r(n);
{
// vec<int> r(n);
for(int i=0;i<n;i++) r[i]=dist(ft,i);
v=max_element(all(r))-r.begin();
}
vec<int> r1(n),r2(n);
for(int i=0;i<n;i++) r1[i]=dist(v,i);
u=max_element(all(r1))-r1.begin();
vec<pii> cand;
vec<int> d1(n),d2(n);
vec<int> rasts;
vec<int> pref,suf;
vec<int> c1,c2;
map<int,int> mp;
map<int,int> cntk;
for(int i=0;i<n;i++){
// r2[i]=dist(u,i);
int s=(r1[i]+r1[ft]-r[i]);
assert((s%2)==0);
s/=2;
d2[i]=s;
d1[i]=r1[i]-s;
umax(mp[d2[i]],d1[i]);
++cntk[d2[i]];
}
for(auto &z : mp)
rasts.pb(z.f),pref.pb(z.s);
for(auto &z : cntk) c1.pb(z.s);
suf=pref;c2=c1;
for(int i=1;i<sz(rasts);i++)
umax(pref[i],pref[i-1]+rasts[i]-rasts[i-1]),c1[i]+=c1[i-1];
for(int i=sz(rasts)-2;i>=0;i--)
umax(suf[i],suf[i+1]+rasts[i+1]-rasts[i]),c2[i]+=c2[i+1];
int mn=1e9;
for(int i=0;i<sz(rasts);i++){
umin(mn,max(pref[i],suf[i]));
}
int cen = -1;
int ok=0;
for(int i=0;i<sz(rasts);i++){
if(max(pref[i],suf[i])!=mn) continue;
int f=(i?c1[i-1]:0),s=(i+1==sz(rasts)?0:c2[i+1]);
// int t=c1[i]-f;
if(f<=(n/2) && s<=(n/2))
cen=i;
}
if(cen == -1) return -mn;
auto check=[&](int x,int y){
if(x == y) return 1;
int my=d1[x]+abs(d2[x]-rasts[cen]);
int his=d1[y]+abs(d2[y]-rasts[cen]);
if((my+his)!=dist(x,y)) return 1;
return 0;
};
vec<int> cnt(n);
int mb=0;
int h=0;
map<int,int> ban;
for(int i=0;i<n;i++){
if(d2[i]==d2[cen]){
if(!h) mb=i,ban.clear();
if(check(mb,i)) ++h,++cnt[mb];
else --h,ban[i]=1,cnt[i]=1;
}
}
int cntr=0;
for(int i=0;i<n;i++){
if(d2[i]==d2[cen] && !ban[i] && cnt[i]){
cntr+=(cnt[i]*check(i,mb));
}
}
// int ok=0;
//// cout<<"OK "<<ok<<endl;
if(cntr>(n/2)) mn*=-1;
// cout<<"W "<<mn<<endl;
return mn;
}
/*
3 1
11
0 17 18 20 17 12 20 16 23 20 11
17 0 23 25 22 17 25 21 28 25 16
18 23 0 12 21 16 24 20 27 24 17
20 25 12 0 23 18 26 22 29 26 19
17 22 21 23 0 9 21 17 26 23 16
12 17 16 18 9 0 16 12 21 18 11
20 25 24 26 21 16 0 10 29 26 19
16 21 20 22 17 12 10 0 25 22 15
23 28 27 29 26 21 29 25 0 21 22
20 25 24 26 23 18 26 22 21 0 19
11 16 17 19 16 11 19 15 22 19 0
*/
