#include "race.h"
#include <bits/stdc++.h>
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>
using namespace std;
struct Path {
ll i, w;
};
ll n, k;
ll ans = INF64;
vector<Path> adj [(ll) 2e5+1];
bool wasCentroid [(ll) 2e5+1];
ll subtree [(ll) 2e5+1];
void find_subtree(ll& i, ll& from) {
subtree[i] = 1;
for (Path& k : adj[i]) {
if (k.i != from && !wasCentroid[k.i]) {
find_subtree(k.i, i);
subtree[i] += subtree[k.i];
}
}
}
ll find_centroid(ll& i, ll& from, ll& N) {
for (Path& k : adj[i]) {
if (k.i != from && !wasCentroid[k.i] && subtree[k.i] > n/2)
return find_centroid(k.i, i, N);
}
return i;
}
ll freq[(ll)1e6+1];
void find_ans(ll& i, ll& from, vector<Path>& cur, ll cnt, ll w) {
if (w > k)
return;
if (w == k) {
ans = min(ans, cnt);
return;
}
if (freq[k-w] != INF64) {
ans = min(ans, freq[k-w]+cnt);
}
cur.push_back({cnt, w});
for (Path& k : adj[i]) {
if (!wasCentroid[k.i] && k.i != from)
find_ans(k.i, i, cur, cnt+1, w+k.w);
}
}
void clean (ll& i, ll& from, ll w) {
if (w > k)
return;
freq[w] = INF64;
for (Path& k : adj[i]) {
if (k.i != from && !wasCentroid[k.i])
clean(k.i, i, w+k.w);
}
}
void process(ll& i) {
for (Path& k : adj[i]) {
if (!wasCentroid[k.i]) {
vector<Path> cur;
find_ans(k.i, i, cur, 1, k.w);
for (Path& it : cur) {
freq[it.w] = min(freq[it.w], it.i);
}
}
}
clean(i, i, 0);
}
void answer(ll i) {
find_subtree(i, i);
ll N = subtree[i];
i = find_centroid(i, i, N);
process(i);
wasCentroid[i] = 1;
for (Path& k : adj[i]) {
if (!wasCentroid[k.i])
answer(k.i);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N; k = K;
fill(all(wasCentroid), 0);
fill(all(freq), INF64);
range(i, 0, n-1) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
answer(0);
return (ans == INF64 ? -1 : ans);
}
