#include "race.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
const int inf = 1e9 + 7;
int n, l, r;
ll k;
vector<pair<int,int>> adj[N];
int sub_sz[N];
bool deleted[N];
int get_sz(int x,int p = 0){
sub_sz[x] = 1;
for(pair<int,int> i : adj[x]){
if(i.first == p || deleted[i.first]) continue;
sub_sz[x] += get_sz(i.first,x);
}
return sub_sz[x];
}
int find_cen(int x, int sz, int p = 0){
for(pair<int,int> i : adj[x]){
if(i.first == p || deleted[i.first]) continue;
if(sub_sz[i.first] * 2 > sz) return find_cen(i.first,sz,x);
}
return x;
}
ll sum[N];
int ans = inf;
int mx = 0, H[N];
vector<pair<int,int>> v;
int Sz;
map<ll,int> mp;
//void upd(int idx, int val){
// for(;idx <= Sz ; idx += (idx & (-idx)))
// bit[idx] += val;
//}
//
//ll get(int idx){
// ll s = 0;
// for(;0 < idx ; idx -= (idx & (-idx)))
// s += bit[idx];
// return s;
//}
void get_dist(int x, int p, ll h, int cur){
// cout << x << '.' << h << '.' << mp[k - h] << '\n';
if(h > k) return;
if(h == k) {ans = min(ans,cur); return;}
else if(mp[k - h]) {
//cout << x << '.' << cur << '.' << mp[k - h] << '\n';
ans = min(ans,cur + mp[k - h]);
}
v.push_back({h,cur});
for(pair<int,int> i : adj[x]){
if(i.first == p || deleted[i.first]) continue;
get_dist(i.first,x,h + i.second,cur + 1);
}
return;
}
void build_centroid(int x){
Sz = get_sz(x);
x = find_cen(x,Sz);
mx = 0;
deleted[x] = 1;
mp.clear();
for(pair<int,int> i : adj[x]) {
if(deleted[i.first]) continue;
v.clear();
get_dist(i.first,x,i.second,1);
for(pair<int,int> j : v)
{
if(!mp[j.first]) mp[j.first] = j.second;
else mp[j.first] = min(mp[j.first],j.second);
}
}
for(pair<int,int> i : adj[x]){
if(deleted[i.first]) continue;
build_centroid(i.first);
}
}
int best_path(int N, int K, int H[][2],int L[]){
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
n = N;
k = K;
for(int i = 0,x,y,z; i < n - 1; ++i){
x = H[i][0];
y = H[i][1];
z = L[i];
x++;y++;
adj[x].push_back({y,z});
adj[y].push_back({x,z});
}
build_centroid(1);
return (ans == inf ? -1 : ans);
}
