#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());
}
}
bool has=0;
for (int i=0; i<n && !has; i++) {
for (int j=i+1; j<n && !has; j++) {
map<int,int> dst;
map<int,vi> adj;
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);
adj[(dist[i][k]+dist[i][j]-dist[j][k])/2].pb(k);
}
int val=0;
int prv=0;
int sum=1;
map<int,int> nw;
map<int,int> cnts;
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];
cnts[pt->fi]=sum;
sum+=adj[pt->fi].size();
}
sum=1;
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]);
cnts[pt->fi]=max(sum,cnts[pt->fi]);
sum+=adj[pt->fi].size();
if (ans==pt->se) {
bool ok=1;
ok&=(cnts[pt->fi]<=n/2);
for (int l=0; l<adj[pt->fi].size() && ok; l++) {
int tcnt=1;
for (int m=0; m<adj[pt->fi].size(); m++) {
if (dist[l][m]!=(dist[i][l]+dist[j][l]-dist[i][j])/2+(dist[i][m]+dist[j][m]-dist[i][j])/2) {
tcnt++;
}
}
ok&=tcnt<=n/2;
}
has|=ok;
}
} while (pt!=dst.begin());
}
}
return (has?ans:-ans);
}
