#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
#define ff first
#define ss second
const int maxn = 510;
int n, root, m;
int d[maxn][maxn];
vector <ii> adj[maxn];
int s[maxn],id[maxn],nhanh,rt[maxn];
int dp[maxn];
ii par[maxn];
int num = 0;
bool cmp(ii x, ii y)
{
return s[x.ff]>s[y.ff];
}
void dfs(int x, int p)
{
s[x] = 1;
for (ii i:adj[x])
{
dfs(i.ff,x);
par[i.ff] ={x,i.ss};
s[x] += s[i.ff];
}
rt[x] = x;
sort(adj[x].begin(),adj[x].end(),cmp);
if (!adj[x].empty()) rt[x] = rt[adj[x][0].ff];
}
void build(bool nguoc = 0)
{
for (int i=0; i<m; i++) adj[i].clear(), rt[i] = -1, s[i] = 0;
for (int i=0; i<m; i++)
{
ii u = par[i];
if (u.ff==i||u.ff==-1) continue;
adj[u.ff].push_back({i,u.ss});
if (nguoc) adj[i].push_back({u.ff,u.ss});
}
if (!nguoc) dfs(root,root);
}
int Ask(int u, int v)
{
if (u>v) swap(u,v);
if (d[u][v] == -1)
{
num++;
assert(num<=5*n);
d[u][v] = getDistance(u,v);
}
return d[u][v];
}
void addNode(int p, int w)
{
par[m++] = {p,w};
}
iii get(int a, int b, int c)
{
/**
d = lca(b,c);
**/
int ad = (Ask(a,b) + Ask(a,c) - Ask(b,c) ) /2;
int bd = Ask(a,b) - ad;
int cd = Ask(a,c) - ad;
// cerr<<a<<' '<<b<<' '<<c<<" ?? "<<ad<<' '<<bd<<' '<<cd<<endl;
return {ad,{bd,cd}};
}
void dfs2(int x, int p)
{
s[x] = (x<n);
dp[x] = 0;
for (ii i:adj[x])
if (i.ff!=p)
{
dfs2(i.ff,x);
s[x] += s[i.ff];
dp[x] = max(dp[x],dp[i.ff]+i.ss);
}
}
int hubDistance(int N, int sub) {
vector <int> a;
n=N; m=n;
for (int i=0; i<n; i++) a.push_back(i);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) d[i][j] = -1;
// random_shuffle(a.begin(),a.end());
for (int i=0; i<n; i++) par[i] = {-1,-1};
root = a[0];
iii temp = get(a[0],a[1],a[2]);
addNode(root,temp.ff);
par[1] = {m-1,temp.ss.ff};
par[2] = {m-1,temp.ss.ss};
// for (int j=0; j<m; j++) cerr<<par[j].ff<<','<<par[j].ss<<' '; cerr<<endl;
for (int i=3; i<n; i++)
{
build();
int x = root;
int dist_temp = 0;
while (true)
{
bool check = 1;
for (ii j:adj[x])
{
int v = j.ff;
iii temp = get(root,rt[v],a[i]);
if (temp.ff == dist_temp) continue;
int u = rt[v];
int dist = 0;
while (u!=x&&dist + par[u].ss <= temp.ss.ff)
{
dist+=par[u].ss;
u=par[u].ff;
}
// cerr<<x<<' '<<rt[v]<<' '<<a[i]<<" = "<<u<<' '<<par[u].ff<<','<<par[u].ss<<" : "<<temp.ss.ff<<' '<<dist<<endl;
if (dist == temp.ss.ff)
{
x=u; check = 0;
dist_temp = temp.ff;
par[a[i]] = {x,temp.ss.ss};
break;
}
else
{
addNode(par[u].ff,dist + par[u].ss - temp.ss.ff);
par[u] = {m-1, temp.ss.ff - dist};
x=u;
par[a[i]] = {m-1,temp.ss.ss};
check=1;
break;
}
}
if (check) break;
}
// for (int j=0; j<m; j++) cerr<<par[j].ff<<','<<par[j].ss<<' '; cerr<<endl;
}
build(1);
// for (int i=0; i<m; i++)
// {
// cerr<<i<<" := ";
// for (ii j:adj[i]) cerr<<j.ff<<','<<j.ss<<" "; cerr<<endl;
// }
int R = 1e9;
int it = -1;
for (int i=n; i<m; i++)
{
dfs2(i,i);
bool ccheck = 1;
for (ii j:adj[i]) if (s[j.ff] > n/2) ccheck = 0;
// cerr<<dp[i]<<" :: "<<ccheck<<endl;
if (dp[i] < R)
{
R = dp[i];
it = ccheck;
}
else if (dp[i] == R) it |=ccheck;
}
if (!it) R = -R;
return R;
}
