#include "towns.h"
#include <bits/stdc++.h>
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define iter(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
const ll MOD = 1000000007;
const ll MAX = 1000000000;
vector<vector<int>> qry;
int n;
int query(int u, int v){
if(u == v) return 0;
//cerr << "query " << u << " " << v << " " << qry[u][v] << "\n";
if(qry[u][v] == -1){
int tmp = getDistance(u, v);
qry[u][v] = qry[v][u] = tmp;
}
return qry[u][v];
}
vector<int> dis(int v){
vector<int> ans(n);
for(int i = 0; i < n; i++) ans[i] = query(v, i);
return ans;
}
int hubDistance(int N, int sub){
qry.clear();
n = N;
qry.resize(n, vector<int>(n, -1));
vector<int> d0 = dis(0);
int v1 = max_element(iter(d0)) - d0.begin();
vector<int> d1 = dis(v1);
int v2 = max_element(iter(d1)) - d1.begin();
vector<int> d2 = dis(v2);
//cerr << v1 << " " << v2 << "\n";
int dia = query(v1, v2);
int ans = MAX;
vector<int> ld(n), rd(n), oao(n);
for(int i = 0; i < n; i++){
int sum = query(v1, i) + query(v2, i);
oao[i] = (sum - dia) / 2;
ld[i] = query(v1, i) - oao[i];
rd[i] = query(v2, i) - oao[i];
ans = min(ans, max(ld[i], rd[i]));
}
//cerr << ans << "\n";
int lmn = MAX, rmn = MAX;
for(int i = 0; i < n; i++){
if(ld[i] == ans || rd[i] == ans){
lmn = min(lmn, ld[i]);
rmn = min(rmn, rd[i]);
}
}
int lb = 0, rb = 0;
vector<int> lh, rh;
//cerr << lmn << " " << rmn << "\n";
for(int i = 0; i < n; i++){
//cerr << i << " " << ld[i] << " " << rd[i] << "\n";
if(ld[i] < lmn) lb++;
else if(rd[i] < rmn) rb++;
else if(ld[i] == lmn) lh.eb(i);
else if(rd[i] == rmn) rh.eb(i);
}
int lhsz = 0, rhsz = 0;
for(int i : lh){
int sz = 0;
for(int j : lh){
if(query(i, j) < oao[i] + oao[j]) sz++;
}
lhsz = max(sz, lhsz);
}
for(int i : rh){
int sz = 0;
for(int j : rh){
if(query(i, j) < oao[i] + oao[j]) sz++;
}
rhsz = max(sz, rhsz);
}
if(max({lb, rb, lhsz, rhsz}) > n / 2) ans = -ans;
return ans;
}
