#include <vector>
#include <set>
#include <map>
#include "race.h"
using namespace std;
int const MAXN=2e5+10;
vector<pair<int,int>>nei[MAXN]={};
int reqval=0,ans=1e9+10;
bool dead[MAXN]={};
int sz[MAXN]={};
int h[MAXN]={};
int find_centroid(int n,int m,int root,int f)
{
for (auto [i,we]:nei[n])
{
if (!dead[i]&&i!=m&&(sz[i]-f)*2>sz[root]-f)
return find_centroid(i,n,root,f);
}
return n;
}
map<long long,int>f;
vector<pair<long long,int>>cur;
void dfs1(int n,int m,long long val)
{
cur.push_back({val,h[n]});
if (val>reqval)
return;
if (f.find(reqval-val)!=f.end())
{
ans=min(ans,h[n]+f[reqval-val]);
}
for (auto [i,we]:nei[n])
{
if (!dead[i]&&i!=m)
{
h[i]=h[n]+1;
dfs1(i,n,val+we);
}
}
}
void sol(int n,int g=0)
{
if (sz[n]==1)
return;
n=find_centroid(n,-1,n,g);
dead[n]=1;
cur={};
f.clear();
f[0]=0;
for (auto [i,we]:nei[n])
{
if (!dead[i])
{
h[i]=1;
dfs1(i,-1,we);
for (auto [j,w]:cur)
{
if (f.find(j)==f.end())
f[j]=w;
f[j]=min(f[j],w);
}
cur={};
}
}
for (auto [i,we]:nei[n])
{
if (!dead[i])
{
if (sz[i]>sz[n])
sol(i,sz[n]);
else
sol(i,0);
}
}
}
int best_path(int n, int K, int H[][2], int L[])
{
reqval=K;
for (int i=0;i<n-1;i++)
{
int u=H[i][0],v=H[i][1];
nei[u].push_back({v,L[i]});
nei[v].push_back({u,L[i]});
}
sol(0);
ans=(ans==1e9+10?-1:ans);
return ans;
}
