#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5;
const int INF = 1e9;
int n, k;
int ans;
vector<pair<int,int>> adj[N];
unordered_map<int,int> best[N];
void dfs(int u, int p) {
best[u][0] = 0; // độ dài 0, 0 cạnh
for (auto [v, w] : adj[u]) {
if (v == p) continue;
dfs(v, u);
// small-to-large
if (best[v].size() > best[u].size())
best[u].swap(best[v]);
// tìm đường ghép đủ k
for (auto [len, cnt] : best[v]) {
int need = k - w - len;
if (need < 0) continue;
if (best[u].count(need)) {
ans = min(ans, best[u][need] + cnt + 1);
}
}
// gộp map
for (auto [len, cnt] : best[v]) {
int nl = len + w;
if (nl > k) continue;
if (!best[u].count(nl))
best[u][nl] = cnt + 1;
else
best[u][nl] = min(best[u][nl], cnt + 1);
}
best[v].clear();
}
}
/* ===== IOI INTERFACE ===== */
int best_path(int _n, int _k, int H[][2], int L[]) {
n = _n;
k = _k;
ans = INF;
for (int i = 0; i < n; i++) {
adj[i].clear();
best[i].clear();
}
for (int i = 0; i < n - 1; i++) {
int u = H[i][0];
int v = H[i][1];
int w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(0, -1);
return (ans == INF ? -1 : ans);
}
