#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
int hubDistance(int n, int sub) {
sub--; // suppress unused warning
vector<int> d0(n), du(n);
for(int i = 1; i < n; i++) d0[i] = getDistance(0, i);
int u = int(max_element(d0.begin(), d0.end())-d0.begin());
for(int i = 0; i < n; i++) if(u!=i) du[i] = getDistance(u, i);
int v = int(max_element(du.begin(), du.end())-du.begin());
int l = 0, r = 0;
vector<int> xl, xr;
int maxB = 0, maxC = 0;
for(int i = 0; i < n; i++){
int b = (d0[u]+d0[i]-du[i])/2;
int c = d0[u]-b;
if(b+du[v]-d0[u] <= du[v]/2){
if(b < maxB) l++;
if(b > maxB) l+=sz(xl), xl.clear(), maxB = b;
if(b == maxB) xl.push_back(i);
}
if(c <= du[v]/2){
if(c < maxC) r++;
if(c > maxC) r+=sz(xr), xr.clear(), maxC = c;
if(c == maxC) xr.push_back(i);
}
}
int R = min(d0[u]-maxB, du[v]-maxC);
vector<int> x;
bool ok = false;
if(d0[u]-maxB == R){
if(l <= n/2 && r+sz(xr) <= n/2) x = xl, ok = true;
}
if(du[v]-maxC == R){
if(l+sz(xl) <= n/2 && r <= n/2) x = xr, ok = true;
}
if(xl == xr){
if(l <= n/2 && r <= n/2) x = xl, ok = true;
}
if(!ok) return -R;
auto same = [&](int a, int b){
return getDistance(a, b) == (d0[a]+du[a]-d0[u])/2 + (d0[b]+du[b]-d0[u])/2;
};
vector<int> cache(sz(x), -1);
int cnt = 1;
int cur = 0;
cache[0] = 0;
for(int i = 1; i < sz(x); i++){
if(same(x[cur], x[i])) cnt++, cache[i] = cur;
else if(--cnt == 0){
cur = i;
cnt = 1;
cache[i] = cur;
}
}
int other = 0;
bool isSame = false;
for(int i = 0; i < sz(x); i++){
if(other >= (n+1)/2) break;
if(cache[i] == i){
if(isSame) isSame = false;
else isSame = same(cur, x[i]);
}
if(cache[i] != -1 && !isSame) other++;
if(cache[i] == -1 && isSame) other++;
if(cache[i] == -1 && !isSame) other += !same(cur, x[i]);
}
if(sz(x)-other <= n/2) return R;
else return -R;
}
