#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
vector<int> dsu, sz;
vector<vector<int> > cant;
int fp(int a){
if (dsu[a]==-1)return a;
return dsu[a]=fp(dsu[a]);
}
void merge(int a, int b){
a=fp(a), b=fp(b);
if (a==b)return;
dsu[a]=b;
sz[b]+=sz[a];
for (auto c:cant[a])cant[b].pb(c);
}
int hubDistance(int n, int sub){
dsu.clear();
sz.clear();
cant.clear();
vector<int> dist(n, 0), dista(n, 0), distb(n, 0);
dsu.resize(n, -1);
sz.resize(n, 1);
cant.resize(n);
for (int i=1; i<n; ++i)dist[i]=getDistance(0, i);
int mx=-1, a=-1, b=-1, ans=INT_MAX/2, d=-1, d2=-1;
for (int i=0; i<n; ++i)if (dist[i]>mx)mx=dist[i], a=i;
for (int i=0; i<n; ++i)if (i!=a)dista[i]=getDistance(a, i);
mx=-1;
for (int i=0; i<n; ++i)if (dista[i]>mx)mx=dista[i], b=i;
for (int i=0; i<n; ++i)if (i!=b)distb[i]=getDistance(b, i);
for (int i=0; i<n; ++i)ans=min(ans, max(dista[i]-(dista[i]+distb[i]-dista[b])/2, distb[i]-(dista[i]+distb[i]-dista[b])/2));
for (int i=0; i<n; ++i)if (max(dista[i]-(dista[i]+distb[i]-dista[b])/2, distb[i]-(dista[i]+distb[i]-dista[b])/2)==ans){
if (dista[i]-(dista[i]+distb[i]-dista[b])/2>distb[i]-(dista[i]+distb[i]-dista[b])/2)d=dista[i]-(dista[i]+distb[i]-dista[b])/2;
else d2=distb[i]-(dista[i]+distb[i]-dista[b])/2;
}
if (d!=-1){
vector<int> vect;
for (int i=0; i<n; ++i)if (i!=a&&i!=b){
if (dista[b]+dista[i]-distb[i]<2*d)merge(i, a);
else if (dista[b]+dista[i]-distb[i]>2*d)merge(i, b);
else vect.pb(i);
}
for (int aa=0; aa<vect.size(); ++aa)for (int bb=aa+1; bb<vect.size(); ++bb){
int i=vect[aa], j=vect[bb];
bool die=0;
for (auto c:cant[fp(i)])if (fp(j)==fp(c))die=1;
for (auto c:cant[fp(j)])if (fp(i)==fp(c))die=1;
if (die||fp(i)==fp(j))continue;
if (getDistance(i, j)==dista[i]+dista[j]-2*d)cant[fp(i)].pb(j), cant[fp(j)].pb(i);
else{
merge(i, j);
if (sz[fp(i)]>n/2)return -ans;
}
}
for (int i=0; i<n; ++i)if (sz[fp(i)]>n/2)return -ans;
}
if (d2!=-1){
dsu.clear();
sz.clear();
cant.clear();
dsu.resize(n, -1);
sz.resize(n, 1);
cant.resize(n);
vector<int> vect;
for (int i=0; i<n; ++i)if (i!=a&&i!=b){
if (dista[b]+dista[i]-distb[i]<2*d2)merge(i, a);
else if (dista[b]+dista[i]-distb[i]>2*d2)merge(i, b);
else vect.pb(i);
}
for (int aa=0; aa<vect.size(); ++aa)for (int bb=aa+1; bb<vect.size(); ++bb){
int i=vect[aa], j=vect[bb];
bool die=0;
for (auto c:cant[fp(i)])if (fp(j)==fp(c))die=1;
for (auto c:cant[fp(j)])if (fp(i)==fp(c))die=1;
if (die||fp(i)==fp(j))continue;
if (getDistance(i, j)==dista[i]+dista[j]-2*d2)cant[fp(i)].pb(j), cant[fp(j)].pb(i);
else{
merge(i, j);
if (sz[fp(i)]>n/2)return -ans;
}
}
for (int i=0; i<n; ++i)if (sz[fp(i)]>n/2)return -ans;
}
return ans;
}
