#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int hubDistance(int N, int sub) {
vector<int> q(N);
for(int i=1;i<N;i++){
q[i]=getDistance(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]=getDistance(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]=getDistance(b,i);
}
vector<int> r(N, 1e9), h(N, 1e9);
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;
for(auto [key, v]:mp){
pref+=v.size();
if(pref>N/2){
cand=key;
break;
}
}
/* 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(getDistance(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;
}
return -R;
}
