#include "towns.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 105;
int dist[MAX_N][MAX_N];
int n;
int Dist(int v, int u) {
if (u == v) return 0;
if (dist[v][u] == -1) {
dist[v][u] = dist[u][v] = getDistance(u, v);
}
return dist[v][u];
}
struct Dsu{
vi par, sz;
Dsu(int n) {
par.resize(n), sz.resize(n, 1);
iota(all(par), 0);
}
int Find(int i) {
return par[i] == i ? i : par[i] = Find(par[i]);
}
void Union(int a, int b) {
int pa = Find(a), pb = Find(b);
if (pa == pb) return;
if (sz[pa] < sz[pb]) swap(pa, pb);
par[pb] = pa;
sz[pa] += sz[pb];
}
};
int dist_center[MAX_N];
bitset<MAX_N> interesting;
inline bool Same(int i, int j) {
if (!interesting[i] || !interesting[j]) return false;
return Dist(i, j) < dist_center[i] + dist_center[j];
}
bool CheckCentroid(int v, int d1, int u, int d2) {
dist_center[v] = d1, dist_center[u] = d2;
vi s;
interesting.reset();
for (int i = 0; i < n; i++) {
if (i == v || i == u) continue;
int a1 = Dist(v, u), a2 = Dist(v, i), a3 = Dist(u, i);
int x, y, z;
z = (a2 + a3 - a1) >> 1;
x = a2 - z, y = a3 - z;
if (x <= d1) {
dist_center[i] = z + d1 - x;
} else {
dist_center[i] = z + d2 - y;
}
s.push_back(x);
if (x == d1) interesting[i] = true;
}
s.push_back(0), s.push_back(d1 + d2);
sort(all(s));
if (n & 1 && s[n / 2] != d1) return false;
if (!(n & 1) && s[n / 2] != d1 && s[n / 2 - 1] != d1) return false;
stack<int> list, bucket;
list.push(0);
for (int i = 1; i < n; i++) {
if (!Same(list.top(), i)) {
list.push(i);
if (!bucket.empty()) {
list.push(bucket.top());
bucket.pop();
}
} else {
bucket.push(i);
}
}
int x = list.top();
while (!list.empty()) {
if (Same(list.top(), x)) {
if (list.size() == 1) {
bucket.push(list.top());
break;
}
list.pop();
} else {
if (bucket.empty()) return true;
bucket.pop();
}
list.pop();
}
return bucket.empty();
}
int hubDistance(int N, int sub) {
n = N;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = -1;
}
}
pii p1 = {0, 0}, p2 = {0, 0}, q;
for (int i = 1; i < n; i++) {
q = {Dist(0, i), i};
chkmax(p1, q);
}
int v = p1.y;
for (int i = 0; i < n; i++) {
q = {Dist(v, i), i};
chkmax(p2, q);
}
int u = p2.y;
int ans = dist[v][u];
vii dists;
for (int k = 0; k < n; k++) {
if (k == v || k == u) continue;
int a1 = Dist(v, u), a2 = Dist(v, k), a3 = Dist(u, k);
int x, y, z;
z = (a2 + a3 - a1) >> 1;
x = a2 - z, y = a3 - z;
dists.push_back({x, y});
chkmin(ans, max(x, y));
}
//if (sub <= 2) return ans;
vii hubs;
for (pii p : dists) {
if (max(p.x, p.y) == ans) hubs.push_back(p);
}
sort(all(hubs));
hubs.erase(unique(all(hubs)), hubs.end());
for (pii p : hubs) {
if (CheckCentroid(v, p.x, u, p.y)) return ans;
}
return -ans;
}
/*
1 1
5
0 52 53 53 51
52 0 3 3 3
53 3 0 2 4
53 3 2 0 4
51 3 4 4 0
*/
/*
1 1
4
0 3 3 2
3 0 2 3
3 2 0 3
2 3 3 0
*/
