#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int hubDistance(int n, int sub) {
vector<vector<int>> w(n, vector<int>(n, -1));
for (int i = 0; i < n; i++) {
w[i][i] = 0;
}
auto Ask = [&](int i, int j) {
if (w[i][j] == -1) {
int d = getDistance(i, j);
w[i][j] = w[j][i] = d;
}
return w[i][j];
};
int v, u;
{
vector<int> dist(n);
for (int i = 1; i < n; i++) {
dist[i] = Ask(0, i);
}
v = (int) (max_element(dist.begin(), dist.end()) - dist.begin());
}
{
vector<int> dist(n);
for (int i = 0; i < n; i++) {
dist[i] = Ask(i, v);
}
u = (int) (max_element(dist.begin(), dist.end()) - dist.begin());
}
int diam = Ask(v, u);
int res = diam;
vector<int> f;
vector<int> d(n);
vector<int> e(n);
for (int i = 0; i < n; i++) {
if (u == i || v == i) {
continue;
}
int d_vi = Ask(v, i);
int d_ui = Ask(u, i);
int diff = d_vi - d_ui;
// dv + du = diam
// dv - du = diff
int dv = (diam + diff) / 2;
int du = diam - dv;
d[i] = d_vi - dv;
e[i] = dv;
res = min(res, max(dv, du));
f.push_back(dv);
}
sort(f.begin(), f.end());
vector<int> ch;
for (int i = 0; i < (int) f.size(); i++) {
if (i == 0 || f[i] != f[i - 1]) {
ch.push_back(1);
} else {
ch.back() += 1;
}
}
f.erase(unique(f.begin(), f.end()), f.end());
assert(is_sorted(f.begin(), f.end()));
int m = (int) f.size();
{
int L = 1, R = n - 1;
for (int i = 0; i < m; i++) {
R -= ch[i];
if (res == max(f[i], diam - f[i])) {
if (L <= n / 2 && R <= n / 2 && ch[i] <= n / 2) {
return res;
}
}
L += ch[i];
}
}
auto Connected = [&](int x, int y) {
int d_xy = Ask(x, y);
return d_xy < d[x] + d[y];
};
auto Solve = [&](int r) {
vector<int> ver;
for (int i = 0; i < n; i++) {
if (i != u && i != v && e[i] == f[r]) {
ver.push_back(i);
}
}
if ((int) ver.size() <= n / 2) {
return true;
}
int maj = -1;
int bal = 0;
for (int i : ver) {
if (bal == 0) {
maj = i;
bal = 1;
} else {
if (Connected(maj, i)) {
bal++;
} else {
bal--;
}
}
}
vector<int> que(1, maj);
vector<bool> in(n);
in[maj] = true;
vector<bool> seen(n);
seen[maj] = true;
while ((int) que.size() < (int) ver.size()) {
for (int b = 0; b < (int) que.size(); b++) {
int i = que[b];
for (int j = 0; j < n; j++) {
if (!seen[j] && w[i][j] != -1 && (Connected(i, j) || in[i])) {
seen[j] = true;
in[j] = (in[i] && Connected(i, j));
que.push_back(j);
}
}
}
for (int i : ver) {
if (!seen[i]) {
in[i] = Connected(i, maj);
que.push_back(i);
seen[i] = true;
break;
}
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt += in[i];
}
return cnt <= n / 2;
};
int L = 1, R = n - 1, med = 0;
for (int i = 0; i < m; i++) {
R -= ch[i];
if (res == max(f[i], diam - f[i])) {
if (L <= n / 2 && R <= n / 2 && Solve(i)) {
return res;
}
}
L += ch[i];
}
return -res;
}
/*
1 1
11
0 17 18 20 17 12 20 16 23 20 11
17 0 23 25 22 17 25 21 28 25 16
18 23 0 12 21 16 24 20 27 24 17
20 25 12 0 23 18 26 22 29 26 19
17 22 21 23 0 9 21 17 26 23 16
12 17 16 18 9 0 16 12 21 18 11
20 25 24 26 21 16 0 10 29 26 19
16 21 20 22 17 12 10 0 25 22 15
23 28 27 29 26 21 29 25 0 21 22
20 25 24 26 23 18 26 22 21 0 19
11 16 17 19 16 11 19 15 22 19 0
17
*/
