#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int melhor(int v, vector<vector< pair<int,int> > > &adj, vector<int> &visit, int k,int parcial = 0) {
if(visit[v]) return INT_MAX;
visit[v] = true;
if(k==0) {
return parcial;
}
int mi= INT_MAX;
for(auto &[w,peso]: adj[v]) {
mi = min(mi, melhor(w,adj,visit,k-peso,parcial+1));
}
return mi;
}
int best_path(int n, int k, int H[][2], int L[])
{
vector<vector< pair<int,int> > > adj(n);
for(int i=0;i<n-1;i++) {
int a = H[i][0];
int b = H[i][1];
int w = L[i];
adj[a].push_back(make_pair(b,w ) );
adj[b].push_back(make_pair(a,w ) );
}
int mi= INT_MAX;
for(int i=0;i<n;i++) {
vector<int> visit(n,false);
int ans = melhor(i,adj,visit,k);
mi = min(mi, ans);
}
if(mi==INT_MAX) mi = -1;
return mi;
}
