#include "towns.h"
#include "bits/stdc++.h"
using namespace std;
map <pair <int, int>, int> mp;
int distance(int i, int j) {
if(i == j) return 0;
if(i > j) swap(i, j);
if(mp.find(make_pair(i, j)) != mp.end()) return mp[make_pair(i, j)];
return mp[make_pair(i, j)] = getDistance(i, j);
}
int hubDistance(int N, int sub) {
mp.clear();
int opt = 0;
int dist = 0;
for(int i = 1; i < N; i++) {
int d = distance(0, i);
if(d > dist) {
dist = d;
opt = i;
}
}
int P = 0, Q = opt;
dist = 0;
for(int i = 0; i < N; i++) {
if(i == opt) continue;
int d = distance(opt, i);
if(d > dist) {
dist = d;
P = i;
}
}
map <int, int> dist_chain;
int R = distance(P, Q);
for(int i = 0; i < N; i++) {
int lca_dist = (distance(i, P) + distance(i, Q) - distance(P, Q)) / 2;
int p_dist = distance(i, P) - lca_dist;
R = min(R, max(p_dist, distance(P, Q) - p_dist));
dist_chain[i] = lca_dist;
}
int root = 0;
for(int i = 0; i < N; i++) {
int lca_dist = (distance(i, P) + distance(i, Q) - distance(P, Q)) / 2;
int p_dist = distance(i, P) - lca_dist;
int val = max(p_dist, distance(P, Q) - p_dist);
if(val == R && distance(i, P) + distance(i, Q) == distance(P, Q)) {
root = i;
break;
}
}
vector <int> unmatched;
for(int i = 0; i < N; i++) {
if(i == root) continue;
if(unmatched.empty()) {
unmatched.push_back(i);
continue;
}
int d1 = abs(distance(P, i) - distance(P, root)) + dist_chain[i];
int d2 = abs(distance(P, unmatched.back()) - distance(P, root)) + dist_chain[unmatched.back()];
int d3 = distance(i, unmatched.back());
if(d1 + d2 == d3) {
unmatched.pop_back();
} else {
unmatched.push_back(i);
}
}
if(unmatched.empty()) return R;
int piv = unmatched.back();
int cnt = 0;
for(int i = 0; i < N; i++) {
if(i == root) continue;
int d1 = abs(distance(P, i) - distance(P, root)) + dist_chain[i];
int d2 = abs(distance(P, piv) - distance(P, root)) + dist_chain[piv];
int d3 = distance(i, piv);
if(d1 + d2 != d3) {
++cnt;
}
}
if(cnt > (N / 2)) R *= -1;
return R;
}
