#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=110;
int D[MAXN][MAXN];
int hubDistance(int N, int sub) {
memset(D, -1, sizeof(D));
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i==j)D[i][j]=0;
if(D[i][j]==-1){
D[i][j]=getDistance(i,j);
D[j][i]=D[i][j];
}
}
}
int b=0, c=0, s1=-1, s2=-1;
for(int i=0;i<N;i++){
if(D[0][i]>s1){
b=i;
s1=D[0][i];
}
}
for(int i=0;i<N;i++){
if(D[b][i]>s2){
c=i;
s2=D[b][i];
}
}
int diam=D[b][c], r=1e9;
map<int, vector<int>> mp;
vector<int> h(N);
for(int i=0;i<N;i++){
int to_diam=(D[i][b]+D[b][c]-D[i][c])/2;
int mx=max(diam-to_diam, to_diam);
r=min(r, mx);
mp[to_diam].push_back(i);
h[i]=D[i][b]-to_diam;
}
//cout<<b<<" "<<c<<endl;
/* for(int i=0;i<N;i++){
cout<<h[i]<<" ";
}
cout<<endl; */
bool exist=false;
int lef=N, rig=0;
for(auto [cand,v]:mp){
lef-=v.size();
if((cand==r||diam-cand==r)&&(lef<=N/2&&rig<=N/2)){
if(v.size()<=N/2)exist=true;
vector<int> treeSizes;
int maxSubtree=0;
for(auto x:v){
int curSubtree=0;
for(auto y:v){
if(h[x]+h[y]!=D[x][y]){
curSubtree++;
}
}
maxSubtree=max(maxSubtree, curSubtree);
}
if(maxSubtree<=N/2){
exist=true;
}
}
rig+=v.size();
}
if(exist)return r;
return -r;
}
