#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 = 1e18;
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(i, u) - ((ask(i, u) + ask(i, v) - diam) / 2);
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);
if (cur < R) {
R = cur;
cand = {{di, i}};
} else if (cur == R) cand.push_back({di, i});
}
}
// cerr << "bruh: " << 436 << " " << max(ask(u, v) - 436, 436LL) << '\n';
// 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());
// cerr << a.size() << '\n';
vector<pair<int, int>> crit;
int neg = 0;
for (auto x : cand) {
// cerr << x.first << '\n';
int big = 0, smol = 0, child = 0;
for (auto& [di, i] : a) {
// if (i == u || i == v || i == x.second) continue;
if (di < x.first) smol++;
else if (di > x.first) big++;
else if (di == x.first) child++;
}
// cerr << smol << " " << big << " " << child << '\n';
if (smol > N / 2 || big > N / 2) continue;
if (child <= N / 2) return R;
crit.push_back(x);
// if (child > N / 2) crit.push_back(x);
// else neg++;
}
if (crit.empty()) return -R;
// cerr << "hi\n";
// 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) {
// for (auto xx : val) cerr << xx << ' ';
// // return -R;
// }
// return R;
// cerr << qc << '\n';
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;
cerr << "match: " << rep << " " << i << '\n';
freq++;
} else {
mp[{rep, i}] = 0, mp[{i, rep}] = 0;
--freq;
}
}
int cnter = 1;
vector<int> det(sz, -1);
det[rep] = 1;
// cerr << qc << '\n';
// cerr << "paint:" << rep << '\n';
for (int it = 1; it < sz; it++) {
if (cnter > N / 2) return -R;
if (qc > upper_bound) {
cerr << "hi\n";
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}];
if (det[i] == 1) cerr << "paint:" << i << '\n';
cnter += det[i];
oked = 1;
break;
}
for (int j = 0; j < sz; j++) if (det[j] == 0 && mp.count({i, j}) && mp[{i, j}] == 1) {
det[i] = 0;
cerr << "paint NOT: " << i << '\n';
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;
cnter++;
if (det[i] == 1) cerr << "paintQ:" << i << '\n';
} else {
mp[{rep, i}] = 0, mp[{i, rep}] = 0;
cerr << "paintQ NOT: " << i << '\n';
det[i] = 0;
}
cerr << "queried " << rep << " " << i << '\n';
oked = 1;
break;
}
}
if (cnter > N / 2) return -R;
if (qc > upper_bound) {
cerr << "hi\n";
return R;
}
}
return R;
}
/*
1 2
2 3
2 4
2 5
4 6
5 7
3 8
3 9
3 10
*/
/*
1 2 3 7 8 10 13 14 15 16 17 18 19 20 21 23 25 27 29 33 34 40 41 42 44 45
*/
