#include <bits/stdc++.h>
#include "race.h"
#define pp pair<int, int>
#define F first
#define S second
using namespace std;
const int SZ = 2e5 + 10, M = 1e6 + 10, INF = 1e9;
vector<pp> graph[SZ];
int mn[M], ti[M], c[SZ], n, k, ans = INF, cnt = 0;
bool del[SZ];
void dfs(int u, int p){
c[u] = 1;
for(auto &[v, w] : graph[u]){
if(v == p || del[v]) continue;
dfs(v, u);
c[u] += c[v];
}
}
void upd(int u, int p, int w, int d){
if(w > k) return;
if(ti[w] != cnt) mn[w] = d;
else mn[w] = min(mn[w], d);
ti[w] = cnt;
for(auto &[v, l] : graph[u]){
if(v == p || del[v]) continue;
upd(v, u, w + l, d + 1);
}
}
void calc(int u, int p, int w, int d){
if(w > k) return;
if(ti[k - w] == cnt) ans = min(ans, mn[k - w] + d);
for(auto &[v, l] : graph[u]){
if(v == p || del[v]) continue;
calc(v, u, w + l, d + 1);
}
}
int centroid(int u, int p, int sz) {
for(auto &[v, _] : graph[u]){
if(v == p || del[v]) continue;
if (c[v] > (sz >> 1)) return centroid(v, u, sz);
}
return u;
}
void solve(int u){
dfs(u, 0);
u = centroid(u, 0, c[u]);
del[u] = 1;
ti[0] = ++cnt;
for(auto &[v, w] : graph[u]){
if(del[v]) continue;
calc(v, u, w, 1);
upd(v, u, w, 1);
}
for(auto &[v, _] : graph[u]){
if(!del[v]) solve(v);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
for(int i = 1, u, v, w; i < n; ++i){
u = H[i - 1][0] + 1;
v = H[i - 1][1] + 1;
w = L[i - 1];
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
fill(mn, mn + M - 5, INF);
mn[0] = 0;
solve(1);
if(ans == INF) return -1;
return ans;
}
