#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
using vvll = vector <vll>;
const ll INF = ll(1E18)+16;
struct Info {
ll u1, u2, u3;
ll dis1, dis2, dis3;
ll id;
};
struct DSU {
vll par;
vll sz;
DSU (ll n): par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }
ll find (ll u) {
return u == par[u] ? u : par[u] = find(par[u]);
}
void join (ll u, ll v) {
u = find(u);
v = find(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
par[u] = v;
sz[v] += sz[u];
}
};
int hubDistance (int n, int sub) {
vvll dis(n, vll(n, 0));
for (ll i = 0; i < n; i++) {
for (ll j = i+1; j < n; j++) {
dis[i][j] = dis[j][i] = getDistance(i, j);
}
}
auto fdiss = [&](ll u1, ll u2, ll u3) -> array <ll, 3> {
ll d1 = dis[u1][u2], d2 = dis[u1][u3], d3 = dis[u2][u3];
ll disU1 = (d3-d1-d2)/-2;
ll disU2 = (d2-d1-d3)/-2;
ll disU3 = (d1-d2-d3)/-2;
return { disU1, disU2, disU3 };
};
// for (ll i: fdiss(0, 1, 2) )cerr<<i<< ' ';
// cerr<<'\n';
vector <Info> ve;
ll id = 0;
for (ll u1 = 0; u1 < n; u1++) {
for (ll u2 = u1+1; u2 < n; u2++) {
for (ll u3 = u2+1; u3 < n; u3++) {
auto [dis1, dis2, dis3] = fdiss(u1, u2, u3);
ve.push_back({ u1, u2, u3, dis1, dis2, dis3, id++ });
}
}
}
map <pair <ii, ii>, ll> mp;
DSU dsu(id);
for (auto [u1, u2, u3, dis1, dis2, dis3, id] : ve) {
if (!mp.count({ { u1, dis1 }, { u2, dis2 } })) mp[{ { u1, dis1 }, { u2, dis2 } }] = id;
if (!mp.count({ { u1, dis1 }, { u3, dis3 } })) mp[{ { u1, dis1 }, { u3, dis3 } }] = id;
if (!mp.count({ { u2, dis2 }, { u3, dis3 } })) mp[{ { u2, dis2 }, { u3, dis3 } }] = id;
ll &a = mp[{ { u1, dis1 }, { u2, dis2 } }];
ll &b = mp[{ { u1, dis1 }, { u3, dis3 } }];
ll &c = mp[{ { u2, dis2 }, { u3, dis3 } }];
dsu.join(a, id);
dsu.join(b, id);
dsu.join(c, id);
}
map <ll, ll> mpAns;
for (Info a : ve) {
mpAns[dsu.find(a.id)] = max({ mpAns[dsu.find(a.id)], a.dis1, a.dis2, a.dis3 });
}
// for (Info a : ve) {
// if (a.u1 == 9 && a.dis1 == 13
// || a.u2 == 9 && a.dis2 == 13
// /* || a.u3 == 9 && a.dis3 == 13 */) cerr << dsu.find(a.id) << '\n';
// }
ll ans = INF;
for (auto [_, d] : mpAns) ans = min(ans, d);
// for (auto [_, d] : mp) cerr << _ << ": " << d << '\n';
// cerr << mpAns.size() << '\n';
return ans;
}
