#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
#define el '\n'
const int N = 2e6 + 24;
const ll INF = 1e18;
ll n, k;
vector<pair<ll, ll>> g[N];
ll h[N], d[N]; map<ll, ll> mp[N];
ll res;
void dfs(int u, int pre, ll cnt, ll W) {
if (W == k) res = min(res, cnt);
for (auto [v, w]: g[u]) {
if (v == pre) continue;
dfs(v, u, cnt + 1, W + w);
}
}
// void dfs(int u, int pre) {
// for (auto [v, w]: g[u]) {
// if (v == pre) continue;
// d[v] = d[u] + w;
// h[v] = h[u] + 1;
// dfs(v, u);
// }
// // cout << u << ':' << d[u] << ' ' << h[u] << el;
// }
// void stl_dfs(int u, int pre) {
// mp[u][d[u]] = h[u];
// for (auto [v, w]: g[u]) {
// if (v == pre) continue;
// stl_dfs(v, u);
// // if (mp[u].size() < mp[v].size()) {
// // swap(mp[u], mp[v]);
// // }
// for (auto [dv, hv]: mp[v]) {
// if (mp[u].count(dv)) {
// mp[u][dv] = min(mp[u][dv], hv);
// }
// else mp[u][dv] = hv;
// }
// }
// // cout << u << "\n";
// // for (auto [dv, hv]: mp[u]) {
// // cout << dv << '/' << hv << el;
// // }
// if (mp[u].count(k + d[u])) {
// // cout << "." << mp[u][k + d[u]] - h[u] << el;
// res = min(res, mp[u][k + d[u]] - h[u]);
// }
// }
int best_path(int N, int K, int H[][2], int L[]) {
n = N; k = K;
for (int i = 1; i <= n - 1; i++) {
int u = H[i - 1][0], v = H[i - 1][1];
ll w = L[i - 1];
u++, v++;
// cout << u << ' ' << v << ' ' << w << el;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
res = INF;
for (int i = 1; i <= n; i++) {
dfs(i, 0, 0, 0);
}
return (res > n ? -1 : res);
}
