#include "towns.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }
/*
getDistance (i, j)
*/
int hubDistance(int N, int sub) {
int A = 0, B = 0, b = 0;
fore (i, 1, N) {
int g = getDistance (0, i);
if (g > b) {
b = g;
A = i;
}
}
vector<int> dA(N, 0), dB(N, 0);
B = 0;
fo (i, N) {
if (i == A) continue;
int g = getDistance (A, i);
dA[i] = g;
if (g > b) {
b = g;
B = i;
}
}
int ans = dA[B], ok = -1;
fo (i, N) {
if (i == B) continue;
dB[i] = getDistance (B, i);
}
map<ll, ll> cnt;
fo (i, N) {
if (i == A || i == B) continue;
int d = dA[i] + dB[i] - dA[B];
d /= 2;
cnt[dA[i] - d]++;
ans = min(ans, max(dA[i], dB[i]) - d);
}
ll sum = 0;
for (auto [k, v]: cnt) {
if (max(k, dA[B] - k) > ans) continue;
if (k > N/2) continue;
if (sum <= N/2 && N - sum - v <= N/2)
ok = 1;
sum += v;
}
if (sub > 2) {
return ans * ok;
}
return ans;
}
