#include "towns.h"
#include <bits/stdc++.h>
#define maxn 115
using namespace std;
int cached[maxn][maxn], par[maxn], nodeA, nodeB, diameter;
int find_set(int v) {
return par[v] < 0 ? v : par[v] = find_set(par[v]);
}
void union_set(int u, int v) {
u = find_set(u); v = find_set(v);
if (u == v) return;
if (par[u] < par[v]) swap(u, v);
par[v] += par[u];
par[u] = v;
}
void solve(int u, int v) {
int distance_to_mid_point = 0,
distance_to_lca = 0;
int A_minus_B = cached[nodeA][u] - cached[nodeB][u],
A_plus_B = diameter;
int mid_point_to_A = (A_plus_B + A_minus_B) / 2;
distance_to_mid_point = cached[nodeA][u] - mid_point_to_A;
int u_minus_v = cached[nodeA][u] - cached[nodeA][v];
int u_plus_v = cached[u][v];
distance_to_lca = (u_minus_v + u_plus_v) / 2;
if (distance_to_lca < distance_to_mid_point) union_set(u, v);
}
int hubDistance(int N, int sub) {
for (int i = 0; i < N; i++) par[i] = -1;
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++) cached[i][j] = cached[j][i] = getDistance(i, j);
nodeA = 0; nodeB = 0; int mx = -1;
for (int i = 1; i < N; i++)
if (mx < cached[0][i]) {
nodeA = i;
mx = cached[0][i];
}
mx = -1;
for (int i = 0; i < N; i++)
if (i != nodeA && mx < cached[nodeA][i]) {
mx = cached[nodeA][i];
nodeB = i;
}
vector<int> Mid; int SzL = 0, SzR = 0;
int ans = INT_MAX, tong = diameter = mx, disA, disB;
for (int i = 0; i < N; i++)
if (i != nodeA && i != nodeB) {
int hieu = cached[nodeA][i] - cached[nodeB][i];
if (hieu < 0) hieu = -hieu;
if (ans > (tong+hieu)/2) {
ans = (tong+hieu)/2;
disA = (tong + (cached[nodeA][i] - cached[nodeB][i])) / 2;
disB = (tong + (cached[nodeB][i] - cached[nodeA][i])) / 2;
}
}
for (int i = 0; i < N; i++) {
int dA = (tong + (cached[nodeA][i] - cached[nodeB][i])) / 2;
if (dA == disA) Mid.emplace_back(i);
else if (dA < disA) ++SzL;
else ++SzR;
}
int sz = Mid.size();
for (int i = 0; i < sz; i++)
for (int j = i+1; j < sz; j++) {
int u = Mid[i], v = Mid[j];
solve(u, v);
}
if (SzL > (N/2) || SzR > (N/2)) return -ans;
for (int i = 0; i < N; i++) if (-par[i] > (N/2)) return -ans;
return ans;
}
