#include "towns.h"
#include <iostream>
#include <vector>
#include <array>
#include <map>
#define ll long long
using namespace std;
ll dist[200][200], X[200], G[200], Z[200], sz[200];
vector <ll> grp;
vector <ll> V[200];
map <ll, ll> mp;
int hubDistance(int N, int sub) {
for (int i=0; i<N; ++i) V[i].clear();
grp.clear();
mp.clear();
for (int i=0; i<N; ++i) sz[i] = Z[i] = X[i] = G[i] = 0;
ll mx = -1, id = -1, a, b, diam = -1, f = 1e18, hub = -1, hub2 = -1;
for (int i=1; i<N; ++i) {
ll res = getDistance(0, i);
dist[0][i] = dist[i][0] = res;
if (res > mx) mx = res, id = i;
}
a = id;
for (int i=1; i<N; ++i) {
if (i == a) continue;
ll res = getDistance(a, i);
dist[a][i] = dist[i][a] = res;
if (res > diam) diam = res, b = i;
}
if (dist[0][a] > diam) diam = dist[0][a], b = 0;
for (int i=1; i<N; ++i) {
if (i == a) continue;
ll s = (dist[i][a] + dist[i][0] + dist[0][a]) / 2;
++mp[s-dist[i][a]];
X[i] = s-dist[0][a], G[i] = s-dist[i][a];
}
G[0] = 0, G[a] = dist[0][a];
++mp[0];
++mp[dist[0][a]];
ll k = 0;
for (auto [x, y] : mp) {
mp[x] = k++;
}
for (int i=0; i<N; ++i) {
V[mp[G[i]]].push_back(i);
Z[mp[G[i]]] = G[i];
}
for (int i=0; i<k; ++i) {
if (Z[i] >= G[b]) {
Z[i] = dist[0][a]-Z[i];
if (f > max(Z[i], diam-Z[i])) f = max(Z[i], diam-Z[i]), hub = i, hub2 = -1;
else if (f == max(Z[i], diam-Z[i])) hub2 = i;
}
}
if (hub2 != -1) {
ll tot = 0, tot2 = 0;
for (int i=0; i<=hub; ++i) tot += V[i].size();
for (int i=hub2; i<k; ++i) tot2 += V[i].size();
if (tot <= N/2 && tot2 <= N/2) return (int)f;
else if (tot <= N/2) hub = hub2;
}
ll tot = 0, tot2 = 0;
for (int i=0; i<hub; ++i) tot += V[i].size();
for (int i=hub+1; i<k; ++i) tot2 += V[i].size();
if (max(tot, tot2) > N/2) return (int)-f;
ll cur = -1, x = 0, y = 0;
for (auto u : V[hub]) {
if (cur == -1) {
cur = u, x = 1, y = 0;
sz[u] = 1;
grp.push_back(u);
}
else {
ll res = getDistance(cur, u);
if (res != X[u] + X[cur]) {
++x, ++sz[cur];
}
else {
++y;
grp.push_back(u);
sz[u] = 1;
}
}
if (x == y) cur = -1, x = y = 0;
}
if (cur == -1) return (int)-f;
for (auto u : grp) {
if (cur == u) continue;
ll res = getDistance(cur, u);
if (res != X[u] + X[cur]) {
sz[cur] += sz[u];
}
}
if (sz[cur] > N/2) return (int)-f;
else return (int)f;
}
