#include <bits/stdc++.h>
#include "race.h"
using namespace std;
// #include "grader.cpp"
#define all(x) x.begin(), x.end()
const int mxN = 2e5 + 5;
vector<pair<int, int>> adj[mxN];
map<long long, int> mp;
int sbz[mxN], del[mxN];
int k;
int ans = 1e9;
void dfs(int v, int p) {
sbz[v] = 1;
for(auto [to, w] : adj[v]) {
if(to == p || del[to]) continue;
dfs(to, v);
sbz[v] += sbz[to];
}
}
int Centroid(int v, int p, int size) {
for(auto [to, w] : adj[v]) {
if(to == p || del[to]) continue;
if(sbz[to] * 2 > size) {
return Centroid(to, v, size);
}
}
return v;
}
void Ans(int v, int p, int d, long long cost) {
if(mp.count(k - cost)) {
ans = min(ans, d + mp[k - cost]);
}
for(auto [to, w] : adj[v]) {
if(to == p || del[to]) continue;
Ans(to, v, d + 1, cost + w);
}
}
void Cnt(int v, int p, int d, long long cost) {
if(mp.count(cost)) {
mp[cost] = min(mp[cost], d);
} else mp[cost] = d;
for(auto [to, w] : adj[v]) {
if(to == p || del[to]) continue;
Cnt(to, v, d + 1, cost + w);
}
}
void Decom(int v) {
dfs(v, v);
int C = Centroid(v, v, sbz[v]);
mp.clear();
mp[0] = 0;
for(auto [to, w] : adj[C]) {
if(del[to]) continue;
Ans(to, C, 1, w);
Cnt(to, C, 1, w);
}
del[C] = 1;
for(auto [to, w] : adj[C]) {
if(!del[to]) Decom(to);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for(int i = 0; i < N - 1; i++) {
auto [u, v] = H[i];
adj[u].emplace_back(v, L[i]);
adj[v].emplace_back(u, L[i]);
}
Decom(0);
return (ans == 1e9 ? -1 : ans);
}
