#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 10000000;
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]].push_back({h[i][1], l[i]});
adj[h[i][1]].push_back({h[i][0], l[i]});
}
vector<int> weight(n), depth(n);
auto dfs1 = [&](int v, int p, ll w, int d, auto &&self) -> void {
depth[v] = d;
weight[v] = w;
for (pair<int, int> &i : adj[v]) {
if (i.first != p) self(i.first, v, w + i.second, d + 1, self);
}
};
dfs1(0, -1, 0, 0, dfs1);
vector<map<ll, int>> maps(n);
int ans = INT32_MAX;
auto dfs2 = [&](int v, int p, auto &&self) -> void {
maps[v][weight[v]] = depth[v] ;
for (pair<int, int> &i : adj[v]) {
if (i.first != p) {
self(i.first, v, self);
if (maps[i.first].size() > maps[v].size()) swap(maps[i.first], maps[v]);
for (map<ll, int>::iterator iter = maps[i.first].begin(); iter != maps[i.first].end(); iter++) {
map<ll, int>::iterator found = maps[v].find(k + 2 * weight[v] - iter->first);
if (found != maps[v].end()) {
ans = min(ans, iter->second + found->second - 2 * depth[v]);
// cout << "found " << iter->second << " " << found->second << endl;
}
}
for (map<ll, int>::iterator iter = maps[i.first].begin(); iter != maps[i.first].end(); iter++) {
map<ll, int>::iterator other = maps[v].find(iter->first);
// cout << v << " merging " << iter->first << "->" << iter->second << endl;
if (other != maps[v].end()) {
if (other->second > iter->second) other->second = iter->second;
} else maps[v][iter->first] = iter->second;
}
}
}
// cout << "vis " << v << endl;
// for (map<int, int>::iterator iter = maps[v].begin(); iter != maps[v].end(); iter++) {
// cout << "map " << v << " " << iter->first << "->" << iter->second << endl;
// }
};
dfs2(0, -1, dfs2);
return (ans == INT32_MAX) ? -1 : ans;
}
