#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int best_path(int N, int K, int H[][2], int L[]){
map<ll,int> m[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]});
}
ll dist = 0;
int best = N+1;
int depth = 0;
function<void(int,int)> dfs = [&](int x, int prev){
m[x][dist] = depth;
depth++;
for (auto nxt : adj[x]){
if (nxt.first == prev) continue;
dist += nxt.second;
dfs(nxt.first, x);
dist -= nxt.second;
if (m[x].size()<m[nxt.first].size()) m[x].swap(m[nxt.first]);
for (auto y : m[nxt.first]){
if (!m[x].count(K+2*dist-y.first)) continue;
best = min(best, m[x][K+2*dist-y.first]+y.second-2*depth+2);
}
for (auto y : m[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;
}
}
}
depth--;
};
dfs(0, -1);
if (best == (N+1)) best = -1;
return best;
}
