#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
vector<int>root;
vector<int>siz;
int mxsiz=1;
dsu(int n){
root=vector<int>(n);
iota(root.begin(),root.end(),0);
siz=vector<int>(n,1);
}
int findRoot(int x){
if(x==root[x])
return x;
return root[x]=findRoot(root[x]);
}
bool unite(int x, int y){
x=findRoot(x);
y=findRoot(y);
if(x==y)
return 0;
if(siz[x]<siz[y])
swap(x,y);
siz[x]+=siz[y];
root[y]=x;
mxsiz=max(mxsiz,siz[x]);
return 1;
}
};
int hubDistance(int n, int sub) {
//int R = getDistance(0,1);
int dist[n][n];
for(int i = 0;i<n;i++){
fill(dist[i],dist[i]+n,0);
}
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
dist[i][j]=dist[j][i]=getDistance(i,j);
}
}
int ans = 2e9;
unordered_map<int,array<int,3>>mxs;
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
for(int k = j+1;k<n;k++){
int dists[n];
int a = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[j][k];
int b = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[i][k];
int c = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[i][j];
for(int l = 0;l<n;l++){
dists[l]=max({dist[i][l]-a,dist[j][l]-b,dist[k][l]-c});
}
ans=min(ans,*max_element(dists,dists+n));
if(ans==*max_element(dists,dists+n)){
mxs[ans]={i,j,k};
}
}
}
}
bool wor = 0;
array<int,3>aa=mxs[ans];
int i,j,k;
i=aa[0];
j=aa[1];
k=aa[2];
int dists[n];
int a = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[j][k];
int b = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[i][k];
int c = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[i][j];
for(int l = 0;l<n;l++){
dists[l]=max({dist[i][l]-a,dist[j][l]-b,dist[k][l]-c});
}
if(ans==*max_element(dists,dists+n)){
//valid.
//count out now
dsu ds(n);
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
if(dists[i]+dists[j]>dist[i][j]){
ds.unite(i,j);
}
}
}
if(ds.mxsiz<=n/2){
wor=1;
}
}
if(!wor)
ans=-ans;
return ans;
}
