#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5;
vi w, to, uzy;
vi E[N];
int siz[N], dep[N];
ll d[N];
const int M=1e6+5;
int dist[M], dist2[M], opt[M];
int k, cent, ans=N;
void dfs_siz(int v, int p, int n){
siz[v]=1;
bool czy=1;
for(int i:E[v]){
if(to[i]!=p && !uzy[i]){
dfs_siz(to[i], v, n);
siz[v]+=siz[to[i]];
if(2*siz[to[i]]>n)czy=0;
}
}
if(2*(n-siz[v])>n)czy=0;
if(czy)cent=v;
//cout<<v<<" "<<siz[v]<<"\n";
}
int dfs_calc(int v, int p, int anc){
//cout<<v<<" "<<dep[v]<<" "<<d[v]<<"\n";
int res=1;
if(d[v]<=k && (dist[d[v]]==0 || dist[d[v]]>dep[v])){
if(opt[d[v]]!=anc)dist2[d[v]]=dist[d[v]];
dist[d[v]]=dep[v];
opt[d[v]]=anc;
}
if(k>=d[v] && dist[k-d[v]]!=0 && opt[k-d[v]]!=anc)ans=min(ans, dep[v]+dist[k-d[v]]);
if(k>=d[v] && dist2[k-d[v]]!=0)ans=min(ans, dep[v]+dist2[k-d[v]]);
if(k==d[v])ans=min(ans, dep[v]);
for(int i:E[v]){
if(to[i]!=p && !uzy[i]){
dep[to[i]]=dep[v]+1;
d[to[i]]=d[v]+w[i];
res+=dfs_calc(to[i], v, anc);
}
}
return res;
}
void dfs_clear(int v, int p){
if(d[v]<=k){
dist[d[v]]=dist2[d[v]]=opt[d[v]]=0;
}
for(int i:E[v]){
if(!uzy[i] && to[i]!=p){
dfs_clear(to[i], v);
}
}
}
void decomp(int v, int n){
//cout<<v<<" "<<n<<"a\n";
if(n==1)return;
cent=-1;
dfs_siz(v, 0, n);
assert(cent>0);
//cout<<cent<<"\n";
for(int i:E[cent]){
if(!uzy[i]){
dep[to[i]]=1;
d[to[i]]=w[i];
siz[to[i]]=dfs_calc(to[i], cent, to[i]);
}
}
int C=cent;
dfs_clear(C, 0);
for(int i:E[C]){
if(!uzy[i]){
uzy[i]=1;
uzy[i^1]=1;
decomp(to[i], siz[to[i]]);
}
}
}
int best_path(int n, int _k, int H[][2], int L[])
{
k=_k;
for(int i=0; i<n-1; i++){
H[i][0]++;
H[i][1]++;
E[H[i][0]].pb(to.size());
to.pb(H[i][1]);
E[H[i][1]].pb(to.size());
to.pb(H[i][0]);
w.pb(L[i]);
w.pb(L[i]);
}
uzy.resize(w.size());
decomp(1, n);
return ((ans==N) ? -1 : ans);
}
