#include "towns.h"
#include <bits/stdc++.h>
#define maxn 115
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int par[maxn], nodeA, nodeB, diameter, condition = 0, cached[maxn][maxn];
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_for_node(int N, int disA, int disB) {
vector<int> Mid; int SzL = 0, SzR = 0;
for (int i = 0; i < N; i++) {
int dA = (diameter + (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();
if (SzL > (N/2) || SzR > (N/2) || sz > (N/2)) return;
condition = 1;
}
int hubDistance(int N, int sub) {
condition = 0;
for (int i = 0; i < N; i++) par[i] = -1;
nodeA = 0; nodeB = 0; int mx = -1;
for (int i = 1; i < N; i++) {
int t = getDistance(0, i);
if (mx < t) {
nodeA = i;
mx = t;
}
}
mx = -1;
for (int i = 0; i < N; i++) {
int t = (cached[nodeA][i] = cached[i][nodeA] = getDistance(nodeA, i));
if (i != nodeA && mx < cached[nodeA][i]) {
mx = cached[nodeA][i];
nodeB = i;
}
}
for (int i = 0; i < N; i++) cached[nodeB][i] = cached[i][nodeB] = getDistance(nodeB, i);
int ans = INT_MAX, tong = diameter = mx;
vector<ii> possible;
for (int i = 0; i < N; i++)
if (i != nodeA && i != nodeB) {
int hieu = cached[nodeA][i] - cached[nodeB][i],
disA = (tong + (cached[nodeA][i] - cached[nodeB][i])) / 2,
disB = (tong + (cached[nodeB][i] - cached[nodeA][i])) / 2;
if (hieu < 0) hieu = -hieu;
if (ans > (tong+hieu)/2) {
ans = (tong+hieu)/2;
possible.clear();
possible.emplace_back(disA, disB);
} else if (ans == (tong+hieu)/2) {
possible.emplace_back(disA, disB);
}
}
for (auto [u, v] : possible) solve_for_node(N, u, v);
return condition ? ans : -ans;
}
