#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int dd[200][200], d1[200], d2[200];
mt19937 rng(69420);
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;
ans=min(ans, max(dl, dr));
vv.emplace_back(dl, dr);
}
if (sub<=2) 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());
int cnt=0;
for (auto &ii:vv) if (max(ii.first, ii.second)==ans) ++cnt;
int mx=N/2;
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);
}
if (szl>mx || szr>mx) continue;
vector<pair<int, int>> subtree;
if (sub==4){
if (child.size()) subtree.emplace_back(child[0], child.size());
}else{
shuffle(child.begin(), child.end(), rng);
int sum=szl+szr;
while (child.size()){
vector<int> nc;
subtree.emplace_back(child[0], 0);
for (int i:child){
bool check=0;
int ff=GetDistance(i, subtree.back().first);
int common=(d1[i]+d1[subtree.back().first]-ff-ii.first*2)/2;
if (common){
++subtree.back().second;
check=1;
}else nc.push_back(i);
}
if (subtree.back().second>N/2) break;
sum+=subtree.back().second;
if (sum>=N-N/2) break;
}
}
bool check=szl<=mx && szr<=mx;
for (auto &i:subtree) check&=i.second<=mx;
if (check) return ans;
}
return -ans;
}
