#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
int mem[111][111];
int ask(int i, int j) {
if (i==j) return 0;
if (mem[i][j]) return mem[i][j];
mem[i][j] = mem[j][i] = getDistance(i, j);
return mem[i][j];
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int hubDistance(int n, int ilyashevchenko1love) {
for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) mem[i][j]=0;
vector<int> d0(n), dr(n);
int r=1;
for(int i=1; i<n; ++i) {
d0[i] = ask(0,i);
if (d0[i] > d0[r]) r=i;
}
int l=0;
for(int i=0; i<n; ++i) {
dr[i] = ask(r,i);
if (dr[i] > dr[l]) l=i;
}
int diam = dr[l];
map<int,vector<int>> m;
if (l==0) {
for(int i=0; i<n; ++i) {
int z = (d0[i]+dr[i]-diam)>>1;
m[dr[i]-z].pb(i);
}
} else {
int z0 = (d0[l]+d0[r]-diam)>>1;
int dr0 = dr[0]-z0;
m[dr0].pb(0);
for(int i=1; i<n; ++i) {
if (i==l) {
m[diam].pb(i); continue;
}
if (i==r) {
m[0].pb(i); continue;
}
int z = (d0[i] + dr[i] - d0[r])>>1;
if (dr[i]-z < dr0) {
m[dr[i]-z].pb(i);
} else if (dr[i]-z == dr0) {
m[dr0].pb(i);
} else {
m[dr0].pb(i);
}
}
}
int ans=diam;
for(auto&x:m) {
ans=min(ans,max(x.f,diam-x.f));
}
int left=0,right=n;
for(auto&x:m) {
int z = max(x.f, diam-x.f);
int sz = x.s.size();
right-=sz;
if (z==ans) if (max({left,right,sz}) <= n/2) return ans;
left+=sz;
}
left=0,right=n;
for(auto&x:m) {
int z = max(x.f, diam-x.f);
int sz = x.s.size();
right-=sz;
if (z==ans) if (max(left,right) <= n/2) {
vector<pi> a,b;
for(auto&v:x.s) a.pb({v,1});
while (a.size() > 1) {
vector<pi> c;
shuffle(a.begin(), a.end(), rng);
for(int i=0; i+1<a.size(); i+=2) {
int u=a[i].f, v=a[i+1].f;
int fx = dr[u]-x.f;
int fy = dr[v]-x.f;
int fz = ask(u,v);
if (fz < fx+fy) {
c.pb({u,a[i].s+a[i+1].s});
} else {
b.pb(a[i]);
b.pb(a[i+1]);
}
}
if (a.size()&1) b.pb(a.back());
a=c;
}
if (!a.size()) return ans;
int rt = a[0].f;
int tot = a[0].s;
//cout<<"? "<<tot<<' '<<rt<<'\n';
for(auto&it:b) {
int fx = dr[it.f]-x.f;
int fy = dr[rt]-x.f;
int fz = ask(it.f,rt);
if (fz < fx+fy) tot+=it.s;
if (tot>n/2) return -ans;
}
return ans;
}
left+=sz;
}
return -ans;
}
