#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;
vector<vi> dist(4*maxn,vi(4*maxn));
int hubDistance(int n, int sub) {
for (int i=0; i<n; i++) {
dist[i][i]=0;
for (int j=i+1; j<n; j++) {
dist[i][j]=getDistance(i,j);
dist[j][i]=dist[i][j];
}
}
int ans=2e9;
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
map<int,int> dst;
for (int k=0; k<n; k++) {
if (k==i || k==j) {
continue;
}
dst[(dist[i][k]+dist[i][j]-dist[j][k])/2]=max(dst[(dist[i][k]+dist[i][j]-dist[j][k])/2],(dist[i][k]+dist[j][k]-dist[i][j])/2);
}
int val=0;
int prv=0;
map<int,int> nw;
for (auto pt=dst.begin(); pt!=dst.end(); pt++) {
val+=pt->fi-prv;
prv=pt->fi;
nw[pt->fi]=max(pt->se,val);
val=nw[pt->fi];
}
prv=dist[i][j];
val=0;
auto pt=dst.end();
do {
pt--;
val+=prv-pt->fi;
prv=pt->fi;
val=max(val,pt->se);
pt->se=max(val,nw[pt->fi]);
ans=min(ans,pt->se);
} while (pt!=dst.begin());
}
}
return ans;
}
