// Note: 0-indexed, multiple tests
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 115, INF = 2e9;
int n;
arr<int, N> dst;
int fr(int u) {
pii mx = {-1, -1};
for (int v = 1; v <= n; v++)
dst[v] = getDistance(u - 1, v - 1), mx = max(mx, {dst[v], v});
assert(mx.sec != -1);
return mx.sec;
}
arr<int, N> a_dst, b_dst;
set<int> df;
int hubDistance(int _n, int _s) {
n = _n;
int a = fr(1);
int b = fr(a);
a_dst = dst;
fr(b);
b_dst = dst;
df.clear();
for (int u = 1; u <= n; u++)
if (u != a && u != b) df.insert(a_dst[u] - b_dst[u]);
// cout << a << " " << b << " " << a_dst[b] << endl;
int ans = INF;
for (int x : df) {
int in_a = (x + a_dst[b]) / 2;
int in_b = (-x + a_dst[b]) / 2;
ans = min(ans, max(in_a, in_b));
}
return ans;
}
