#include "race.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int NMAX = 2e5 + 5;
constexpr int INF = 1e9;
typedef long long LL;
typedef pair <int, LL> PIL;
int Dist;
int ans;
map <LL, int> mp[NMAX];
vector <PIL > G[NMAX];
void Dfs (int Node, int dad = -1) {
mp[Node][0] = 1;
for (auto it : G[Node]) {
int to = it.first;
LL cost = it.second;
if (to == dad) continue;
Dfs(to, Node);
if (mp[to].size() > mp[Node].size())
swap(mp[to], mp[Node]);
for (auto drum : mp[to]) {
LL remain = Dist - drum.first - cost;
if (mp[Node][remain] != 0)
ans = min(ans, mp[Node][remain] + drum.second);
}
for (auto drum : mp[to]) {
LL new_drum = drum.first + cost;
if (new_drum > Dist) continue;
if (new_drum == Dist) {
ans = min(ans, drum.second + 1);
continue;
}
if (mp[Node][new_drum] == 0)
mp[Node][new_drum] = drum.second + 1;
else mp[Node][new_drum] = min(mp[Node][new_drum], drum.second + 1);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ans = INF;
Dist = K;
for (int i = 0; i < N-1; ++ i ) {
G[H[i][0]].push_back({H[i][1], L[i]});
G[H[i][1]].push_back({H[i][0], L[i]});
}
Dfs(0);
if (ans == INF) return -1;
else return ans-1;
}
