#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> g;
vector<int> sz;
vector<bool> vis;
int fi = 0;
void dfs(int k, int p){
sz[k] = 1;
for(int i = 0; i < g[k].size(); i++){
if(g[k][i].first == p || vis[g[k][i].first]) continue;
dfs(g[k][i].first, k);
sz[k] += sz[g[k][i].first];
}
}
int mn = 1e9;
int find_cen(int k, int s, int p){
for(int i = 0; i < g[k].size(); i++){
if(vis[g[k][i].first] || g[k][i].first == p) continue;
if(sz[g[k][i].first] > s/2){
return find_cen(g[k][i].first, s, k);
}
}
return k;
}
int co = 0;
void fsz(int k, int p){
co++;
for(int i = 0; i < g[k].size(); i++){
if(vis[g[k][i].first] || g[k][i].first == p) continue;
fsz(g[k][i].first, k);
}
}
vector<pair<long long, int>> pen;
void dfs1(int k, int p, int cur, int co){
pen.push_back({cur, co+1});
for(int y = 0; y < g[k].size(); y++){
if(vis[g[k][y].first] || g[k][y].first == p) continue;
dfs1(g[k][y].first, k, cur+g[k][y].second, co+1);
}
}
void solve(int k){
if(vis[k]) return;
//find cen
co = 0;
fsz(k, 0);
dfs(k, 0);
int cen = find_cen(k, co, 0);
// cout << cen << "\n";
vis[cen] = true;
map<long long, int> mp;
for(int i = 0; i < g[cen].size(); i++){
if(vis[g[cen][i].first]) continue;
pen.clear();
dfs1(g[cen][i].first, 0, g[cen][i].second, 0);
for(auto y : pen){
// cout << y.first << " J\n";
long long cur = fi-y.first;
if(cur == 0){
mn = min(mn, y.second);
}
if(mp[cur] == 0) continue;
mn = min(mn, mp[cur]+y.second);
}
for(auto y : pen){
if(mp[y.first] == 0){
mp[y.first] = y.second;
// cout << mp[1] << " K\n";
}else{
mp[y.first] = min(mp[y.first], y.second);
}
}
}
for(int i = 0; i < g[cen].size(); i++){
if(vis[g[cen][i].first]) continue;
solve(g[cen][i].first);
}
solve(k);
}
int best_path(int N, int K, int H[][2], int L[])
{
fi = K;
vis.resize(N+1);
g.resize(N+1);
sz.resize(N+1);
for(int i = 0; i < N-1; i++){
g[H[i][0]+1].push_back({H[i][1]+1, L[i]});
g[H[i][1]+1].push_back({H[i][0]+1, L[i]});
}
dfs(1, 0);
solve(1);
if(mn == 1e9){
mn = -1;
}
return mn;
}
