#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pll;
#define X first
#define Y second
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 300 + 10;
int n, f[MAXN], sz[MAXN], dist[MAXN][MAXN];
/*
inline int get(int u, int v) {
u--, v--;
return getDistance(u, v);
}
*/
inline int get(int u, int v) {
return dist[u][v];
}
inline pll diam_t(int v) {
int ans = v, ans_val = 0;
for (int i = 1; i <= n; i++) {
int t = get(v, i);
f[i] = t;
if (t > ans_val)
ans = i, ans_val = t;
}
return {ans, ans_val};
}
int hubDistance(int N_, int sub) {
n = N_;
memset(sz, 0, sizeof sz);
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
dist[i][j] = dist[j][i] = getDistance(i - 1, j - 1);
int diam_v = diam_t(1).X;
auto [diam_u, diam] = diam_t(diam_v);
int r = numeric_limits<int>::max();
map<int, vector<int>> mp;
for (int i = 1; i <= n; i++) {
int du = get(diam_u, i);
int dv = f[i];
mp[du - dv].push_back(i);
int diff = max(du, dv) - min(du, dv);
int a = (diff + diam) / 2;
r = min(r, a);
}
int tr = 2 * r - diam;
int ps = 0;
int ss = n;
for (auto [x, y] : mp) {
ss -= y.size();
int mx = 0;
vector<int> vec;
for (int e : y) {
vec.push_back(e);
sz[e]++;
for (int x : vec) {
if (x == e) continue;
if (get(e, x) + diam <= min(get(e, diam_u) + get(x, diam_v), get(e, diam_v) + get(x, diam_u))) {
sz[x]++;
sz[e]--;
vec.pop_back();
break;
}
}
}
for (int e : y)
mx = max(mx, sz[e]);
if (x == -1 * tr || x == tr)
if (ps <= n / 2 && ss <= n / 2 && mx <= n / 2)
return r;
ps += y.size();
}
return -r;
}
