#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
map<pair<int, int>, ll> memo;
ll query(int i, int j) {
if (i == j) return 0;
if (i > j) swap(i, j);
if (memo.count({i, j})) return memo[{i, j}];
return memo[{i, j}] = getDistance(i, j);
}
int hubDistance(int N, int sub) {
ll best = LLONG_MAX;
ll mn, fir = -1, sec = -1, mid = -1;
mn = -1;
for (int i = 0; i < N; i++) {
ll curr = query(0, i);
if (curr > mn) {
mn = curr;
fir = i;
}
}
mn = -1;
for (int i = 0; i < N; i++) {
ll curr = query(fir, i);
if (curr > mn) {
mn = curr;
sec = i;
}
}
ll dia = mn;
vector<pair<ll, ll>> cands;
for (int i = 0; i < N; i++) {
ll curr = (query(fir, i) + query(sec, i) - query(fir, sec)) / 2;
ll cand = abs(curr - query(fir, sec));
cands.emplace_back(cand, i);
}
sort(cands.begin(), cands.end());
auto work = [&](ll a, ll b, ll c) -> ll {
ll AB = query(a, b);
ll BC = query(b, c);
ll CA = query(c, a);
cerr << AB sp BC sp CA << endl;
ll ABC = (AB+BC+CA) / 2;
ll A = ABC-BC, B = ABC-CA, C = ABC-AB;
cerr << A sp B sp C << endl;
return max({A, B, C});
};
return max(work(fir, sec, cands[0].second), work(fir, sec, cands[1].second));
}
