#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#define int long long
map<pair<int, int>, int> cache;
int qc = 0;
int ask(int i, int j) {
if (i == j) return 0;
if (!cache.count({i, j})) {
qc++;
int res = getDistance((int32_t) i, (int32_t) j);
cache[{i, j}] = cache[{j, i}] = res;
return cache[{i, j}];
}
return cache[{i, j}];
}
int p[111];
int find(int u) {
return p[u] == u ? u : p[u] = find(p[u]);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
p[v] = u;
}
}
int32_t hubDistance(int32_t N, int32_t sub) {
for (int i = 0; i < 111; i++) p[i] = i;
cache.clear();
qc = 0;
// cerr << "hi\n";
int upper_bound = (7 * N + 1) / 2;
int mx = -1, u, v;
for (int i = 0; i < N; i++) {
if (ask(0, i) > mx) mx = ask(0, i), u = i;
}
mx = -1;
for (int i = 0; i < N; i++) if (ask(u, i) > mx) mx = ask(u, i), v = i;
vector<pair<int, int>> a;
vector<pair<int, int>> cand;
// cerr << u << " " << v << '\n';
// cerr << "hi\n";
const int inf = 1e9;
int R = mx;
if (v == 0 || u == 0) {
int diam = ask(u, v);
for (int i = 0; i < N; i++) {
if (i == u || i == v) continue;
int di = ask(i, u) - ((ask(i, u) + ask(i, v) - diam) / 2);
a.push_back({di, i});
// cerr << di << " " << i << '\n';
int cur = max(di, diam - di);
if (cur < R) {
R = cur;
cand = {{di, i}};
} else if (cur == R) cand.push_back({di, i});
}
} else {
int diam = ask(u, v);
int d0;
for (int i = 0; i < N; i++) {
if (i == u || i == v) continue;
int di = (ask(0, u) + ask(i, u) - ask(0, i)) / 2;
if (i == 0) d0 = di = ask(0, u) - ((ask(0, u) + ask(0, v) - ask(u, v)) / 2);
else {
int compo = (ask(0, u) + ask(i, u) + ask(0, i)) / 2;
if (compo > d0 + ask(0, i)) di = d0;
}
a.push_back({di, i});
int cur = max(di, diam - di);
// cerr << i << " " << di << '\n';
if (cur < R) {
R = cur;
cand = {{di, i}};
} else if (cur == R) cand.push_back({di, i});
}
}
// return R;
a.push_back({0, u});
a.push_back({ask(u, v), v});
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
vector<pair<int, int>> crit;
for (auto x : cand) {
int big = 0, smol = 0, child = 1;
for (auto& [di, i] : a) {
// if (i == u || i == v || i == x.second) continue;
if (i == x.second) continue;
if (di < x.first) smol++;
else if (di > x.first) big++;
else child++;
}
if (smol > N / 2 || big > N / 2) continue;
if (child > N / 2) crit.push_back(x);
}
if (crit.empty()) return R;
// assert((int) crit.size() == 1);
int node = crit[0].second, distance = crit[0].first;
// cerr << node << " " << distance << '\n';
vector<pair<int, int>> vec;
for (auto& [di, i] : a) if (distance == di) {
int newd = ask(i, u) - di;
vec.push_back({newd, i});
// cerr << newd << " " << i << '\n';
}
int sz = vec.size();
for (int i = 0; i < sz; i++) {
for (int j = 0; j < sz; j++) {
if (i != j && ask(vec[j].second, vec[i].second) != vec[j].first + vec[i].first) merge(i, j);
// if (i != j) cerr << i << " " << j << " " << !!(ask(vec[j].second, vec[i].second) != vec[j].first + vec[i].first) << '\n';
}
}
map<int, vector<int>> asdf;
for (int i = 0; i < sz; i++) asdf[find(i)].push_back(i);
for (auto& [key, val] : asdf) if (val.size() > N / 2) return -R;
return R;
int rep = 0, freq = 0;
map<pair<int, int>, int> mp;
for (int i = 0; i < sz; i++) {
if (freq == 0) rep = i, freq = 1;
else if (ask(vec[rep].second, vec[i].second) != vec[rep].first + vec[i].first) {
mp[{rep, i}] = 1, mp[{i, rep}] = 1;
freq++;
} else {
mp[{rep, i}] = 0, mp[{i, rep}] = 0;
--freq;
}
}
int cnter = 1;
vector<int> det(sz, -1);
det[rep] = 1;
for (int it = 1; it < sz; it++) {
if (cnter > N / 2) return -R;
if (qc >= upper_bound) return R;
bool oked = 0;
for (int i = 0; i < sz; i++) {
if (det[i] >= 0) continue;
for (int j = 0; j < sz; j++) if (det[j] == 1 && mp.count({i, j})) {
det[i] = mp[{i, j}];
cnter += det[i];
oked = 1;
break;
}
if (oked) break;
}
if (!oked) {
for (int i = 0; i < sz; i++) {
if (det[i] != -1) continue;
if (ask(vec[i].second, vec[rep].second) != vec[rep].first + vec[i].first) {
mp[{rep, i}] = 1, mp[{i, rep}] = 1;
det[i] = 1;
} else {
mp[{rep, i}] = 0, mp[{i, rep}] = 0;
det[i] = 0;
}
oked = 1;
break;
}
}
if (cnter > N / 2) return -R;
if (qc >= upper_bound) return R;
}
return R;
}
/*
1 2
2 3
2 4
2 5
4 6
5 7
3 8
3 9
3 10
*/
