#include "towns.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=700;
const ll inf=1e9+900;
ll fasta0[maxn];
ll mx[maxn];
ll cnt[maxn];
vector<pii> ger[maxn];
void addYal(ll a,ll b,ll w){
// cout<<a<<' '<<b<<":"<<w<<endl;
ger[a].pb(mp(b,w));
ger[b].pb(mp(a,w));
}
ll findFar(ll a,ll p=-1){
ll ans=0;
for(auto e:ger[a]){
if(e.F!=p){
ans=max(ans,findFar(e.F,a)+e.S);
}
}
return ans;
}
ll shoa(ll n){
ll ans=inf;
for(ll i=0;i<n;i++){
ans=min(ans,findFar(i));
}
return ans;
}
int hubDistance(int n, int sub) {
memset(fasta0,0,sizeof fasta0);
memset(mx,0,sizeof mx);
memset(cnt,0,sizeof cnt);
for(ll i=0;i<maxn;i++){
ger[i].clear();
}
pii far=mp(0,0);
for(ll i=1;i<n;i++){
fasta0[i]=getDistance(0,i);
far=max(far,mp(fasta0[i],i));
}
ll v=far.S;
ll u=0;
ll w=far.F;
vector<pair<ll,pii> > vec;
vector<ll> comp;
// cout<<u<<"<--"<<w<<"-->"<<v<<endl;
for(ll i=1;i<n;i++){
if(i!=v && i!=u){
ll a=getDistance(v,i);
ll b=getDistance(u,i);
ll s123=(a+b+w)/2;
ll s1=s123-a;
ll s2=s123-b;
ll s3=s123-w;
// cout<<s1<<' '<<s2<<' '<<s3<<endl;
vec.pb(mp(i,mp(s1,s3)));
comp.pb(s1);
}
}
sort(comp.begin(),comp.end());
comp.resize(unique(comp.begin(),comp.end())-comp.begin());
addYal(u,n,comp[0]);
for(ll i=0;i+1<comp.size();i++){
addYal(n+i,n+i+1,comp[i+1]-comp[i]);
}
addYal(n+comp.size()-1,v,w-comp.back());
for(auto e:vec){
ll u=lower_bound(comp.begin(),comp.end(),e.S.F)-comp.begin();
addYal(e.F,n+u,e.S.S);
}
return shoa(n+comp.size());
}
