#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
int getDistance(int i, int j);
ll calc(ll x, ll d1, ll y, ll d2, vector<vector<ll>>&dis, ll N)
{
ll i, r=max(d1,d2), d;
for(i=0; i<N; i++)
{
if(x==i||y==i)
continue;
d=max(dis[x][i]-d1,d=dis[y][i]-d2);
r=max(d,r);
}
return r;
}
int hubDistance(int N, int sub)
{
vector<vector<ll>>dis(N,vector<ll>(N,0));
ll i, j, k, d, R=LLONG_MAX;
for(i=0; i<N; i++)
{
for(j=i+1; j<N; j++)
{
dis[j][i]=dis[i][j]=getDistance(i,j);
}
}
for(i=0; i<N; i++)
{
for(j=i+1; j<N; j++)
{
for(k=j+1; k<N; k++)
{
d=(dis[i][j]+dis[i][k]-dis[j][k])/2;
R=min(R,calc(i,d,j,dis[i][j]-d,dis, N));
}
}
}
return R;
}
