#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
#define ii pair<int, int>
#define mp make_pair
int A, B;
int dA, dB;
map<ii, int> cached;
int getD(int a, int b) {
if (a == b) return 0;
if (a > b) swap(a, b);
if (cached.count(mp(a, b))) return cached[mp(a, b)];
return cached[mp(a, b)] = getDistance(a, b);
}
int isInA(int x) {
return (getD(x, A) + getD(A, B) - getD(B, x)) / 2 < dA;
}
int isInB(int x) {
return (getD(x, B) + getD(A, B) - getD(A, x)) / 2 < dB;
}
int getR(int x) {
if (isInA(x) || isInB(x)) assert(false);
return (getD(A, x) + getD(B, x) - getD(A, B)) / 2;
}
int hubDistance(int N, int sub) {
cached.clear();
int maxDist = -1;
A = -1;
for (int i = 1; i < N; i++) {
int d = getD(0, i);
if (d > maxDist) {
maxDist = d;
A = i;
}
}
maxDist = -1;
B = -1;
for (int i = 0; i < N; i++) {
int d = getD(A, i);
if (d > maxDist) {
maxDist = d;
B = i;
}
}
int opt = 1e9;
for (int i = 0; i < N; i++) {
int distTo0 = getD(B, i);
int distTo1 = getD(A, i);
int dist0 = (maxDist + distTo0 - distTo1)/2;
int dist1 = (maxDist + distTo1 - distTo0)/2;
if (max(dist0, dist1) < opt) {
opt = max(dist0, dist1);
dA = dist1;
dB = dist0;
}
}
int mult = 1;
for (int i = 0; i < N; i++) {
int sz = 0;
if (isInA(i) || isInB(i)) continue;
for (int j = 0; j < N; j++) {
if (isInA(j) || isInB(j)) continue;
if (getD(i, j) != getR(i) + getR(j)) {
sz++;
}
}
if (sz > N/2) {
mult = -1;
}
}
int sz = 0;
for (int i = 0; i < N; i++) {
if (isInA(i)) {
sz++;
}
}
if (sz > N/2) mult = -1;
sz = 0;
for (int i = 0; i < N; i++) {
if (isInB(i)) sz++;
}
if (sz > N/2) mult = -1;
return opt*mult;
}
