#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
const ll MAXN = 120;
int dis[MAXN][MAXN];
int hubDistance (int N, int sub) {
ll n = N;
ll u1 = 0, dis1 = 0;
for (ll u = 1; u < n; u++) {
ll dis = getDistance(0, u);
if (dis <= dis1) continue;
dis1 = dis;
u1 = u;
}
vll disU1(n, 0), disU2(n, 0);
map <ll, vll> mp1, mp2;
ll u2 = 0, diam = dis1;
mp1[0].push_back(dis1);
disU1[0] = dis1;
for (ll u = 1; u < n; u++) {
if (u == u1) continue;
ll dis = getDistance(u1, u);
disU1[u] = dis;
mp1[dis].push_back(u);
if (dis <= diam) continue;
diam = dis;
u2 = u;
}
// cerr << u1 << ' ' << u2 << '\n';
disU2[u1] = disU1[u2];
for (ll u = 0; u < n; u++) {
if (u == u1 || u == u2) continue;
disU2[u] = getDistance(u2, u);
}
for (ll u = 0; u < n; u++) {
ll ext = (disU1[u] - disU2[u] + diam) / 2;
mp2[ext].push_back(u);
}
ll ans = diam;
for (auto [d, ve] : mp2) {
ans = min(ans, max(d, diam-d));
}
bool existsBal = false;
ll lhs = 0;
for (auto [d, ve] : mp2) {
if (ans != max(d, diam-d)) { lhs += ve.size(); continue; }
ll rhs = n-lhs-ve.size();
if (lhs > n/2 || rhs > n/2) { lhs += ve.size(); continue; }
existsBal = true;
lhs += ve.size();
}
return (existsBal ? ans : -ans);
// for (auto [d, ve] : mp2) {
// cerr << d << ": ";
// for (ll u : ve) cerr << u << ' ';
// cerr << '\n';
// }
// return 0;
}
