#pragma once
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define len(s) (ll) s.size()
#define pb push_back
#define S second
#define F first
using namespace std;
typedef int ll;
const int MXN = 2e5 + 11;
const long long inf = 1e18 + 11;
ll n, m, res, lng;
ll sz[MXN], mrk[MXN], d[MXN];
vector < pair < ll, ll > > g[MXN];
multiset < pair < long long, ll > > st;
long long val;
long long path[MXN];
void sizes(ll v, ll p){
sz[v] = 1;
for(auto [u, w] : g[v])
if(u != p)
d[u] = d[v] + 1,
path[u] = path[v] + w,
sizes(u, v),
sz[v] += sz[u];
}
void add(ll v, ll p, ll x){
for(auto [u, w] : g[v])
if(u != p && !mrk[u])
add(u, v, x);
if(x) st.insert({path[v], d[v]});
else st.erase(st.find({path[v], d[v]}));
}
void calc(ll v, ll p, ll lca){
val = lng + 2 * path[lca] - path[v];
auto it = st.lower_bound({val, 0});
if(it != st.end() && (it -> F) == val) res = min(res, d[v] + (it -> S) - 2 * d[lca]);
for(auto [u, w] : g[v])
if(u != p && !mrk[u])
calc(u, v, lca);
}
void small_to_large(ll v, ll p, bool keep){
ll big_child = -1;
for(auto [u, w] : g[v])
if(u != p && (big_child == -1 || sz[u] > sz[big_child]))
big_child = u;
for(auto [u, w] : g[v])
if(u != p && u != big_child)
small_to_large(u, v, 0);
if(big_child != -1)
small_to_large(big_child, v, 1), mrk[big_child] = 1;
st.insert({path[v], d[v]});
for(auto [u, w] : g[v])
if(u != p && !mrk[u])
calc(u, v, v),
add(u, v, 1);
if(big_child != -1)
mrk[big_child] = 0;
val = lng + path[v];
auto it = st.lower_bound({val, 0});
if(it != st.end() && (it -> F) == val) res = min(res, (it -> S) - d[v]);
if(!keep){
for(auto [u, w] : g[v])
if(u != p && !mrk[u])
add(u, v, 0);
st.erase(st.find({path[v], d[v]}));
}
}
int best_path(int N, int K, int H[][2], int L[]){
lng = K, res = MXN;
for(ll i = 0; i < N - 1; i++)
g[H[i][0]].pb({H[i][1], L[i]}),
g[H[i][1]].pb({H[i][0], L[i]});
sizes(0, 0);
small_to_large(0, 0, 0);
if(res == MXN) res = -1;
return res;
}
