#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> >adj[1000010];
int ans = INT_MAX;
vector<long long>preff;
void dfs(int v, int p, int k)
{
long long sum = preff.back();
if(sum == k)
{
ans = min(ans, (int)preff.size() - 1);
}
if(sum > k)
{
int need = sum - k;
int indx = lower_bound(preff.begin(), preff.end(), need) - preff.begin();
if(preff[indx] == need)
{
ans = min(ans, (int)preff.size() - indx - 1);
}
}
for(auto to: adj[v])
{
if(to.first == p)continue;
preff.push_back(preff.back() + to.second);
dfs(to.first, v, k);
}
preff.pop_back();
}
int best_path(int N, int K, int H[][2], int L[])
{
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]});
}
preff.push_back(0);
dfs(0, 0, K);
if(ans == INT_MAX)return -1;
return ans;
}
