#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;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int getRandomInt(int l, int r) {
std::uniform_int_distribution<int> dist(l, r);
return dist(rng);
}
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, a, b, ra;
vector<vector<ll>> v, nv, die;
for (i = 0; i < N; i++)
v.pb({i});
while (sz(v) > 1)
{
if (sz(v) % 2 != 0)
{
die.pb(v.back());
v.pop_back();
}
while(sz(v)>1)
{
a=getRandomInt(0, sz(v) - 1);
d = max(dis[x][a] - d1, dis[y][a] - d2);
vector<ll>ins=v[a];
v.erase(v.begin()+a);
b=getRandomInt(0, sz(v) - 1);
ac = max(dis[x][b] - d1, dis[y][b] - d2);
if (dis[a][b] == -1)
dis[a][b] = dis[b][a] = getDistance(a, b);
if (dis[x][a]+dis[x][b]-dis[a][b]>2*r)
{
for(auto k:v[b])
ins.pb(k);
nv.pb(ins);
}
else
{
die.pb(ins);
die.pb(v[b]);
}
v.erase(v.begin()+b);
}
v = nv;
nv.resize(0);
}
if (sz(v) == 0)
return N / 2;
a = v[0][0];
d = max(dis[x][a] - d1, dis[y][a] - d2);
for (i = 0; i < sz(die); i++)
{
b = die[i][0];
ac = max(dis[x][b] - d1, dis[y][b] - d2);
if (dis[a][b] == -1)
dis[a][b] = dis[b][a] = getDistance(a, b);
if (dis[x][a]+dis[x][b]-dis[a][b]>2*r)
for (auto k : die[i])
v[0].pb(k);
}
return sz(v[0]);
}
pair<ll,ll>nods(ll x, ll d1, ll y, ll d2, vector<vector<ll>> &dis, ll N)
{
pair<ll,ll>p= {1,1};
ll i, ac;
for(i=0; i<N; i++)
{
if(i==x||i==y)
continue;
ac = max(dis[x][i] - d1, dis[y][i] - d2);
if(dis[x][i]-d1!=ac)
p.fr++;
else if(dis[y][i]-d2!=ac)
p.se++;
}
return p;
}
int hubDistance(int N, int sub)
{
vector<vector<ll>> dis(N, vector<ll>(N, -1));
vector<vector<ll>> v;
ll i, j, k, d, R = LLONG_MAX, r;
for(i=0; i<N; i++)
dis[i][i]=0;
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);
mj=0;
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});
}
}
pair<ll,ll>p=nods(v[0][0], v[0][1], v[0][2], v[0][3], dis, N);
if(p.fr>N/2)
mi=N;
else if(p.se>N/2)
mi=N;
else if(p.se==N/2||p.fr==N/2)
mi=N/2;
else if(p.se+p.fr>=N/2)
mi=N/2;
else
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;
p=nods(v[i][0], v[i][1], v[i][2], v[i][3], dis, N);
if(p.fr>N/2)
mi=min(mi,1ll*N);
else if(p.se>N/2)
mi=min(mi,1ll*N);
else if(p.se==N/2||p.fr==N/2)
mi=min(mi,1ll*N/2);
else if(p.se+p.fr>=N/2)
mi=min(mi,1ll*N/2);
else
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;
}
