#include "towns.h"
#include <bits/stdc++.h>
struct Dsu {
std::vector <int> p;
Dsu (int s) {
p.resize(s);
std::iota(p.begin(), p.end(), 0);
}
int find(int v) {
return v == p[v] ? v : (p[v] = find(p[v]));
}
void unite(int u, int v) {
p[find(u)] = find(v);
}
void print() {
for (int i = 0; i < (int) p.size(); i++) std::cerr << find(i) << " ";
std::cerr << std::endl;
}
};
std::vector <std::vector <int>> mem;
int ask(int i, int j) {
if (i == j) return 0;
if (mem[i][j]) return mem[i][j];
if (mem[j][i]) return mem[j][i];
return mem[i][j] = mem[j][i] = getDistance(i, j);
}
int hubDistance(int n, int sub) {
mem = std::vector <std::vector <int>> (n, std::vector <int> (n, 0));
int l1, l2;
int mx = 0;
for (int i = 1; i < n; i++) {
int val = ask(0, i);
if (val > mx) {
mx = val;
l1 = i;
}
}
std::vector <int> dl1(n, -1);
std::vector <int> dl2(n, -1);
mx = 0;
for (int i = 0; i < n; i++) {
if (i == l1) {
continue;
}
dl1[i] = ask(l1, i);
if (dl1[i] > mx) {
mx = dl1[i];
l2 = i;
}
}
for (int i = 0; i < n; i++) {
if (i == l2) {
continue;
}
dl2[i] = ask(l2, i);
}
int r = 1 << 30;
std::vector <int> to(n);
int xx, yy;
for (int i = 0; i < n; i++) {
if (i == l1 || i == l2) {
continue;
}
to[i] = (dl1[i] + dl2[i] - dl1[l2]) / 2;
int x = (dl1[l2] + dl1[i] - dl2[i]) / 2;
int y = (dl2[l1] + dl2[i] - dl1[i]) / 2;
if (std::max(x, y) < r) {
xx = x;
yy = y;
r = std::max(x, y);
}
}
//if (sub <= 2) {
//return r;
//}
to[l1] = xx;
to[l2] = yy;
std::vector <bool> vis(n, false);
Dsu dsu(n);
vis[l1] = vis[l2] = true;
for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
bool bad = false;
bad |= to[l1] != ask(l1, i) - to[i];
bad |= to[l2] != ask(l2, i) - to[i];
if (bad) {
//std::cerr << i << " is" << std::endl;
vis[i] = true;
int vl1 = ask(l1, i) - to[i];
if (vl1 > to[l1]) {
dsu.unite(l2, i);
} else {
dsu.unite(l1, i);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (vis[i] || vis[j]) {
continue;
}
if (ask(i, j) != to[i] + to[j]) {
dsu.unite(i, j);
}
}
}
std::vector <int> siz(n, 0);
int max = 0;
for (int i = 0; i < n; i++) {
max = std::max(max, ++siz[dsu.find(i)]);
}
//dsu.print();
//std::cerr << "n = " << n << " ; max = " << max << std::endl;
if (max <= n / 2) return r;
return -r;
}
