#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define MAXI (int)1e5
vector<int> ad[MAXI];
int shortest = 1e9;
int len = 0;
map<pair<int,int>,int> paths;
void dfs(int x,int e,ll summe,int cnt){
if(summe > len || cnt > shortest) return;
if(summe == len){
shortest = min(shortest,cnt);
return;
}
for(auto s: ad[x]){
if(s == e) continue;
dfs(s,x,summe+paths[{x,s}],cnt+1);
}
}
int best_path(int n, int k, int h[][2], int l[]){
len = k;
for(int i = 0;i<n-1;i++){
int u = h[i][0];
int v = h[i][1];
ad[u].push_back(v);
ad[v].push_back(u);
paths.insert({{u,v},l[i]});
paths.insert({{v,u},l[i]});
}
for(int i = 1;i<=n;i++){
dfs(i,i,0,1);
}
if(shortest == 1e9) return -1;
return shortest-1;
}
