#include<bits/stdc++.h>
using namespace std;
const int N=2e5+3;
const int inf = 1e9+7;
#define ll long long
#define fi first
#define se second
#define VOI void
map<ll,int>best[N];
int ans = inf;
int n,k;
vector<pair<int,ll>>adj[N];
VOI DFS(int u,int pre){
best[u][0] = 0;
for(pair<int,ll> tmp : adj[u]){
int v = tmp.fi;
ll weight = tmp.se;
if(v == pre)continue;
DFS(v,u);
if(best[v].size() > best[u].size())best[u].swap(best[v]);
for(auto [len,paths] : best[v]){
ll newlen = k - weight - len;
if(newlen < 0)continue;
if(best[u].find(newlen) != best[u].end()){
ans = min(ans,paths + 1 + best[u][newlen]);
}
}
for(auto [len,paths] : best[v]){
if(best[u].find(len + weight) == best[u].end())
best[u][len+weight] = inf;
best[u][len + weight] = min(best[u][len + weight],paths);
}
best[v].clear();
}
}
/* === HÀM IOI – CHỈ THAY PHẦN ĐỌC INPUT / OUTPUT === */
int best_path(int _n, int _k, int H[][2], int L[]) {
n = _n;
k = _k;
ans = inf;
for(int i=0;i<n;i++){
adj[i].clear();
best[i].clear();
}
for(int i=0;i<n-1;i++){
int x = H[i][0];
int y = H[i][1];
ll w = L[i];
adj[x].push_back({y,w});
adj[y].push_back({x,w});
}
DFS(0,-1);
if(ans == inf) return -1;
return ans;
}
