#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
map<int, map<int, int> > mmm;
int query(int a, int b){
if (a==b)return 0;
if (!mmm[min(a, b)][max(a, b)])mmm[min(a, b)][max(a, b)]=getDistance(min(a, b), max(a, b))+1;
return mmm[min(a, b)][max(a, b)]-1;
}
int hubDistance(int n, int sub){
mmm.clear();
vector<int> dist(n, 0), dista(n, 0), distb(n, 0);
for (int i=1; i<n; ++i)dist[i]=query(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]=query(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]=query(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 if (dista[i]-(dista[i]+distb[i]-dista[b])/2<distb[i]-(dista[i]+distb[i]-dista[b])/2)d2=distb[i]-(dista[i]+distb[i]-dista[b])/2;
else d=d2=dista[i]-(dista[i]+distb[i]-dista[b])/2;
}
bool diea=0, dieb=0;
if (d!=-1){
vector<int> vect;
int ca=1, cb=1;
for (int i=0; i<n; ++i)if (i!=a&&i!=b){
if (dista[b]+dista[i]-distb[i]<2*d)++ca;
else if (dista[b]+dista[i]-distb[i]>2*d)++cb;
else vect.pb(i);
}
if (ca>n/2||cb>n/2){
diea=1;
goto end;
}
int c=0, count=0, sz=1;
for (int i=0; i<vect.size(); ++i){
if (!count)count=1, c=vect[i];
else if (query(vect[i], c)!=dista[vect[i]]+dista[c]-2*d)++count;
else --count;
}
for (int i=0; i<vect.size(); ++i){
if (vect[i]!=c&&query(vect[i], c)!=dista[vect[i]]+dista[c]-2*d)++sz;
if (sz>n/2){
diea=1;
goto end;
}
}
}
if (d2!=-1){
vector<int> vect;
int ca=1, cb=1;
for (int i=0; i<n; ++i)if (i!=a&&i!=b){
if (distb[a]+distb[i]-dista[i]<2*d2)++ca;
else if (distb[a]+distb[i]-dista[i]>2*d2)++cb;
else vect.pb(i);
}
if (ca>n/2||cb>n/2){
dieb=1;
goto end;
}
int c=0, count=0, sz=1;
for (int i=0; i<vect.size(); ++i){
if (!count)count=1, c=vect[i];
else if (query(vect[i], c)!=distb[vect[i]]+distb[c]-2*d2)++count;
else --count;
}
for (int i=0; i<vect.size(); ++i){
if (vect[i]!=c&&query(vect[i], c)!=distb[vect[i]]+distb[c]-2*d2)++sz;
if (sz>n/2){
dieb=1;
goto end;
}
}
}
end:;
if (diea&&dieb&&d!=-1&&d2!=-1)return -ans;
if (diea&&d2==-1)return -ans;
if (dieb&&d==-1)return -ans;
return ans;
}
