#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<int>to_mid(115,0),sz(115,0);
for (int i=0;i<N;i++){
if (ds[i]<dis) to_mid[i]=dis-ds[i]+up[i];
else to_mid[i]=ds[i]-dis+up[i];
}
int num=1,alive=0;
for (int i=1;i<N;i++){
if (!num){
sz[i]=1; num=1; alive=i;
}
else {
if (query(i,alive)==to_mid[i]+to_mid[alive]){
sz[i]++; num--;
}
else num++,sz[alive]++;
}
}
if (num<=0) return 1;
num=0;
for (int i=0;i<N;i++){
if (query(i,alive)==to_mid[i]+to_mid[alive])
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,sz=0,op=-1;
map<pii,int>cnt;
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];
ans=min(ans,max(d-ds[i],ds[i]));
cnt[{ds[i],d-ds[i]}]++;
}
int sol=0;
for (auto [i,c]:cnt){
if (max(i.x,i.y)==ans){
if (sz<=N/2&&c<=N/2&&(N-c-sz)<=N/2)
return ans;
else if (sz<=N/2&&(N-c-sz)<=N/2){
sol=i.x;
}
}
sz+=c;
}
bool flag=check(N,sol);
if (flag) op=1;
return ans*op;
}
