#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using vl = vector<ll>;
#define mp make_pair
#define f first
#define s second
// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define ins insert
#define pf push_front
#define pb push_back
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MOD = 1e9+7; // 998244353;
const ll INF = 1e18; // not too close to LLONG_MAX
// #define int ll
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!!
const int MAXN = 1e6+5;
const int LOGN = 25;
ll n,current_tree = 0;
vector<pl> g[MAXN];
ll best[MAXN],deleted[MAXN];
ll depth[MAXN];
ll par[MAXN],sub[MAXN];
ll dist[LOGN][MAXN];
// initally all nodes are red
ll LCA(ll u,ll v){
// finds LCA in of u and v in the centroid tree
while(u != v){
if(depth[u] < depth[v])
v = par[v]; // get v a level up
else
u = par[u]; // get u a level up
}
return u;
}
ll compute_dist(ll x,ll y){
ll lc = depth[LCA(x,y)];
return dist[lc][x] + dist[lc][y];
}
void find_subtree(ll u,ll p){
sub[u] = 1;
current_tree++;
trav(P,g[u]){
int v = P.f;
if(deleted[v] == 0 && v != p){
find_subtree(v,u);
sub[u] += sub[v];
}
}
}
ll find_centroid(ll u,ll p){
trav(P,g[u]){
ll v = P.f;
if(deleted[v] == 0 && v !=p && sub[v] > (current_tree / 2)) return find_centroid(v,u);
}
return u;
}
void dfs(ll u,ll p,ll lvl,ll dd){
dist[lvl][u] = dd;
trav(P,g[u]){
ll v = P.f;
ll w = P.s;
if(deleted[v] == 0 && v != p){
dfs(v,u,lvl,dd + w);
}
}
}
void decompose(ll root,ll p){
current_tree = 0;
find_subtree(root,p);
ll cen = find_centroid(root,p);
par[cen] = p;
if(p != -1) depth[cen] = depth[p] + 1;
dfs(cen,p,depth[cen],0);
deleted[cen] = 1;
trav(P,g[cen]){
int v = P.f;
if(deleted[v] == 1) continue;
decompose(v,cen);
}
}
ll query(ll u){
// find the nearest blue node to u
ll ans = best[u];
ll x = u;
u = par[u];
while(u != -1){
ans = min(ans,compute_dist(x,u) + best[u]);
u = par[u];
}
return ans;
}
void update(ll u){
// colour node u to blue
ll x = u;
while(u != -1){
best[u] = min(best[u],compute_dist(u,x));
u = par[u];
}
}
void remove_col(ll u){
// u has to be a blue node
// remove its colour
while(u != -1){
best[u] = INF;
u = par[u];
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
FOR(i,0,n-1){A[i]++,B[i]++;
g[A[i]].pb(mp(B[i],D[i]));
g[B[i]].pb(mp(A[i],D[i]));
}
for(int i =1;i<=n;i++) best[i] = INF;
decompose(1,-1);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i =0;i<S;i++) X[i]++;
for(int i =0;i<T;i++) Y[i]++;
for(int i = 0;i < T;i++){
update(Y[i]);
}
ll ans = INF;
for(int i = 0;i< S;i++){
ans = min(ans,query(X[i]));
}
for(int i =0;i<T;i++){
remove_col(Y[i]);
}
return ans;
}
/* void solve(){
cin >> n;
int q;
cin >> q;
FOR(i,2,n+1){
int u,v,w;
cin >> u >> v >> w;
u++,v++;
g[u].pb(mp(v,w));
g[v].pb(mp(u,w));
}
for(int i =1;i<=n;i++) best[i] = INF;
decompose(1,-1);
FOR(i,1,n+1){
cout << i << " " << par[i] << endl;
}
while(q--){
int s,t;
cin >> s >> t;
vl u(s),v(t);
for(int i =0;i<s;i++) cin >> u[i],u[i]++;
for(int i =0;i<t;i++) cin >> v[i],v[i]++;
for(int i = 0;i < t;i++){
update(v[i]);
}
int ans = INF;
for(int i = 0;i< s;i++){
ans = min(ans,query(u[i]));
}
cout << ans << endl;
for(int i =0;i<t;i++){
remove_col(v[i]);
}
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
// you should actually read the stuff at the bottom
int t=1;
// cin >> t;
while(t--){
solve();
}
} */
/* stuff you should look for
* read the probem 3 more times in case of WA :)
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
