#include "race.h"
#include <vector>
#include <map>
#include <functional>
using namespace std;
typedef pair<int,int> pi;
#define pb push_back
const int inf = 1e9;
int best_path(int N, int K, int H[][2], int L[]) {
vector<pi> adj[N];
for (int i = 0; i < N-1; i++) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
vector<long long> path(N);
vector<int> dep(N);
vector<vector<pi>> pres(N);
int ans = inf;
function<void(int,int,map<long long,int>&)> dfs = [&](int u, int p, map<long long,int>& mp) {
mp[path[u]] = dep[u];
pres[u].emplace_back((int)path[u], dep[u]);
for (auto [v, w] : adj[u]) {
if (v == p) continue;
path[v] = path[u] + w;
dep[v] = dep[u] + 1;
map<long long,int> curr;
dfs(v, u, curr);
if (pres[u].size() < pres[v].size()) {
swap(pres[u], pres[v]);
swap(mp, curr);
}
for (auto [x, d] : pres[v]) {
if (mp.find(2*path[u]+K-x) == mp.end()) continue;
ans = min(ans, mp[2*path[u]+K-x] + d - 2*dep[u]);
}
for (auto [x, d] : pres[v]) {
pres[u].emplace_back(x, d);
if (mp.find(x) != mp.end()) mp[x] = min(mp[x], d);
else mp[x] = d;
}
}
};
map<long long,int> tmp;
dfs(0, -1, tmp);
return ans == inf ? -1 : ans;
}
