#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 = 1e9;
vector<int> d_0, d_a, d_x;
set<ll> cmp1, cmp2;
bool same (ll i, ll j) {
if (cmp1.count(i) && cmp1.count(j)) return 1;
if (cmp2.count(i) && cmp2.count(j)) return 1;
if (cmp1.count(i) || cmp1.count(j) || cmp2.count(i) || cmp2.count(j)) return 0;
return (getDistance(i, j) < d_a[i] + d_a[j] - 2ll*d_x[i]);
}
int solve (vector<int> vec) {
// cout << "Solve\n";
// for (ll i: cmp1) cout << i << ' ';
// cout << '\n';
// for (ll i: cmp2) cout << i << ' ';
// cout << '\n';
// for (ll i: vec) cout << i << ' ';
// cout << '\n';
// return 0 ;
vector<int> A, B;
for (ll i: vec) {
if (A.size() == 0) {
A.pb(i);
continue;
}
if (same(A.back(), i)) {
B.pb(i);
continue;
}
A.pb(i);
if (B.size()) {
A.pb(B.back());
B.pop_back();
}
}
// for (ll i: A) cout << i << ' ';
// cout << '\n';
// for (ll i: B) cout << i << ' ';
// cout << '\n';
ll m = A.back();
while (A.size()) {
if (A.back() == m || same(A.back(), m)) {
if (A.size() == 1) {
B.push_back(A.back());
A.pop_back();
continue;
}
A.pop_back();
A.pop_back();
} else {
A.pop_back();
if (B.size() == 0) return 0;
B.pop_back();
}
}
return (B.size() > 0 ? 1 : 0);
}
int hubDistance(int N, int sub) {
cmp1.clear();
cmp2.clear();
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;
R = min(R, max(d_x[i], d_a[b]-d_x[i]));
if (d_x[i] > mid || i == a || i == b) continue;
mp[d_x[i]].pb(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;
}
fo (i, N) {
if (d_x[i] == k) continue;
if (d_x[i] < k) cmp1.insert(i);
else cmp2.insert(i);
}
vector<int> vec2;
fo (i, N) vec2.pb(i);
if (t <= N/2) return R;
if (solve(vec2)) return -R;
return R;
sum += t;
}
return -R;
}
