#include "towns.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second vector<int> dsu, sz; vector<vector<int> > cant; int fp(int a){ if (dsu[a]==-1)return a; return dsu[a]=fp(dsu[a]); } void merge(int a, int b){ a=fp(a), b=fp(b); if (a==b)return; dsu[a]=b; sz[b]+=sz[a]; for (auto c:cant[a])cant[b].pb(c); } int hubDistance(int n, int sub){ dsu.clear(); sz.clear(); cant.clear(); vector<int> dist(n, 0), dista(n, 0), distb(n, 0); dsu.resize(n, -1); sz.resize(n, 1); cant.resize(n); for (int i=1; i<n; ++i)dist[i]=getDistance(0, i); int mx=-1, a=-1, b=-1, ans=INT_MAX/2, d; for (int i=0; i<n; ++i)if (dist[i]>mx)mx=dist[i], a=i; for (int i=0; i<n; ++i)if (i!=a)dista[i]=getDistance(a, i); mx=-1; for (int i=0; i<n; ++i)if (dista[i]>mx)mx=dista[i], b=i; for (int i=0; i<n; ++i)if (i!=b)distb[i]=getDistance(b, i); for (int i=0; i<n; ++i){ if (max(dista[i]-(dista[i]+distb[i]-dista[b])/2, distb[i]-(dista[i]+distb[i]-dista[b])/2)<ans){ ans=max(dista[i]-(dista[i]+distb[i]-dista[b])/2, distb[i]-(dista[i]+distb[i]-dista[b])/2); d=dista[i]-(dista[i]+distb[i]-dista[b])/2; } } vector<int> vect; for (int i=0; i<n; ++i)if (i!=a&&i!=b){ if (dista[b]+dista[i]-distb[i]<2*d)merge(i, a); else if (dista[b]+dista[i]-distb[i]>2*d)merge(i, b); else vect.pb(i); } for (int aa=0; aa<vect.size(); ++aa)for (int bb=aa+1; bb<vect.size(); ++bb){ int i=vect[aa], j=vect[bb]; bool die=0; for (auto c:cant[fp(i)])if (fp(j)==fp(c))die=1; for (auto c:cant[fp(j)])if (fp(i)==fp(c))die=1; if (die||fp(i)==fp(j))continue; if (getDistance(i, j)==dista[i]+dista[j]-2*d)cant[fp(i)].pb(j), cant[fp(j)].pb(i); else{ merge(i, j); if (sz[fp(i)]>n/2)return -ans; } } for (int i=0; i<n; ++i)if (sz[fp(i)]>n/2)return -ans; return ans; }