#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 2e5 + 2;
const int inf = 1e9 + 7;
const long long INF = (long long)1e18 + 7;
const int mod = 1e9 + 7;
void add(int &x, int y) {x += y; if (x >= mod) x -= mod;}
void sub(int &x, int y) {x -= y; if (x < 0) x += mod;}
int mul(int x, int y) {return 1LL * x * y % mod;}
int calPw(int x, int y) {
int ans = 1;
for(; y > 0; y >>= 1) {
if (y & 1) ans = 1LL * ans * x % mod;
x = 1LL * x * x % mod;
}
return ans;
}
// -----------------------------------------//
vector<ii> adj[N];
void read() {
}
map<int, int> mp[N];
int dfs(int u, int p, int K) {
int ans = inf;
// pair<int, int> middle = {inf, inf};
mp[u][0] = 0;
for(auto [v, c]: adj[u]) if (v != p) {
ans = min(ans, dfs(v, u, K));
for(auto x: mp[v]) {
if (x.fi == K) ans = min(ans, x.se);
else if (x.fi + c == K) ans = min(ans, x.se + 1);
if (K - x.fi - c >= 0 && mp[u].count(K - x.fi - c)) ans = min(ans, x.se + 1 + mp[u][K - x.fi - c]);
}
for(auto x: mp[v]) {
if (x.fi + c > K) continue;
// if (x.fi * 2 == K) {
// if (x.se < middle.fi) {
// middle.se = middle.fi;
// middle.fi = x.se;
// }
// else middle.se = min(middle.se, x.se);
// }
// cout << u << ' ' << v << ' ' << x.fi << ' ' << x.se << ' ' << c << endl;
if (mp[u].count(x.fi + c) == 0) mp[u][x.fi + c] = x.se + 1;
else mp[u][x.fi] = min(mp[u][x.fi + c], x.se + 1);
}
}
// if (middle.fi < inf && middle.se < inf) {
// ans = min(ans, middle.fi + middle.se + 2);
// }
return ans;
}
int best_path(int N, int K, int H[][2], int L[]) {
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]});
}
int ans = dfs(0, -1, K);
return ans == inf ? -1 : ans;
}
// int H[N][2], L[N];
// int n, K;
// void solve() {
// cin >> n >> K;
// for(int i = 0; i < n - 1; i++) cin >> H[i][0] >> H[i][1];
// for(int i = 0; i < n - 1; i++) cin >> L[i];
// cout << best_path(n, K, H, L);
// }
// signed main() {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// if (fopen(TASK".inp", "r")) {
// freopen(TASK".inp", "r", stdin);
// freopen(TASK".out", "w", stdout);
// }
// int test = 1;
// // cin >> test;
// while(test--) {
// read();
// solve();
// }
// return 0;
// }
// struct Point {
// int x, y;
// void read(){ scanf("%d %d", &x, &y); }
// Point operator +(const Point& b) const { return Point{x+b.x, y+b.y}; }
// Point operator -(const Point& b) const { return Point{x-b.x, y-b.y}; }
// ll operator *(const Point& b) const { return (ll) x * b.y - (ll) y * b.x; }
// bool operator <(const Point& b) const { return x == b.x ? y < b.y : x < b.x; }
// void operator +=(const Point& b) { x += b.x; y += b.y; }
// void operator -=(const Point &b) { x -= b.x; y -= b.y; }
// void operator *=(const int k) { x *= k; y *= k; }
// ll cross(const Point& b, const Point& c) const {
// return (b - *this) * (c - *this);
// }
// };
