#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int hubDistance(int N, int subtask) {
int maxDist = 0, diam1 = 0;
for (int i = 1; i < N; i++) {
int distOn = getDistance(0, i);
if (distOn > maxDist) {
maxDist = distOn, diam1 = i;
}
}
vector<int> distDiam1(N, 0);
for (int i = 0; i < N; i++) {
distDiam1[i] = getDistance(diam1, i);
}
int diam2 = max_element(distDiam1.begin(), distDiam1.end()) - distDiam1.begin();
vector<int> distDiam2(N, 0);
for (int i = 0; i < N; i++) {
distDiam2[i] = getDistance(diam2, i);
}
vector<int> distHor(N, 0), distVert(N, 0); // from diam1
int maxMin = 0;
for (int i = 0; i < N; i++) {
assert(!((distDiam1[diam2] + distDiam2[i] - distDiam1[i])&1));
distHor[i] = (distDiam1[diam2] + distDiam2[i] - distDiam1[i]) / 2;
assert(!((3*distDiam2[i] - distDiam1[diam2] - distDiam1[i])&1));
distVert[i] = (3*distDiam2[i] - distDiam1[diam2] - distDiam1[i]) / 2;
maxMin = max(distHor[i], distDiam1[diam2] - distHor[i]);
}
cerr << maxMin << "\n";
return maxMin;
}
