#include <bits/stdc++.h>
#include "race.h"
// #include "grader.cpp"
using namespace std;
#define all(x) x.begin(), x.end()
int best_path(int N, int K, int H[][2], int L[]) {
map<long long, int> mp;
vector<vector<pair<int, int>>> adj(N);
for(int i = 0; i < N - 1; i++) {
int u = H[i][0], v = H[i][1];
adj[u].emplace_back(v, L[i]);
adj[v].emplace_back(u, L[i]);
}
int ans = N + 1;
auto dfs = [&](auto &&self, int v, int p, long long pref, int d) -> void {
mp[pref] = d;
if(pref - K >= 0 && mp.count(pref - K)) {
ans = min(ans, d - mp[pref - K]);
}
for(auto [to, w] : adj[v]) {
if(to == p) continue;
self(self, to, v, pref + w, d + 1);
}
mp.erase(pref);
};
dfs(dfs, 0, 0, 0, 0);
return (ans == N + 1 ? -1 : ans);
}
