#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;
map <int, int> pos_chain;
int R = distance(P, Q);
int radius_pos = -1;
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);
R = min(R, val);
dist_chain[i] = lca_dist;
pos_chain[i] = p_dist;
}
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(R == val) {
int l = 0;
int r = 0;
for(int ii = 0; ii < N; ii++) {
if(pos_chain[ii] < p_dist) ++l;
if(pos_chain[ii] > p_dist) ++r;
}
if(l > (N / 2) || r > (N / 2)) continue;
radius_pos = p_dist;
}
}
if(radius_pos < 0) return -R;
vector <int> unmatched;
// cout << l << ' ' << r << endl;
// cout << radius_pos << endl;
// for(int i = 0; i < N; i++) {
// cout << i << ' ' << pos_chain[i] << ' ' << endl;
// }
// exit(0);
for(int i = 0; i < N; i++) {
if(pos_chain[i] != radius_pos) continue;
if(unmatched.empty()) {
unmatched.push_back(i);
}
int x = i;
int y = unmatched.back();
int d = distance(x, y);
int lca_dist = (distance(P, x) + distance(P, y) - distance(x, y)) / 2;
int meet = distance(P, x) - lca_dist;
if(meet != dist_chain[x]) {
unmatched.push_back(x);
} else {
unmatched.pop_back();
}
}
if(unmatched.empty()) return R;
int piv = unmatched.back();
// cout << "piv: " << piv << endl;
int cnt = 0;
for(int i = 0; i < N; i++) {
if(pos_chain[i] != radius_pos) continue;
int x = i;
int y = piv;
int d = distance(x, y);
int lca_dist = (distance(P, x) + distance(P, y) - distance(x, y)) / 2;
int meet = distance(P, x) - lca_dist;
if(meet != dist_chain[x]) {
++cnt;
// cout << x << endl;
}
}
if(cnt > (N / 2)) R *= -1;
return R;
}
