//#include "race.h"
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
vector<vector<pair<int,int> > > g(MAXN);
vector<vector<pair<int,int> > > ceng(MAXN);
vector<int> subsz(MAXN);
bitset<MAXN> vis;
vector<map<int,int> > sol(MAXN);
int cenroot=-1;
int ans=INT_MAX;
void solve(int u,const int& K)
{
vis.flip(u);
map<int,deque<pair<int,int> > > m;
for(auto ch:g[u])
{
if(!vis.test(ch.first))
{
solve(ch.first,K);
for(auto p:sol[ch.first])
{
int len=p.first+ch.second,nm=p.second+1;
if(len<=K)
{
if(sol[u].find(len)==sol[u].end())
{
sol[u][len]=INT_MAX;
}
sol[u][len]=min(sol[u][len],nm);
if(m.find(len)==m.end())
{
m[len].emplace_back(nm,ch.first);
}else if(m[len].size()==1)
{
if(nm<=m[len][0].first)
{
m[len].emplace_front(nm,ch.first);
}else
{
m[len].emplace_back(nm,ch.first);
}
}else
{
if(nm<=m[len][0].first)
{
m[len].pop_back();
m[len].emplace_front(nm,ch.first);
}else if(nm<=m[len][1].first)
{
m[len].pop_back();
m[len].emplace_back(nm,ch.first);
}
}
}
}
}
}
if(sol[u].find(K)!=sol[u].end()) ans=min(ans,sol[u][K]);
for(auto p:m)
{
int len=p.first,nm=p.second[0].first,ch=p.second[0].second;
if(m.find(K-len)!=m.end())
{
if(m[K-len][0].second!=ch)
{
ans=min(ans,nm+m[K-len][0].first);
}else
{
if(m[K-len].size()==2)
{
ans=min(ans,nm+m[K-len][1].first);
}
}
}
}
sol[u][0]=0;
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i=0;i<N-1;i++)
{
int u=H[i][0],v=H[i][1];
g[u].push_back({v,L[i]});
g[v].push_back({u,L[i]});
}
/*findsubsz(1);
vis.clear();
makeceng(1);
vis.clear();
solve(cenroot);*/
solve(0,K);
if(ans==INT_MAX) return -1;
else return ans;
}
