#include <bits/stdc++.h>
#include "race.h"
using namespace std;
constexpr int nmx = 2e5+23;
int sz[nmx];
vector<pair<int, int>> adj[nmx];
bool proc[nmx];
set<pair<int, int>> vals;
int rq;
void dfs1(int u, int p){
sz[u] = 1;
for(auto &[v, w] : adj[u])if(!proc[v] && v!=p){
dfs1(v, u);
sz[u] += sz[v];
}
}
int centroid_dfs(int u, int p, int nd){
for(auto &[v, w] : adj[u])if(!proc[v] && v!=p && sz[v]>=nd) return centroid_dfs(v, u, nd);
return u;
}
int centroid(int u){
dfs1(u, 0);
int nd = sz[u]/2;
return centroid_dfs(u, nd, 0);
}
void dfs3(int u, int p, int depth, int path){
vals.insert(make_pair(path, depth));
for(auto &[v, w] : adj[u])if(!proc[v] && v!=p){
dfs3(v, u, depth+1, path+w);
}
}
int solve(int u){
int c = centroid(u);
proc[c] = 1;
dfs3(c, 0, 0, 0);
int res = -1;
while(!vals.empty()){
pair<int, int> top = *vals.begin();
vals.erase(top);
int nd = rq - top.first;
if(top.first>rq) break;
auto it = lower_bound(vals.begin(), vals.end(), make_pair(nd, -1));
if(it==vals.end()) continue;
if((*it).first==rq){
int cur = 1+(*it).second + top.second;
res = res==-1?cur:min(res, cur);
}
}
vals.clear();
for(auto &[v, w] : adj[c]) if(!proc[v]){
int ch = solve(v);
if(ch!=-1) res = res==-1?ch:min(res, ch);
}
return res;
}
int best_path(int N, int K, int H[][2], int L[])
{
int n = N;
rq = K;
int res = -1;
for(int i = 0; i <= n; ++i) proc[i] = 0;
for(int i = 0; i < n-1; ++i){
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
res = solve(1);
return res;
}
