#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int k, sum, cnt, best=INT_MAX;
vector<pair<int,int>>adj[1000000];
void dfs(int node, int e) {
if(sum == k) {
best=min(best,cnt);
return;
}
for(auto a : adj[node]) {
if(a.first == e || sum+a.second > k) continue;
sum+=a.second;
cnt++;
dfs(a.first,node);
cnt--;
sum-=a.second;
}
}
int best_path(int N, int K,int H[][2],int L[]) {
k=K;
for(int i = 0 ; i < N-1 ; i++) {
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
for(int root = 0 ; root < N ; root++) {
sum=0;
cnt=0;
dfs(root,-1);
}
return (best==INT_MAX?-1:best);
}
