#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;
DSU (ll n): par(n) { 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) {
par[find(u)] = par[find(v)];
}
};
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 = 1; 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++ });
}
}
}
auto fsame = [&](Info a, Info b) {
if (a.u1 == b.u1) return a.dis1 == b.dis1;
if (a.u1 == b.u2) return a.dis1 == b.dis2;
if (a.u1 == b.u3) return a.dis1 == b.dis3;
if (a.u2 == b.u1) return a.dis2 == b.dis1;
if (a.u2 == b.u2) return a.dis2 == b.dis2;
if (a.u2 == b.u3) return a.dis2 == b.dis3;
if (a.u3 == b.u1) return a.dis3 == b.dis1;
if (a.u3 == b.u2) return a.dis3 == b.dis2;
if (a.u3 == b.u3) return a.dis3 == b.dis3;
return false;
};
DSU dsu(id);
map <ll, map <ll, ll> > mp;
for (auto [u1, u2, u3, dis1, dis2, dis3, id] : ve) {
if (mp.count(u1) && mp[u1].count(dis1)) dsu.join(id, mp[u1][dis1]);
if (mp.count(u2) && mp[u2].count(dis2)) dsu.join(id, mp[u2][dis2]);
if (mp.count(u3) && mp[u3].count(dis3)) dsu.join(id, mp[u3][dis3]);
mp[u1][dis1] = id;
mp[u2][dis2] = id;
mp[u3][dis3] = id;
// for (Info b : ve) {
// if (fsame(a, b)) dsu.join(a.id, b.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 });
}
ll ans = INF;
for (auto [_, d] : mpAns) ans = min(ans, d);
// for (auto [_, d] : mp) cerr << _ << ": " << d << '\n';
// cerr << mp.size() << '\n';
return ans;
// vll disToPar(n, INF);
// for (ll i = 1; i < n; i++) {
// for (ll j = i+1; j < n; j++) {
// ll x = dis[i][j], y = dis[i][0], z = dis[j][0];
// ll disI = (z-x-y)/-2, disJ = (y-x-z)/-2;
// disToPar[i] = min(disToPar[i], disI);
// disToPar[j] = min(disToPar[j], disJ);
// }
// }
// DSU dsu(n);
// vll remDis(n, 0);
// for (ll i = 1; i < n; i++) {
// for (ll j = i+1; j < n; j++) {
// ll x = dis[i][j], y = dis[i][0], z = dis[j][0];
// ll disI = (z-x-y)/-2, disJ = (y-x-z)/-2;
// if (disI != disToPar[i] || disJ != disToPar[j]) continue;
// dsu.join(i, j);
// }
// }
return 0;
}
