#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int N =200100;
vector<pair<int,int>>adj[N];
int KIL[N],k,ans=1e9,sz[N],rt;
map<int,int> STF;
void dfs1(int n,int p,int tot){
sz[n]=1;
int mx=0;
for(auto[a,_]:adj[n]) if(!KIL[a]&&a-p)
dfs1(a,n,tot),sz[n]+=sz[a],mx=max(mx,sz[a]);
mx=max(mx,tot-sz[n]);
if(mx<=tot/2)
rt=n;
}
void dfs2(int n,int p,int d1,int d2){
if(d1>k)return;
if(STF.count(k-d1))
ans=min(ans,STF[k-d1]+d2);
for(auto [x,y]:adj[n])
if(x-p&&!KIL[x])
dfs2(x,n,d1+y,d2+1);
}
void dfs3(int n,int p,int d1,int d2){
if(d1>k)return;
if(STF.count(d1))
STF[d1]=min(STF[d1],d2);
else STF[d1]=d2;
for(auto [x,y]:adj[n])
if(x-p&&!KIL[x])
dfs3(x,n,d1+y,d2+1);
}
void decomp(int n,int tot){
dfs1(n,0,tot);
STF.clear();
STF[0]=0;
n=rt;
dfs1(n,0,tot);
KIL[n]=1;
for(auto[a,b]:adj[n])if(!KIL[a])
dfs2(a,n,b,1),dfs3(a,n,b,1);
for(auto [k,_]:adj[n])
if(!KIL[k])
decomp(k,sz[k]);
}
void AE(int a,int b,int k){
adj[a].push_back({b,k});
adj[b].push_back({a,k});
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i=0;i<N-1;i++)
AE(H[i][0],H[i][1],L[i]);
k=K;
decomp(1,N);
return (ans>N?-1:ans);
}
