#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN=200100;
struct edge{int v,d,nxt;}a[maxN*2];
int k,tmp=0,ans=-1,head[maxN],vis[maxN];
void add(int u,int v,int d){
a[tmp].v=v;a[tmp].d=d;a[tmp].nxt=head[u];head[u]=tmp++;
}
void dfs(int u,int s,int ed){
vis[u]=1;
// printf("to->%d dis:%d vis_edge:%d\n",u,s,ed);
if(s==k){
if(ed<ans||ans==-1)ans=ed;
return;
}
for (int i=head[u];i!=-1;i=a[i].nxt){
int v=a[i].v,d=a[i].d;
if (vis[v])continue;
if(s+d<=k)dfs(v,s+d,ed+1);
}
}
int best_path(int N, int K, int H[][2], int L[]){
k=K;
for (int i=0;i<N;i++)head[i]=-1;
for (int i=0;i<N-1;i++){
add(H[i][0],H[i][1],L[i]);
add(H[i][1],H[i][0],L[i]);
}
for (int i=0;i<N;i++){
memset(vis,0,sizeof(vis));
dfs(i,0,0);
}
return ans;
}
