#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, dis[y][i] - d2);
r = max(d, r);
}
return r;
}
ll tam(ll x, ll d1, ll y, ll d2, vector<vector<ll>> &dis, ll N)
{
ll i, r = max(d1, d2), d, j, ac, num;
vector<set<ll>> un(N);
for (i = 0; i < N; i++)
un[i].insert(i);
vector<ll> v;
v.pb(0);
for (i = 1; i < N; i++)
{
if (sz(v) == 0)
v.pb(i);
else
{
d = max(dis[x][i] - d1, dis[y][i] - d2);
j = v.back();
ac = max(dis[x][j] - d1, dis[y][j] - d2);
if (dis[i][j] - d != ac)
{
v.pop_back();
i--;
}
else
v.pb(i);
}
}
if (sz(v) == 0)
return N / 2;
num = v.back();
v.resize(0);
v.pb(num);
d = max(dis[x][num] - d1, dis[y][num] - d2);
for (i = 0; i < N; i++)
{
if (i == num)
continue;
ac = max(dis[x][i] - d1, dis[y][i] - d2);
if (dis[i][j] - d == ac)
v.pb(i);
}
return sz(v);
}
int hubDistance(int N, int sub)
{
vector<vector<ll>> dis(N, vector<ll>(N, 0));
vector<vector<ll>> v;
ll i, j, k, d, R = LLONG_MAX, r;
vector<bool> vis(N, 0);
vis[0] = 1;
for (i = 1; i < N; i++)
dis[0][i] = dis[i][0] = getDistance(0, i);
ll ma = 0, mi = 0, mj = 0;
for (i = 0; i < N; i++)
{
if (ma < dis[i][0])
{
ma = dis[i][0];
mi = i;
}
}
vis[mi] = 1;
for (i = 0; i < N; i++)
if (mi != i)
dis[mi][i] = dis[i][mi] = getDistance(mi, i);
ma = 0;
for (i = 0; i < N; i++)
{
if (ma < dis[i][mi])
{
ma = dis[i][mi];
mj = i;
}
}
if (vis[mj] == 0)
{
for (i = 0; i < N; i++)
if (mj != i)
dis[mj][i] = dis[i][mj] = getDistance(mj, i);
}
i = mi;
j = mj;
for (k = 0; k < N; k++)
{
if (k == j || k == i)
continue;
d = (dis[i][j] + dis[i][k] - dis[j][k]) / 2;
r = calc(i, d, j, dis[i][j] - d, dis, N);
if (R > r)
{
R = r;
v.resize(0);
v.pb({i, d, j, dis[i][j] - d});
}
else if (R == r)
{
v.pb({i, d, j, dis[i][j] - d});
}
}
mi = tam(v[0][0], v[0][1], v[0][2], v[0][3], dis, N);
for (i = 1; i < sz(v); i++)
{
d = max(dis[v[i][0]][v[0][0]] - v[i][1], dis[v[i][2]][v[0][0]] - v[i][3]);
if (d == v[0][1])
continue;
mi = min(tam(v[i][0], v[i][1], v[i][2], v[i][3], dis, N), mi);
break;
}
if (mi > N / 2)
R = -R;
return R;
}
