#include "towns.h"
#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
using namespace std;
int hubDistance(int N, int sub) {
int farthest = 1, maxDist = 0;
for (int i = 2; i <= N; i++) {
int d = getDistance(1, i);
if (d > maxDist) {
maxDist = d;
farthest = i;
}
}
int diamStart = farthest;
maxDist = 0;
for (int i = 1; i <= N; i++) {
if (i == diamStart) continue;
int d = getDistance(diamStart, i);
if (d > maxDist) {
maxDist = d;
farthest = i;
}
}
int diamEnd = farthest;
vector<pair<int, int>> nodes;
for (int i = 1; i <= N; i++) {
nodes.push_back({getDistance(diamStart, i), i});
}
sort(nodes.begin(), nodes.end());
int hub = nodes[maxDist / 2].second;
if (sub == 1 || sub == 2) return maxDist;
vector<int> distances;
for (int i = 1; i <= N; i++) {
if (i != hub) distances.push_back(getDistance(hub, i));
}
sort(distances.begin(), distances.end());
int maxGroupSize = (N - 1) / 2;
if (distances[N - 2] <= maxGroupSize) return maxDist;
return -1;
}
