#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];
map<ll, int> dist[N], dist2[N], opt[N];
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";
}
void dfs_calc(int v, int p, int anc){
//cout<<v<<" "<<dep[v]<<" "<<d[v]<<"\n";
if(dist[cent][d[v]]==0 || dist[cent][d[v]]>dep[v]){
if(opt[cent][d[v]]!=anc)dist2[cent][d[v]]=dist[cent][d[v]];
dist[cent][d[v]]=dep[v];
opt[cent][d[v]]=anc;
}
if(dist[cent][k-d[v]]!=0 && opt[cent][k-d[v]]!=anc)ans=min(ans, dep[v]+dist[cent][k-d[v]]);
if(dist2[cent][k-d[v]]!=0)ans=min(ans, dep[v]+dist2[cent][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];
dfs_calc(to[i], v, anc);
}
}
}
void decomp(int v, int n){
//cout<<v<<"a\n";
if(siz[v]==1)return;
dfs_siz(v, 0, n);
//cout<<cent<<"\n";
for(int i:E[cent]){
if(!uzy[i]){
dep[to[i]]=1;
d[to[i]]=w[i];
dfs_calc(to[i], cent, to[i]);
}
}
int C=cent;
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);
}
