#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int f[110][110];
int g[110];
int cnt[110];
inline int dist(int i, int j) {
if (f[i][j] == -1) return f[i][j] = f[j][i] = getDistance(i, j);
return f[i][j];
}
int hubDistance(int N, int sub) {
int a = 0, b = 0, best = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) f[i][j] = i == j ? 0 : -1;
}
for (int i = 1; i < N; i++) {
if (best < dist(a, i)) best = dist(a, i), b = i;
}
for (int i = 1; i < N; i++) {
if (best < dist(i, b)) best = dist(i, b), a = i;
}
int res = 1e9, c = -1;
for (int i = 0; i < N; i++) {
int ans = max({dist(a, b) + dist(b, i) - dist(a, i),
dist(a, b) + dist(a, i) - dist(b, i),
dist(a, i) + dist(b, i) - dist(a, b)});
if (res > ans) res = ans, c = i;
}
if (sub < 3) return res / 2;
int da = dist(a, c) + dist(a, b) - dist(b, c);
int db = dist(a, b) + dist(b, c) - dist(a, c);
int dc = dist(a, c) + dist(b, c) - dist(a, b);
if (sub == 3) {
for (int i = 0; i < N; i++) g[i] = i;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
bool same_group = 0;
int xa = dist(i, a) + dist(j, a) - dist(i, j);
int xb = dist(i, b) + dist(j, b) - dist(i, j);
int xc = dist(i, c) + dist(j, c) - dist(i, j);
same_group = xa > da || xb > db || xc > dc;
if (same_group) g[j] = g[i];
}
}
for (int i = 0; i < N; i++) cnt[g[i]]++;
for (int i = 0; i < N; i++) {
if (cnt[i] > N / 2) return res / 2;
}
return -res / 2;
}
for (int i = 0; i < N; i++) {
int iab = dist(i, a) + dist(i, b) - dist(a, b);
int iac = dist(i, a) + dist(i, c) - dist(a, c);
int ibc = dist(i, b) + dist(i, c) - dist(b, c);
if (iab == iac) {
cnt[a]++;
} else if (iab == ibc) {
cnt[b]++;
} else if (iac == ibc) {
cnt[c]++;
}
}
for (int i = 0; i < N; i++) {
if (cnt[i] > N / 2) return res / 2;
}
return -res / 2;
}
