#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define P push
#define I insert
typedef long long ll;
const ll INF=10000000000000;
const int maxn=200000;
ll n,k;
int ans=INT32_MAX;
vector<pair<ll,ll> > v[maxn];
int parent[maxn];
int subsiz[maxn];
int len[maxn];
ll dist[maxn];
int dfs(int x,set<int> s){
subsiz[x]=1;
for(int i=0;i<v[x].size();i++){
int y=v[x][i].F;
if(parent[x]==y || s.count(y))continue;
parent[y]=x;
dist[y]=dist[x]+v[x][i].S;
len[y]=len[x]+1;
subsiz[x]+=dfs(y,s);
}
return subsiz[x];
}
int find_centroid(int x,int parsub,set<int> s,int gsiz){
pair<ll,int> p={-1,-1};
for(int i=0;i<v[x].size();i++){
int y=v[x][i].F;
if(parent[x]==y || s.count(y))continue;
if(p.F<subsiz[y])p={subsiz[y],y};
}
if(p.F<=gsiz/2)return x;
else return find_centroid(p.S,subsiz[x]+parsub-p.F,s,gsiz);
}
map<ll,int> func(int x,int prcen,set<int> s){
parent[x]=prcen;len[x]=1;dist[x]=0;
dfs(x,s);
int cen=find_centroid(x,0,s,subsiz[x]);
ll cenpar=parent[cen],cenparlen;
map<ll,int> mp,mp1;mp[0]=1;
s.I(cen);
ll y,disty;
for(int i=0;i<v[cen].size();i++){
y=v[cen][i].F;
disty=v[cen][i].S;
if(y==cenpar){
cenparlen=disty;
continue;
}
if(s.count(y))continue;
mp1=func(y,cen,s);
for(auto itr=mp1.begin();itr!=mp1.end();itr++){
pair<int,int> p=*itr;
if(mp.count(k-p.F-disty)==0)continue;
ans=min(ans,mp[k-p.F-disty]+p.S);
}
for(auto itr=mp1.begin();itr!=mp1.end();itr++){
pair<int,int> p=*itr;
if(mp.count(p.F+disty)==0)mp[p.F+disty]=p.S+1;
else mp[p.F+disty]=min(mp[p.F+disty],p.S+1);
}
}
map<ll,int> nmap;
if(x==cen){
for(auto itr=mp.begin();itr!=mp.end();itr++){
pair<ll,int> p=*itr;
if(nmap.count(p.F+dist[cen])==0)nmap[p.F+dist[cen]]=p.S;
else nmap[p.F+dist[cen]]=min(nmap[p.F+dist[cen]],p.S);
}
nmap[0]=1;
return nmap;
}
y=cenpar;disty=cenparlen;
mp1=func(y,cen,s);
for(auto itr=mp1.begin();itr!=mp1.end();itr++){
pair<int,int> p=*itr;
if(mp.count(k-p.F-disty)==0)continue;
ans=min(ans,mp[k-p.F-disty]+p.S);
}
queue<int> q;q.P(x);
parent[x]=prcen;len[x]=1;dist[x]=0;
while(!q.empty()){
int c=q.front();q.pop();
if(c==cen)continue;
for(int i=0;i<v[c].size();i++){
y=v[c][i].F;
disty=v[c][i].S;
if(parent[c]==y || s.count(y))continue;
parent[y]=c;
len[y]=len[c]+1;
dist[y]=dist[c]+disty;
if(nmap.count(dist[y])==0)nmap[dist[y]]=len[y];
else nmap[dist[y]]=min(nmap[dist[y]],len[y]);
q.P(y);
}
}
for(auto itr=mp.begin();itr!=mp.end();itr++){
pair<ll,int> p=*itr;
if(nmap.count(p.F+dist[cen])==0)nmap[p.F+dist[cen]]=p.S+len[cen]-1;
else nmap[p.F+dist[cen]]=min(nmap[p.F+dist[cen]],p.S+len[cen]-1);
}
nmap[0]=1;
return nmap;
}
int best_path(int N, int K, int h[][2], int l[]){
n=(ll)N;k=(ll)K;
for(int i=0;i<n-1;i++){
v[h[i][0]].PB(MP(h[i][1],(ll)l[i]));
v[h[i][1]].PB(MP(h[i][0],(ll)l[i]));
}
set<int> s;
func(0,0,s);
if(ans>n)return -1;
return ans-1;
}
