#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int best_path(int N, int K, int H[][2], int L[]) {
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < N - 1; i++) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
int ans = N;
vector<set<pair<int64_t, int>>> s(N);
auto dfs = [&](auto dfs, int x, int p, int64_t dis, int dep) -> void {
s[x].emplace(dis, dep);
for (auto [y, z] : adj[x]) {
if (y == p) {
continue;
}
dfs(dfs, y, x, dis + z, dep + 1);
if (s[x].size() < s[y].size()) {
swap(s[x], s[y]);
}
for (auto [len, cnt] : s[y]) {
int64_t q = K - len + 2 * dis;
auto it = s[x].lower_bound({q, 0});
if (it != s[x].end() && (*it).first == q) {
ans = min(ans, (*it).second + cnt - 2 * dep);
}
}
s[x].insert(s[y].begin(), s[y].end());
}
};
dfs(dfs, 0, -1, 0, 0);
if (ans == N) {
ans = -1;
}
return ans;
}
