#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
typedef pair <int, ll> edge;
#define x first
#define y second
const int N = 200010;
const int INF = 1e9 + 10;
vector <edge> g[N];
int n, k, ans = INF;
void dfs (int u, int from, map <ll, int> &f, ll &key_f, int &val_f) {
f[0] = 0;
key_f = val_f = 0;
for (edge e : g[u]) {
int v = e.x;
ll w = e.y;
if (v == from) continue;
map <ll, int> t;
ll key_t;
int val_t;
dfs(v, u, t, key_t, val_t);
key_t += w, ++val_t;
if (t.size() > f.size()) {
f.swap(t);
swap(key_f, key_t);
swap(val_f, val_t);
}
for (auto it : t) {
ll more = k - it.x - key_t - key_f;
if (f.find(more) != f.end()) {
ans = min(ans, it.y + f[more] + val_t + val_f);
}
}
key_t -= key_f, val_t -= val_f;
for (auto it : t) {
if (f.find(it.x + key_t) == f.end()) f[it.x + key_t] = INF;
f[it.x + key_t] = min(f[it.x + key_t], it.y + val_t);
}
}
// cout << u << " ----> \n";
// for (auto it : f) {
// cout << it.x << " " << it.y << endl;
// }
}
int best_path (int N, int K, int H[][2], int L[]) {
n = N, k = K;
for (int i = 0; i < n - 1; ++i) {
g[H[i][0]].emplace_back(H[i][1], L[i]);
g[H[i][1]].emplace_back(H[i][0], L[i]);
}
map <ll, int> f;
ll key;
int val;
dfs(0, 0, f, key, val);
if (ans >= INF / 2) ans = -1;
return ans;
}
