#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 map<int, map<int, int> > mmm; int query(int a, int b){ if (a==b)return 0; if (!mmm[min(a, b)][max(a, b)])mmm[min(a, b)][max(a, b)]=getDistance(min(a, b), max(a, b))+1; return mmm[min(a, b)][max(a, b)]-1; } int hubDistance(int n, int sub){ mmm.clear(); vector<int> dist(n, 0), dista(n, 0), distb(n, 0); for (int i=1; i<n; ++i)dist[i]=query(0, i); int mx=-1, a=-1, b=-1, ans=INT_MAX/2, d=-1, d2=-1; 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]=query(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]=query(b, i); for (int i=0; i<n; ++i)ans=min(ans, max(dista[i]-(dista[i]+distb[i]-dista[b])/2, distb[i]-(dista[i]+distb[i]-dista[b])/2)); 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){ if (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; else if (dista[i]-(dista[i]+distb[i]-dista[b])/2<distb[i]-(dista[i]+distb[i]-dista[b])/2)d2=distb[i]-(dista[i]+distb[i]-dista[b])/2; else d=d2=dista[i]-(dista[i]+distb[i]-dista[b])/2; } bool diea=0, dieb=0; if (d!=-1){ vector<int> vect; int ca=1, cb=1; for (int i=0; i<n; ++i)if (i!=a&&i!=b){ if (dista[b]+dista[i]-distb[i]<2*d)++ca; else if (dista[b]+dista[i]-distb[i]>2*d)++cb; else vect.pb(i); } if (ca>n/2||cb>n/2)diea=1; int c=0, count=0, sz=1; for (int i=0; i<vect.size(); ++i){ if (!count)count=1, c=vect[i]; else if (query(vect[i], c)!=dista[vect[i]]+dista[c]-2*d)++count; else --count; } for (int i=0; i<vect.size(); ++i)if (vect[i]!=c&&query(vect[i], c)!=dista[vect[i]]+dista[c]-2*d)++sz; if (sz>n/2)diea=1; } if (d2!=-1){ vector<int> vect; int ca=1, cb=1; for (int i=0; i<n; ++i)if (i!=a&&i!=b){ if (distb[a]+distb[i]-dista[i]<2*d2)++ca; else if (distb[a]+distb[i]-dista[i]>2*d2)++cb; else vect.pb(i); } if (ca>n/2||cb>n/2)dieb=1; int c=0, count=0, sz=1; for (int i=0; i<vect.size(); ++i){ if (!count)count=1, c=vect[i]; else if (query(vect[i], c)!=distb[vect[i]]+distb[c]-2*d2)++count; else --count; } for (int i=0; i<vect.size(); ++i)if (vect[i]!=c&&query(vect[i], c)!=distb[vect[i]]+distb[c]-2*d2)++sz; if (sz>n/2)dieb=1; } if (diea&&dieb&&d!=-1&&d2!=-1)return -ans; if (diea&&d2==-1)return -ans; if (dieb&&d==-1)return -ans; return ans; }