#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
const int maxn=110;
map<pi,int> mem;
int query(int i, int j) {
if (mem[{i,j}]) {
return mem[{i,j}];
}
if (mem[{j,i}]) {
return mem[{j,i}];
}
if (i==j) {
return 0;
}
return mem[{i,j}]=getDistance(i,j);
}
int hubDistance(int n, int sub) {
mem.clear();
int i=1;
for (int k=0; k<n; k++) {
if (query(0,k)>query(0,i)) {
i=k;
}
}
int j=0;
for (int k=0; k<n; k++) {
if (query(i,k)>query(i,j)) {
j=k;
}
}
int d=query(i,j);
int ans=2e9;
bool has=0;
map<int,vi> dst;
for (int k=0; k<n; k++) {
int tdst=(query(i,0)+query(i,k)-query(0,k))/2;
dst[tdst].pb(k);
ans=min(ans,max(tdst,d-tdst));
}
int a=0, b=0, c=n;
for (auto [tdst,inds]:dst) {
c-=inds.size();
b=inds.size();
if (max(tdst,d-tdst)==ans && a<=n/2 && c<=n/2) {
if (b<=n/2) {
has=1;
break;
}
else {
vi in(n,0);
for (auto t:inds) {
in[t]=1;
}
vi gr,oth;
for (int k=0; k<n; k++) {
if (!oth.size()) {
oth.pb(k);
}
else if (in[k] && in[oth.back()] && (query(i,k)+query(i,oth.back())-query(k,oth.back()))/2!=tdst) {
gr.pb(k);
}
else {
oth.pb(k);
if (gr.size()) {
oth.pb(gr.back());
gr.pop_back();
}
}
}
int t=oth.back();
while (oth.size()) {
if (in[t] && in[oth.back()] && (query(i,t)+query(i,oth.back())-query(t,oth.back()))/2!=tdst) {
if (oth.size()==1) {
gr.pb(oth.back());
oth.pop_back();
}
else {
oth.pop_back();
oth.pop_back();
}
}
else {
oth.pop_back();
if (!gr.size()) {
break;
}
gr.pop_back();
}
}
if (!gr.size()) {
has=1;
break;
}
}
}
a+=inds.size();
}
return (has?ans:-ans);
}
