#include "towns.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int mp[115][115];
int s,t,d; // 直徑兩端點
vector<int>up(115),ds(115);
int query(int a,int b){
if (a==b) return 0;
if (!mp[a][b]){
int dis=getDistance(a,b);
assert(dis!=0);
mp[a][b]=dis;
mp[b][a]=dis;
}
return mp[a][b];
}
bool check(int N,int dis,vector<pair<pii,int> >now){
vector<int>to_mid(115,0),sz(115,0);
for (int i=0;i<now.size();i++){
int a=now[i].y;
if (now[i].x.x<dis) to_mid[a]=dis-now[i].x.x+now[i].x.y;
else to_mid[a]=now[i].x.x-dis+now[i].x.y;
}
int num=1,alive=0;
for (int i=1;i<N;i++){
if (!num){
alive=i; num=1; sz[alive]++;
continue;
}
else {
int a=now[i].y,b=now[alive].y;
if (to_mid[a]+to_mid[b]==query(a,b)){
num--;
sz[i]++;
}
else num++,sz[alive]++;
}
}
if (num<=0) return 1;
num=0;
for (int i=0;i<N;i++){
if (!sz[i]) continue;
int a=now[i].y,b=now[alive].y;
if (query(a,b)==to_mid[a]+to_mid[b])
num-=sz[i];
else num+=sz[i];
}
return num<=0;
}
int hubDistance(int N, int sub) {
for (int i=0;i<=N;i++){
for (int j=0;j<=N;j++)
mp[i][j]=0;
}
s=0; t=0; d=0;
up.resize(N+1,0); ds.resize(N+1,0);
d=-1;
for (int i=1;i<N;i++){
if (d<query(0,i)){
d=query(0,i);
s=i;
}
}
d=-1;
for (int i=0;i<N;i++){
if (d<query(s,i)){
d=query(s,i);
t=i;
}
}
up[s]=0; up[t]=0;
int ans=1e9;
vector<pair<pii,int> >all;
for (int i=0;i<N;i++){
int a=query(0,s);
int b=query(0,i);
int c=query(i,s);
up[i]=(b-a+c)/2;
ds[i]=c-up[i];
all.push_back({{ds[i],up[i]},i});
ans=min(ans,max(d-ds[i],ds[i]));
}
sort(all.begin(),all.end());
if (sub<=2) return ans;
int md=(N-1)/2;
if (max(all[md].x.x,d-all[md].x.x)==ans){
bool flag=check(N,all[(N-1)/2].x.x,all);
if (flag) return ans;
return -ans;
}
md=N/2;
if (max(all[md].x.x,d-all[md].x.x)==ans){
bool flag=check(N,all[N/2].x.x,all);
if (flag) return ans;
return -ans;
}
return -ans;
}
