#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];
}
}
}
vector<int> q(N);
for(int i=1;i<N;i++){
q[i]=D[0][i];
}
int a=max_element(q.begin(), q.end())-q.begin();
vector<int> w(N);
for(int i=0;i<N;i++){
if(i==a)continue;
w[i]=D[a][i];
}
int b=max_element(w.begin(), w.end())-w.begin();
vector<int> e(N);
// Tengo el diametro, ahora necesito computar para cada nodo su distancia a uno de ellos
for(int i=0;i<N;i++){
if(i==b)continue;
e[i]=D[b][i];
}
vector<int> r(N, 1e9), h(N);
map<int, vector<int>> mp;
for(int i=0;i<N;i++){
if(i==a||i==b)continue;
int d1=((e[a]+e[i])-w[i])/2;
int d2=((e[a]+w[i])-e[i])/2;
mp[d1].push_back(i);
h[i]=e[i]-d1;
r[i]=max(d1, d2);
}
int R=*min_element(r.begin(), r.end());
/* if(sub<=2)return R; */
int pref=0, cand=-1, last;
for(auto [key, v]:mp){
pref+=v.size();
if(pref+1>N/2){
cand=key;
break;
}
last=key;
}
/* cout<<a<<" "<<b<<endl;
cout<<cand<<endl; */
if(cand==-1){
return R;
}
auto v=mp[cand];
/* for(int i=0;i<(int)v.size();i++)cout<<v[i]<<" ";
cout<<endl;
for(int i=0;i<(int)v.size();i++)cout<<h[v[i]]<<" ";
cout<<endl; */
vector<int> treeSizes;
vector<bool> vis(N, false);
for(int i=0;i<(int)v.size();i++){
int x=v[i];
if(vis[x])continue;
vis[x]=true;
int currTree=1;
for(int j=0;j<(int)v.size();j++){
int y=v[j];
if(vis[y])continue;
if(D[x][y]!=h[x]+h[y]){
vis[y]=true;
currTree++;
}
}
treeSizes.push_back(currTree);
}
/* for(int i=0;i<(int)treeSizes.size();i++)cout<<treeSizes[i]<<" ";
cout<<endl; */
bool ok=true;
for(int i=0;i<(int)treeSizes.size();i++){
if(treeSizes[i]>N/2){
ok=false;
break;
}
}
if(ok&&N-pref-1<=N/2){
return R;
}
v=mp[last];
treeSizes.resize(0);
vis.resize(N, false);
for(int i=0;i<(int)v.size();i++){
int x=v[i];
if(vis[x])continue;
vis[x]=true;
int currTree=1;
for(int j=0;j<(int)v.size();j++){
int y=v[j];
if(vis[y])continue;
if(D[x][y]!=h[x]+h[y]){
vis[y]=true;
currTree++;
}
}
treeSizes.push_back(currTree);
}
ok=true;
for(int i=0;i<(int)treeSizes.size();i++){
if(treeSizes[i]>N/2){
ok=false;
break;
}
}
if(ok&&N-pref-1<=N/2){
return R;
}
return -R;
}
