#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int dist[300][300], lst;
int query (int x, int y) {
if (x == y) {
return 0;
}
if (dist[x][y] != -1) {
return dist[x][y];
}
int c = getDistance(x, y);
dist[x][y] = dist[y][x] = c;
return c;
}
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) {
memset(dist, -1, sizeof(dist));
if (sub == 3) {
int x = -1, y = -1;
for (int i = 0; i < n; i++) {
if (x == -1 || query(0, i) > query(0, x)) {
x = i;
}
}
for (int i = 0; i < n; i++) {
if (y == -1 || query(x, i) > query(x, y)) {
y = i;
}
}
map <int, vector <int>> path;
int mn = 1e9;
for (int i = 0; i < n; i++) {
path[query(x, i) - query(y, i)].push_back(i);
mn = min(mn, abs(query(x, i) - query(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 = (query(x, y) + i.first) / 2;
DSU cur;
cur.init(n);
for (auto j : i.second) {
for (auto k : i.second) {
if (query(j, k) != (query(j, x) - g) + (query(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 + query(x, y)) / 2;
if (flag) {
return mn;
} else {
return -mn;
}
}
if (sub == 4) {
int x = -1, y = -1;
for (int i = 0; i < n; i++) {
if (x == -1 || query(0, i) > query(0, x)) {
x = i;
}
}
for (int i = 0; i < n; i++) {
if (y == -1 || query(x, i) > query(x, y)) {
y = i;
}
}
map <int, vector <int>> path;
int mn = 1e9;
for (int i = 0; i < n; i++) {
path[query(x, i) - query(y, i)].push_back(i);
mn = min(mn, abs(query(x, i) - query(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 bad = i.second.size() > n / 2;
flag |= !bad;
pref += (int)i.second.size();
}
mn = (mn + query(x, y)) / 2;
if (flag) {
return mn;
} else {
return -mn;
}
}
int x = -1, v = 0;
for (int i = 1; i < n; i++) {
int s = query(0, i);
if (s > v) {
v = s; x = i;
}
}
int y = -1, u = 0;
for (int i = 0; i < n; i++) {
if (i != x) {
int s = query(x, i);
if (s > u) {
u = s; y = i;
}
}
}
int w = 1e9;
for (int i = 0; i < n; i++) {
if (i != x && i != y) {
int s = query(x, i);
int t = query(y, i);
w = min(w, abs(s - t));
}
}
//x + y = u
//x - y = w
//x = (u + w) / 2;
return (u + w) / 2;
}
