// 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
#define vec vector
const int N = 115, INF = 2e9;
int n;
arr<int, N> dst;
arr<int, N> a_dst, b_dst;
arr<bool, N> wt;
int fr(int u) {
pii mx = {-1, -1};
for (int v = 1; v <= n; v++)
if (!wt[v])
dst[v] = getDistance(u - 1, v - 1), mx = max(mx, {dst[v], v});
assert(mx.sec != -1);
return mx.sec;
}
map<int, vec<int>> cmp_mp;
vec<pair<int, vec<int>>> cmp;
vec<int> in_a, in_b;
bool lf(int id) {
int sm = 1;
for (int i = 0; i < id; i++) sm += cmp[i].sec.size();
return (sm <= n / 2);
}
bool rg(int id) {
int sm = 1;
for (int i = cmp.size() - 1; i > id; i--) sm += cmp[i].sec.size();
return (sm <= n / 2);
}
arr<int, N> u_dst, v_dst;
map<int, vec<int>> nw_cmp;
arr<bool, N> in;
bool chck(int id) {
in.fill(false);
for (int u : cmp[id].sec) in[u] = true;
int u = cmp[id].sec[0];
for (int v : cmp[id].sec) {
if (getDistance(u, v) != a_dst[u] + a_dst[v] - 2 * in_a[id]) wt[v] = true;
else {
fr(u);
u_dst = dst;
fr(v);
v_dst = dst;
for (int w : cmp[id].sec) {
if (wt[w]) continue;
nw_cmp[u_dst[w] - v_dst[w]].push_back(w);
}
for (int w = 1; w <= n; w++)
if (wt[w]) nw_cmp.begin()->sec.push_back(w);
for (pair<int, vec<int>> x : nw_cmp)
if (x.sec.size() > n / 2) return false;
return true;
}
}
return (cmp[id].sec.size() <= n / 2);
}
void intl() {
cmp_mp.clear();
cmp.clear();
in_a.clear(), in_b.clear();
wt.fill(false);
nw_cmp.clear();
}
int hubDistance(int _n, int _s) {
intl();
n = _n;
int a = fr(1);
int b = fr(a);
a_dst = dst;
fr(b);
b_dst = dst;
for (int u = 1; u <= n; u++)
if (u != a && u != b) cmp_mp[a_dst[u] - b_dst[u]].push_back(u);
for (pair<int, vec<int>> x : cmp_mp) cmp.push_back(x);
in_a.resize(cmp.size()), in_b.resize(cmp.size());
pair<int, vec<int>> bst = {INF, {}};
for (int i = 0; i < cmp.size(); i++) {
in_a[i] = (cmp[i].fir + a_dst[b]) / 2;
in_b[i] = (-cmp[i].fir + a_dst[b]) / 2;
int vl = max(in_a[i], in_b[i]);
if (vl < bst.fir) bst = {vl, {i}};
else if (vl == bst.fir) bst.sec.push_back(i);
}
bool ok = false;
if (bst.sec.size() == 1) ok = chck(bst.sec[0]);
else {
if (!lf(bst.sec[0])) ok = false;
else if (!rg(bst.sec[0])) ok = chck(bst.sec[1]);
else ok = chck(bst.sec[0]);
}
return (ok ? bst.fir : -bst.fir);
}
