#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);
vector<int> height(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};
height[i] = (apc - a);
mi = min(mi, max(a, b));
}
// dividir em halfs
vector<int> h(2);
vector<vector<int>> 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].push_back(i);
else h[lado]++;
}
int q = -1;
if (c[0].size() > (n/2)) q = 0;
else if (c[1].size() > (n/2)) q = 1;
if (q != -1) {
vector<int> x = c[q];
int curr = 0, cnt = 0;
for (auto u : x) {
if (cnt == 0) {
curr = u;
cnt = 1;
} else if (query(u, curr) < (height[u] + height[curr])) cnt++;
else cnt--;
}
// curr is the goat
cnt = 0;
for (auto u : x) if (query(u, curr) < (height[u] + height[curr])) cnt++;
if (cnt <= (n/2)) return mi;
else return -mi;
}
// show, agora vamo ver se tem o centro bomzao
int q1, q2;
bool ok = 0;
// testar com centro 1
q1 = h[0], q2 = (h[1] + c[1].size());
if (max({q1, q2}) <= (n/2)) ok = 1;
// testar com centro 2
q1 = (h[0] + c[0].size()), q2 = h[1];
if (max({q1, q2}) <= (n/2)) ok = 1;
// res
if (!ok) mi *= -1;
return mi;
}
