#include <bits/stdc++.h>
using namespace std;
#define taskname "IOI11_race"
#define forinc(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordec(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define foreach(i, x) for (auto &i : x)
#define ms(x, n) memset(x, n, sizeof(x))
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define fi first
#define se second
#define pb push_back
#define pf push_front
template<typename TH>
void _dbg(const char* sdbg, TH h)
{
cerr << sdbg << " = " << h << "\n";
}
template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
while (*sdbg != ',') cerr << *sdbg++;
cerr << " = " << h << ",";
_dbg(sdbg + 1, t...);
}
#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";
const int N=2e5+5,INF=1e9;
int n,k,l[N];
vector<pair<int,int>> g[N];
int nEdge[1002][1002],root;
int64_t dist[1002][1002];
void DFS(int u,int fa,int d,int64_t sumW)
{
nEdge[root][u]=d;
dist[root][u]=sumW;
foreach(p,g[u])
{
if(p.fi!=fa)
{
DFS(p.fi,u,d+1,sumW+l[p.se]);
}
}
}
void Calc(int u)
{
root=u;
DFS(u,-1,0,0);
}
int Sub2()
{
forinc(i,0,n-1)
{
Calc(i);
}
int ans=INF;
forinc(u,0,n-1)
{
forinc(v,u+1,n-1)
{
if(dist[u][v]==k)
{
ans=min(ans,nEdge[u][v]);
}
}
}
return (ans==INF?-1:ans);
}
int up[N][102],down1[N][102],down2[N][102];
void CalcDown(int u,int fa)
{
down1[u][0]=0;
foreach(p,g[u])
{
if(p.fi!=fa)
{
CalcDown(p.fi,u);
forinc(i,0,k)
{
if(i-l[p.se]>=0&&down1[p.fi][i-l[p.se]]!=INF)
{
int tmp=down1[p.fi][i-l[p.se]]+1;
if(tmp<=down1[u][i])
{
down2[u][i]=down1[u][i];
down1[u][i]=tmp;
}
else
{
down2[u][i]=min(down2[u][i],tmp);
}
}
}
}
}
}
void CalcUp(int u,int fa,int preW)
{
up[u][0]=0;
if(~fa)
{
forinc(i,0,k)
{
if(i-preW>=0)
{
if(up[fa][i-preW]!=INF)
{
up[u][i]=min(up[u][i],up[fa][i-preW]+1);
}
if(down1[fa][i-preW]!=INF)
{
if(i-2*preW>=0&&down1[fa][i-preW]==down1[u][i-2*preW]+1)
{
if(down2[fa][i-preW]!=INF)
{
up[u][i]=min(up[u][i],down2[fa][i-preW]+1);
}
}
else
{
up[u][i]=min(up[u][i],down1[fa][i-preW]+1);
}
}
}
}
}
foreach(p,g[u])
{
if(p.fi!=fa)
{
CalcUp(p.fi,u,l[p.se]);
}
}
}
int Sub3()
{
forinc(i,0,n-1)
{
forinc(j,0,k)
{
up[i][j]=down1[i][j]=down2[i][j]=INF;
}
}
CalcDown(0,-1);
CalcUp(0,-1,0);
int ans=INF;
forinc(i,0,n-1)
{
ans=min(ans,min(up[i][k],down1[i][k]));
}
return (ans==INF?-1:ans);
}
int Solve()
{
return Sub3();
}
int best_path(int N,int K,int H[][2],int L[])
{
n=N;
k=K;
forinc(i,0,n-2)
{
g[H[i][0]].pb({H[i][1],i});
g[H[i][1]].pb({H[i][0],i});
}
forinc(i,0,n-2)
{
l[i]=L[i];
}
return Solve();
}
//int main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// #ifndef ONLINE_JUDGE
// freopen(taskname".INP","r",stdin);
// #endif // ONLINE_JUDGE
// cin>>n>>k;
// forinc(i,0,n-2)
// {
// int u,v;
// cin>>u>>v;
// g[u].pb({v,i});
// g[v].pb({u,i});
// }
// forinc(i,0,n-2)
// {
// cin>>l[i];
// }
// cout<<Solve();
// return 0;
//}
