#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int dd[200][200], d1[200], d2[200];
int GetDistance(int u, int v){
// if (u==v) return 0;
// if (dd[u][v]) return dd[u][v];
int tmp=getDistance(u, v);
// dd[u][v]=tmp; dd[v][u]=tmp;
return tmp;
}
int hubDistance(int N, int sub) {
memset(dd, 0, sizeof dd);
memset(d1, 0, sizeof d1);
memset(d2, 0, sizeof d2);
int u=0, dis=0;
for (int i=1; i<N; ++i){
int d=GetDistance(0, i);
if (d>dis){
dis=d;
u=i;
}
}
dis=0;
int v=u;
for (int i=0; i<N; ++i) if (i!=u){
int d=GetDistance(u, i);
d1[i]=d;
if (d>dis){
dis=d;
v=i;
}
}
int ans=1e9;
vector<pair<int, int>> vv;
for (int i=0; i<N; ++i) if (i!=u && i!=v){
d2[i]=GetDistance(v, i);
int common=(d1[i]+d2[i]-dis)/2;
int dl=d1[i]-common, dr=d2[i]-common;
// if (!common){
ans=min(ans, max(dl, dr));
vv.emplace_back(dl, dr);
// }
}
return ans;
d1[u]=d2[v]=0;
d1[v]=d2[u]=dis;
sort(vv.begin(), vv.end());
vv.resize(unique(vv.begin(), vv.end())-vv.begin());
for (auto &ii:vv) if (max(ii.first, ii.second)==ans){
int szl=0, szr=0;
vector<int> child;
for (int i=0; i<N; ++i){
int common=(d1[i]+d2[i]-dis)/2;
int dl=d1[i]-common, dr=d2[i]-common;
if (dl<ii.first) ++szl;
else if (dl>ii.first) ++szr;
else child.push_back(i);
}
vector<pair<int, int>> subtree;
for (int i:child){
bool check=0;
for (auto &j:subtree){
int ff=GetDistance(i, j.first);
int common=d1[i]+d1[j.first]-ff-ii.first*2;
if (common){
++j.second;
check=1;
break;
}
}
if (!check) subtree.emplace_back(i, 1);
}
int mx=N/2;
bool check=szl<=mx && szr<=mx && (int)child.size()<=mx;
for (auto &i:subtree) check&=i.second<=mx;
if (check) return ans;
}
return -ans;
}
