#include <bits/stdc++.h>
//#include "towns.h"
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 0;
int getDistance(int i, int j);
int hubDistance(int n, int sub){
vector<int> ds (n,0), db(n,0), da(n,-1);
int a = 0, b;
int maxi = -1;
for(int i = 1; i < n; i++){
ds[i] = getDistance(0,i);
if(ds[i] > maxi)
maxi = ds[i], b = i;
}
maxi = ds[b];
db[0] = ds[b];
for(int i = 1; i < n; i++){
if(i==b)
continue;
db[i] = getDistance(b,i);
if(db[i] > maxi)
maxi = db[i], a = i;
}
da[a] = 0;
da[b] = db[a];
da[0] = ds[a];
vector<int> dlca(n,0), v(n,0);
for(int i = 0; i < n; i++){
dlca[i] = (db[0] + db[i] - ds[i])>>1;
}
iota(v.begin(), v.end(), 0);
sort(v.begin(),v.end(),[&](int x, int y){
return dlca[x] > dlca[y];
});
vector<bool> type(n,0);
// se type = 1, faz parte da subarvore de s
int resp = max(ds[a] + db[a] - ds[b],ds[b] + da[b] - ds[a])>>1;
// resposta comeca com o ponto do caminho (a,b) que intersecta com o caminho de (s,a) e (s,b)
type[0] = 1;
vector<int> retirar;
for(int i = 1; i < n; i++){
int cur = v[i];
if(dlca[cur] == dlca[v[i-1]]){
type[cur] = 1;
retirar.push_back(cur);
continue;
}
if(da[cur] == -1)
da[cur] = getDistance(a,cur);
int d1 = (da[cur] + db[a] - db[cur])>>1;
int d2 = (db[cur] + da[b] - da[cur])>>1;
if(max(d1,d2) > resp){
break;
}
resp = max(d1,d2);
type[cur] = 1;
retirar.clear();
retirar.push_back(cur);
}
for(int i : retirar)
type[i] = 0;
return resp;
}
