#include "race.h"
#include<bits//stdc++.h>
using namespace std;
const int n=2e5;
int k,ans=n+5,cr=n+5;
vector<vector<pair<int,int>>>graph;
map<int,int>dp[n];
void dfs(int u,int p){
dp[u][0]=0;
int v,l;
for(auto&i:graph[u])if(i.first!=p){
dfs(v=i.first,u);
l=i.second;
for(auto&j:dp[v]){
if(j.first+l>k or ans<=j.second+1)break;
if(dp[u].find(k-(j.first+l))!=end(dp[u]))ans=min(ans,j.second+1+dp[u][k-(j.first+l)]);
}
for(auto&j:dp[v]){
if(j.first+l>k or ans<=j.second+1)break;
if(dp[u].find(j.first+l)==end(dp[u]))dp[u][j.first+l]=j.second+1;
else dp[u][j.first+l]=min(dp[u][j.first+l],j.second+1);
}
dp[v].clear();
}
for(auto&i:dp[u])if(i.first==k)ans=min(ans,i.second);
}
void df(int u,int p,int sm,int cn){
if(sm==k){
cr=min(cr,cn);
return;
}
for(auto&i:graph[u])if(i.first!=p)
df(i.first,u,sm+i.second,cn+1);
}
int best_path(int N, int K, int H[][2], int L[])
{
graph.resize(N);
for(int i=0;i<N-1;++i){
graph[H[i][0]].push_back({H[i][1],L[i]});
graph[H[i][1]].push_back({H[i][0],L[i]});
}
k=K;
dfs(0,0);
for(int i=0;i<N;++i)df(i,i,0,0);
ans=(ans==n+5?-1:ans);
cr=(cr==n+5?-1:cr);
assert(ans==cr);
return cr;
}
