#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)
*/
const int INF = 1e18;
vector<int> d_0, d_a, d_x;
bool same (ll i, ll j) {
return (getDistance(i, j) < d_a[i] + d_a[j] - 2ll*d_x[i]);
}
vector<int> unite (vector<int> a, vector<int> b) {
vector<int> c;
for (ll i: a) c.pb(i);
for (ll i: b) c.pb(i);
return c;
}
// si hay un elemento mayoritario este retornara su frecuencia
int solve (vector<int> vec) {
vector<vector<int>> alive, dead;
fo (i, vec.size()) alive.pb({i});
while (alive.size() > 1) {
vector<vector<int>> nalive;
for (ll i = 0; i+1 < alive.size(); i += 2) {
auto a = alive[i], b = alive[i+1];
if (same(vec[a[0]], vec[b[0]])) {
nalive.pb(unite(a, b));
} else {
dead.pb(a);
dead.pb(b);
}
}
if (alive.size()&1) {
if (nalive.size() > 0)
dead.pb(alive.back());
else nalive.pb(alive.back());
}
alive = nalive;
}
if (alive.size() == 0) return 0;
for (vector<int> g: dead) {
if (same(vec[alive[0][0]], vec[g[0]])) {
for (ll i: g) alive[0].pb(i);
}
}
return alive[0].size();
}
int hubDistance(int N, int sub) {
int a, b;
d_0 = vector<int>(N, 0);
d_a = vector<int>(N, 0);
d_x = vector<int>(N, 0);
for (int i = 1; i < N; i++) d_0[i] = getDistance(0, i);
for (int i = 0; i < N; i++) if (d_0[i] == *max_element(all(d_0))) {
a = i;
break;
}
d_a[0] = d_0[a];
for (int i = 1; i < N; i++) {
if (i == a) continue;
d_a[i] = getDistance (a, i);
}
for (int i = 0; i < N; i++) if (d_a[i] == *max_element(all(d_a))) {
b = i;
break;
}
int R = INF, mid = (d_a[0] + d_a[b] - d_0[b])/2;
map<int, vector<int>> mp;
for (int i = 0; i < N; i++) {
d_x[i] = (d_a[i] + d_a[0] - d_0[i])/2;
if (d_x[i] > mid || i == a || i == b) continue;
mp[d_x[i]].pb(i);
R = min(R, max(d_x[i], d_a[b]-d_x[i]));
}
ll sum = 1;
for (auto [k, vec]: mp) {
ll t = vec.size();
if (sum > N/2) break;
if (N - sum - t > N/2 || max(k, d_a[b] - k) > R) {
sum += t;
continue;
}
if (t <= N/2) return R;
if (solve(vec) > N/2) return -R;
return R;
}
return -R;
}
