#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define pb push_back
struct edge
{
int n, w;
};
int k, ans = 1e9;
vector<edge> g[200002];
map<int, int> cnt[200002];
void dfs(int node, int par)
{
for(edge x : g[node])
{
if(x.n == par) continue ;
dfs(x.n, node);
}
for(edge x : g[node])
{
if(x.n == par) continue ;
for(auto it : cnt[x.n])
{
if(k - it.first - x.w <= 0) continue ;
if(cnt[node].count(k - it.first - x.w)) ans = min(ans, it.second + 1 + cnt[node][k-it.first-x.w]);
}
for(auto it : cnt[x.n])
{
if(it.first + x.w > k) continue ;
if(cnt[node].count(it.first + x.w)) cnt[node][it.first+x.w] = min(cnt[node][it.first+x.w], it.second+1);
else cnt[node][it.first+x.w] = it.second+1;
}
}
if(cnt[node].count(k)) ans = min(ans, cnt[node][k]);
cnt[node][0] = 0;
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for(int i=1 ; i<N ; i++)
{
g[H[i-1][0]+1].pb({H[i-1][1]+1, L[i-1]});
g[H[i-1][1]+1].pb({H[i-1][0]+1, L[i-1]});
}
dfs(1, 0);
printf(ans == 1e9 ? "-1\n" : "%d\n",ans);
return N;
}
