#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int hubDistance(int N, int sub) {
int n = N;
assert(sub <= 2);
int a = 0, b = 0;
int maxDis = 0;
for (int i = 1; i < n; i++) {
int tot = getDistance(0, i);
if (tot > maxDis) {
maxDis = tot;
b = i;
}
}
vector<int> disB(n);
disB[0] = maxDis;
for (int i = 1; i < n; i++) {
if (i == b) continue;
int tot = getDistance(b, i);
disB[i] = tot;
if (tot > maxDis) {
maxDis = tot;
a = i;
}
}
vector<int> disA(n);
disA[b] = disB[a];
for (int i = 0; i < n; i++) {
if (i == a || i == b) continue;
disA[i] = getDistance(i, a);
}
int r = maxDis;
for (int i = 0; i < n; i++) {
if (i == a || i == b) continue;
int aa = (disA[i] + disB[i] - maxDis) / 2;
int da = disA[i] - aa;
int db = disB[i] - aa;
r = min(r, max(da, db));
}
return r;
}
