#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
const int MAXN = 120;
const int INF = 0x3f3f3f3f3f3f3f3f;
int dist[MAXN][MAXN];
int query(int a, int b) {
if (a == b) return 0;
if (a > b) swap(a, b);
if (dist[a][b]) return dist[a][b];
return (dist[a][b] = getDistance(a, b));
}
int32_t hubDistance(int32_t n, int32_t sub) {
memset(dist, 0, sizeof dist);
// achar diametro
pii mx = {0, 0};
for (int i = 1; i < n; i++) mx = max(mx, {query(1, i), i});
int p1 = mx.se;
mx = {0, 0};
for (int i = 0; i < n; i++) mx = max(mx, {query(p1, i), i});
int p2 = mx.se, diam = mx.fr;
int mi = INF;
vector<array<int, 2>> ab(n);
for (int i = 0; i < n; i++) {
int apc = query(i, p1);
int bpc = query(i, p2);
int amc = (apc - bpc);
int a = (amc + diam)/2, b = (diam - a);
ab[i] = {a, b};
mi = min(mi, max(a, b));
}
// dividir em halfs
vector<int> h(2), c(2);
for (int i = 0; i < n; i++) {
int lado = 0;
if (ab[i][0] > ab[i][1]) lado = 1;
if (max(ab[i][0], ab[i][1]) == mi) {
c[lado]++;
//cout << i << " " << lado << "\n";
}
else h[lado]++;
}
// show, agora vamo ver se tem o centro bomzao
int q1, q2, q3;
bool ok = 0;
// testar com centro 1
q1 = h[0], q2 = (h[1] + c[1]), q3 = c[0];
if (max({q1, q2, q3}) <= (n/2)) ok = 1;
// testar com centro 2
q1 = (h[0] + c[0]), q2 = h[1], q3 = c[1];
if (max({q1, q2, q3}) <= (n/2)) ok = 1;
//cout << q1 << " " << q2 << " " << q3 << "\n";
// res
if (!ok) mi *= -1;
return mi;
}
