#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
const int INF = 1e9 + 5;
const ll LINF = 4e18;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int((x).size()))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rev(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define f first
#define s second
template<class T> bool chmin(T& a, const T&b) {return b < a ? a = b, 1 : 0;}
template<class T> bool chmax(T& a, const T&b) {return a < b ? a = b, 1 : 0;}
#ifdef LOCAL
#define dbg(x) cout << #x << " = " << x << "\n";
#else
#define dbg(x)
#endif
struct DSU {
int n; vi par, siz, leaf;
DSU(int N = 0) : n(N), par(n, -1), siz(n, 1), leaf(n, -1) {}
int find(int v) {return par[v] == -1 ? v : par[v] = find(par[v]);}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a != b) {
// if (siz[a] < siz[b]) swap(a, b);
par[b] = a; siz[a] += siz[b];
if (leaf[a] == -1) leaf[a] = leaf[b];
}
}
void setleaf(int u) {
leaf[find(u)] = u;
}
int get_leaf(int u) {
return leaf[find(u)];
}
};
/*
1. every small town is a leaf
2. 2 nodes are siblings if every distance differs only by a constant value for every node except themselves
*/
int n; bool sub;
vi par_dist, par;
DSU dsu;
int leaf_dist(int i) {
i = dsu.find(i);
int r = 0, u = dsu.get_leaf(i);
while (par_dist[u] != -1 && u != i) {
r += par_dist[u]; u = par[u];
}
u = dsu.get_leaf(i);
// cout << "leaf distance from ";
// if (u < n) cout << u;
// else cout << char('a' + (u-n));
// cout << " (leaf) to ";
// if (i < n) cout << i;
// else cout << char('a' + (i-n));
// cout << " (head) is " << r << "\n";
return r;
}
map<pi, int> cache;
int query(int idx, int jdx) {
int i = dsu.get_leaf(idx), j = dsu.get_leaf(jdx);
int x = -1;
if (cache.count({i, j})) x = cache[{i, j}];
else {
x = cache[{i,j}] = cache[{j,i}] = getDistance(i, j);
}
x -= leaf_dist(idx);
x -= leaf_dist(jdx);
return x;
}
struct edge {
int v, w;
};
string label(int x) {
return x < n ? to_string(x) : string(1, char('a' + (x-n)));
}
int hubDistance(int N, int SUB) {
cache.clear();
n = N; sub = SUB > 2;
vector<vector<edge>> G(3*n); int id = n;
vi active(n); par_dist.assign(3*n, -1), par.assign(3*n, -1); iota(all(active), 0);
dsu = DSU(3*n); for (int i = 0; i < n; i++) dsu.setleaf(i);
int A = 0, B = -1, C = -1;
// vvi dist(n, vi(n));
vvi dist(3, vi(n));
rep(i, 0, n) dist[0][i] = query(A, i), B = (B == -1 || dist[0][i] > dist[0][B]) ? i : B;
rep(i, 0, n) dist[1][i] = query(B, i), C = (C == -1 || dist[1][i] > dist[1][C]) ? i : C;
rep(i, 0, n) dist[2][i] = query(C, i);
vi T({A, B, C});
// vi T(n); iota(all(T), 0);
// rep(i, 0, n) rep(j, 0, n) dist[i][j] = j <= i ? dist[j][i] : query(i, j);
int L = -1, R = -1;
rep(i, 0, n) {
int x = dist[1][C], y = dist[1][i], z = dist[2][i];
int J = (z+x-y) / 2; int I = (x - J); int K = z - J;
if (L == -1 || R == -1 || abs(I-J) < abs(L-R)) L = I, R = J;
}
return max(L, R);
// auto are_siblings = [&](int u, int v) {
// bool ok = true, found = false; int dx = 0;
// if (u == A || u == B || u == C || v == A || v == B || v == C) return false;
// // rep(i, 0, n) {
// rep(i, 0, sz(dist)) {
// // if (u == T[i] || v == T[i]) continue;
// if (dsu.find(T[i]) == dsu.find(u) || dsu.find(T[i]) == dsu.find(v)) continue;
// // int d1 = query(u, i), d2 = query(v, i);
// int d1 = dist[i][u], d2 = dist[i][v];
// if (!found) found = true, dx = d1 - d2;
// ok = ok && dx == d1 - d2;
// if ((d1 - d2) != dx) {
// cout << u << " and " << v << " fail on " << i << "\n";
// }
// }
// return ok;
// };
// while (sz(active) > 2) {
// vi active2; bool found = false;
// set<int> used;
// rep(idx, 0, sz(active)) {
// vi sib(1, active[idx]);
// rep(jdx, idx+1, sz(active)) {
// int i = active[idx], j = active[jdx];
// if (used.count(i) || used.count(j)) continue;
// if (!are_siblings(i, j)) continue;
// sib.pb(j);
// int k = 0; while (k < 2 * n && (dsu.find(k) == i || dsu.find(k) == j)) k++;
// int x = query(i, j);
// int y = query(i, k);
// int z = query(j, k);
// int di = 0, dj = 0;
// dj = (z + x - y) / 2;
// di = x - dj;
// par_dist[i] = di; par_dist[j] = dj;
// }
// if (sz(sib) <= 1) continue;
// found = true;
// // cout << "merging nodes: ";
// // for (auto j : sib) {
// // if (j < n) cout << j << " ";
// // else cout << char('a' + (j-n)) << " ";
// // }
// // cout << "into node " << char('a' + (id - n)) << "\n";
// for (auto j : sib) {
// dsu.unite(id, j);
// used.insert(j);
// par[j] = id;
// // if (j < n) cout << j << " ";
// // else cout << char('a' + (j-n)) << " ";
// // cout << char('a' + (id-n)) << " " << par_dist[j] << "\n";
// }
// active2.pb(id++);
// }
// if (!found) break;
// for (auto &x : active) if (!used.count(x)) active2.pb(x);
// swap(active, active2);
// }
// if (active.size() == 2) {
// int x = active[0], y = active[1];
// int weight = query(x, y);
// dsu.unite(x, y);
// par[y] = x;
// par_dist[y] = weight;
// // if (x < n) cout << x << " ";
// // else cout << char('a' + (x-n)) << " ";
// // if (y < n) cout << y << " ";
// // else cout << char('a' + (y-n)) << " ";
// // cout << weight << "\n";
// }
// rep(i, 0, 3*n) if (par[i] != -1) G[i].push_back(edge{par[i], par_dist[i]}), G[par[i]].push_back(edge{i, par_dist[i]});
// auto get_r = [&](auto &&self, int u, int p, int cur_dist)->pi {
// if (u < n) return {cur_dist, 1};
// int r = -INF, subsz = 0, submax = -INF;
// for (auto &[v, w] : G[u]) {
// if (v == p) continue;
// auto res = self(self, v, u, cur_dist + w);
// subsz += res.s;
// r = max(r, abs(res.f));
// submax = max(submax, res.s);
// }
// if (r == -INF) r = INF;
// if (submax <= n/2) r = -r;
// return {r, subsz};
// };
// int R = INF; rep(i, n, 3*n) {
// auto r = get_r(get_r, i, -1, 0);
// if (abs(r.f) < abs(R)) R = r.f;
// }
// dbg(A); dbg(B); dbg(C);
// rep(i, 0, 3*n) {
// for (auto &[v, w] : G[i]) {
// if (v == par[i]) continue;
// cout << label(i) << " " << label(v) << " " << w << "\n";
// }
// }
// return R;
return 0;
}
