#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) {
//Random lj
int farthest = 1, maxDist = 0;
for (int i = 2; i <= N; i++) {
int d = getDistance(1, i);
if (d > maxDist) {
maxDist = d;
farthest = i;
}
}
//mas lejano
int diamEnd = farthest;
maxDist = 0;
for (int i = 1; i <= N; i++) {
if (i == diamEnd) continue;
int d = getDistance(diamEnd, i);
if (d > maxDist) {
maxDist = d;
farthest = i;
}
}
// cenntral nodo
int hub = diamEnd;
for (int i = 1; i <= N; i++) {
if (getDistance(diamEnd, i) == maxDist / 2) {
hub = i;
break;
}
}
if (sub == 1 || sub == 2) return maxDist;
// 4 hub
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;
}
