#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int dist[300][300], lst;
struct DSU {
vector <int> sze, par;
void init (int n) {
sze = vector <int> (n, 1);
par = vector <int> (n, 0);
iota(par.begin(), par.end(), 0);
}
int find (int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
bool merge (int x, int y) {
x = find(x); y = find(y);
if (x == y) {
return 0;
}
if (sze[x] > sze[y]) {
swap(x, y);
}
sze[y] += sze[x]; par[x] = y;
return 1;
}
};
int hubDistance (int n, int sub) {
if (sub == 3) {
lst = n - 1;
for (int i = 0; i < n; i++) {
dist[i][i] = 0;
for (int j = i + 1; j < n; j++) {
dist[i][j] = dist[j][i] = getDistance(i, j);
}
}
int x = -1, y = -1;
for (int i = 0; i < n; i++) {
if (x == -1 || dist[0][i] > dist[0][x]) {
x = i;
}
}
for (int i = 0; i < n; i++) {
if (y == -1 || dist[x][i] > dist[x][y]) {
y = i;
}
}
map <int, vector <int>> path;
int mn = 1e9;
for (int i = 0; i < n; i++) {
path[dist[x][i] - dist[y][i]].push_back(i);
mn = min(mn, abs(dist[x][i] - dist[y][i]));
}
int pref = 0, sum = n;
int flag = 0;
for (auto i : path) {
int suff = sum - (int)i.second.size() - pref;
if (abs(i.first) != mn) {
pref += (int)i.second.size();
continue;
}
if (pref > n / 2 || suff > n / 2) {
pref += (int)i.second.size();
continue;
}
int g = (dist[x][y] + i.first) / 2;
DSU cur;
cur.init(n);
for (auto j : i.second) {
for (auto k : i.second) {
if (dist[j][k] != (dist[j][x] - g) + (dist[k][x] - g)) {
cur.merge(j, k);
}
}
}
int bad = 0;
for (auto j : i.second) {
if (cur.sze[cur.find(j)] > n / 2) {
bad = 1;
}
}
flag |= !bad;
pref += (int)i.second.size();
}
mn = (mn + dist[x][y]) / 2;
if (flag) {
return mn;
} else {
return -mn;
}
}
int x = -1, v = 0;
for (int i = 1; i < n; i++) {
int s = getDistance(0, i);
if (s > v) {
v = s; x = i;
}
}
int y = -1, u = 0;
vector <int> dist_x(n, 0);
for (int i = 0; i < n; i++) {
if (i != x) {
int s = getDistance(x, i);
dist_x[i] = s;
if (s > u) {
u = s; y = i;
}
}
}
int w = 1e9;
for (int i = 0; i < n; i++) {
if (i != x && i != y) {
int s = dist_x[i];
int t = getDistance(y, i);
w = min(w, abs(s - t));
}
}
//x + y = u
//x - y = w
//x = (u + w) / 2;
return (u + w) / 2;
}
