#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
bool find_cent(vector<int> cands, int prev) {
// find two nodes in diameter
// merge leaves together based on their distance to one end
// get size of max component
int most = n / 2;
int tot = cands.size();
prev += 2;
if (prev > most) return false;
if (cands.size() <= most) return true;
int a = rand() % tot;
int b = rand() % tot;
while (b == a) b = rand() % tot;
vector<int> disA(tot, 0), disB(tot, 0);
int diff = getDistance(cands[a], cands[b]);
vector<pair<int, int>> comps;
for (int i = 0; i < n; i++) {
if (i == a || i == b) continue;
disA[i] = getDistance(cands[i], cands[a]);
disB[i] = getDistance(cands[i], cands[b]);
int aa = (disA[i] + disB[i] - diff) / 2;
int da = disA[i] - aa;
comps.push_back({da, cands[i]});
}
vector<int> curr, opt;
tot = comps.size();
for (int i = 0; i < tot; i++) {
if (i > 0 && comps[i].first != comps[i-1].first) {
if (curr.size() > opt.size()) {
opt = curr;
}
curr.clear();
}
curr.push_back(comps[i].second);
}
if (curr.size() > opt.size()) opt = curr;
if (opt.size() <= most) return true;
return find_cent(opt, n - (int)opt.size());
}
int hubDistance(int N, int sub) {
n = N;
assert(sub <= 2);
int a = 0, b = 0;
int maxDis = 0;
for (int i = 1; i < n; i++) {
int tot = getDistance(0, i);
if (tot > maxDis) {
maxDis = tot;
b = i;
}
}
vector<int> disB(n);
disB[0] = maxDis;
for (int i = 1; i < n; i++) {
if (i == b) continue;
int tot = getDistance(b, i);
disB[i] = tot;
if (tot > maxDis) {
maxDis = tot;
a = i;
}
}
vector<int> disA(n);
disA[b] = disB[a];
for (int i = 0; i < n; i++) {
if (i == a || i == b) continue;
disA[i] = getDistance(i, a);
}
int r = maxDis;
vector<pair<int, int>> comps;
for (int i = 0; i < n; i++) {
if (i == a || i == b) continue;
int aa = (disA[i] + disB[i] - maxDis) / 2;
int da = disA[i] - aa;
int db = disB[i] - aa;
r = min(r, max(da, db));
comps.push_back({da, i});
}
vector<int> curr, opt;
int tot = comps.size();
for (int i = 0; i < tot; i++) {
if (i > 0 && comps[i].first != comps[i-1].first) {
if (curr.size() > opt.size()) {
opt = curr;
}
curr.clear();
}
curr.push_back(comps[i].second);
}
if (curr.size() > opt.size()) opt = curr;
bool f = find_cent(opt, n - (int)opt.size());
if (!f) r = -r;
return r;
}
