#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 nodeA = 0, nodeB = 0, diameter = 0;
int cached0[maxn], cachedA[maxn];
int cmp(int x, int y) {
return 1;
}
int solve(int N, vector<int> Mid) {
int pos = 0;
for (int i = 1, cnt = 1; i < Mid.size(); i++) {
if (cmp(Mid[pos], Mid[i])) ++cnt;
else --cnt;
if (cnt == 0) {
pos = i;
cnt = 1;
}
}
int ans = 0;
for (int i = 0; i < Mid.size(); i++)
ans += cmp(Mid[i], Mid[pos]);
return (ans > (N/2));
}
int hubDistance(int N, int sub) {
nodeA = 0; nodeB = 0; int mx = -1;
for (int i = 1; i < N; i++) {
int t = cached0[i] = getDistance(0, i);
if (mx < t) {
nodeA = i;
mx = t;
}
}
cachedA[nodeA] = 0; cachedA[0] = mx;
for (int i = 1; i < N; i++) {
if (i == nodeA) continue;
int t = cachedA[i] = getDistance(nodeA, i);
if (mx < cachedA[i]) {
mx = cachedA[i];
nodeB = i;
}
}
diameter = mx;
int disA = 0;
for (int i = 1; i < N; i++)
if (i != nodeA) {
int A_minus_zero = cachedA[i] - cached0[i],
A_plus_zero = cachedA[0];
int dA = (A_minus_zero+A_plus_zero) / 2;
if (abs(2*dA - (diameter)) < abs(2*disA - (diameter))) disA = dA;
}
int ans = max(disA, diameter - disA);
int szL = 1, szR = 1;
vector<int> Mid;
for (int i = 1; i < N; i++)
if (i != nodeA) {
int A_minus_zero = cachedA[i] - cached0[i],
A_plus_zero = cachedA[0];
int dA = (A_minus_zero+A_plus_zero) / 2;
if (dA < disA) ++szL;
else if (dA > disA) ++szR;
else Mid.emplace_back(i);
}
if (szL > (N/2) || szR > (N/2)) return -ans;
return solve(N, Mid) ? -ans : ans;
}
