#include <bits/stdc++.h>
using namespace std;
int best_path(int N, int K, int H[][2], int L[]){
unordered_map<int,int> m[N];
unordered_map<int,int> m2[N];
vector<vector<pair<int,int>>> adj(N);
for (int i = 1; i < N; i++){
adj[H[i-1][0]].push_back({H[i-1][1], L[i-1]});
adj[H[i-1][1]].push_back({H[i-1][0], L[i-1]});
}
int back[N];
fill(back, back+N, 0);
int best = N+1;
function<void(int,int)> dfs = [&](int x, int prev){
m[x][0] = 0;
for (auto nxt : adj[x]){
if (nxt.first == prev) continue;
back[nxt.first] = nxt.second;
dfs(nxt.first, x);
if (m2[nxt.first].size()>m[x].size()) m[x].swap(m2[nxt.first]);
for (auto y : m2[nxt.first]){
if (m[x].count(K-y.first)){
best = min(best, m[x][K-y.first]+y.second);
}
}
for (auto y : m2[nxt.first]){
if (m[x].count(y.first)){
m[x][y.first] = min(m[x][y.first], y.second);
}else{
m[x][y.first] = y.second;
}
}
}
for (auto y : m[x]){
if ((y.first+back[x]) > K) continue;
m2[x][y.first+back[x]] = y.second+1;
}
m[x].clear();
};
dfs(0, -1);
if (best == (N+1)) best = -1;
return best;
}
