#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
#define sz(v) (int)v.size()
const int MAX = 2*1e5+5;
vector< pair<int,int> > adj[MAX];
map< int,int > mp[MAX];
int add[MAX], ans, k;
void merge(int p, int f, int w){
if(sz(mp[p]) >= sz(mp[f])){
//Conta
for(auto it : mp[f]){
int d = it.fi + add[f] + w;
if(mp[p].find(k - d - add[p]) != mp[p].end()) ans = min(ans, mp[p][k-d-add[p]]+it.sc+1);
}
//Adiciona
for(auto it : mp[f]){
int id = it.fi + add[f] + w - add[p];
if( mp[p].find(id) == mp[p].end())mp[p][id] = it.sc+1;
else mp[p][id] = min(mp[p][id], it.sc+1);
}
mp[f].clear();
}else{
//Conta
for(auto it : mp[p]){
int d = it.fi + add[p] + w;
if(mp[f].find(k - d - add[f]) != mp[f].end()) ans = min(ans, mp[f][k-d-add[f]]+it.sc+1);
}
//Adiciona
add[f] += w;
for(auto it : mp[p]){
int id = it.fi + add[p] - add[f];
if( mp[f].find(id) == mp[f].end())mp[f][id] = it.sc+1;
else mp[f][id] = min(mp[f][id], it.sc+1);
}
mp[p].clear();
swap(mp[p],mp[f]);
swap(add[p],add[f]);
}
}
void dfs(int s, int p){
mp[s][0] = 0;
for(int i = 0; i < sz(adj[s]); i++){
int viz = adj[s][i].fi, w = adj[s][i].sc;
if(viz != p){
dfs(viz,s);
merge(s,viz,w);
}
}
}
int best_path(int n, int K, int h[][2], int l[]){
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]);
}
ans = n+1; k = K;
dfs(0,-1);
if(ans == n+1)ans = -1;
return ans;
}
