#include "race.h"
#include <vector>
#include <utility>
#include <unordered_map>
#include <assert.h>
using namespace std;
long long ans=1000000000;
bool use[200005];
long long now=2e5;
pair < long long , long long > small[1000005];
vector < pair < long long , long long > > t;
vector < pair < pair < long long , long long > , long long > > Next[200005];
vector < long long > vis;
long long how[200005];
long long big[200005];
long long tt=0;
long long KK;
long long con=0;
void F(long long fa,long long here,long long dis,long long deg,long long KK)
{
con++;
//assert(con<=100000);
if(dis>KK) return ;
if(small[KK-dis].first==now) ans=min(ans,deg+small[KK-dis].second);
if(dis==KK) return ;
t.push_back(make_pair(dis,deg));
for(auto i:Next[here]) if(i.first.first!=fa&&!use[i.first.first]) F(here,i.first.first,dis+i.first.second,deg+1,KK);
}
void DFS2(long long fa,long long here)
{
big[here]=0;
how[here]=1;
tt++;
vis.push_back(here);
for(auto i:Next[here])
{
if(i.first.first!=fa&&!use[i.first.first])
{
DFS2(here,i.first.first);
big[here]=max(big[here],how[i.first.first]);
how[here]+=how[i.first.first];
}
}
}
void DFS(long long here,long long deg)
{
assert(deg<=40);
now++;
vector < long long > ttt;
vis.clear();
tt=0;
DFS2(-1,here);
long long center;
for(auto i:vis) if(max(big[i],tt-how[i])<=tt/2) center=i;
small[0]=make_pair(now,0);
for(auto &i:Next[center])
{
if(!use[i.first.first])
{
ttt.push_back(i.first.first);
t.clear();
F(center,i.first.first,i.first.second,1,KK);
for(auto j:t)
{
if(small[j.first].first!=now) small[j.first]=make_pair(now,j.second);
else small[j.first].second=min(small[j.first].second,j.second);
}
}
}
use[center]=1;
for(auto i:ttt) DFS(i,deg+1);
}
int best_path(int N, int KK, int H[][2], int L[])
{
//assert((N<=200000));
::KK=KK;
int i;
for(i=0;i<N-1;i++)
{
Next[H[i][0]].push_back(make_pair(make_pair((long long) H[i][1],(long long) L[i]),1));
Next[H[i][1]].push_back(make_pair(make_pair((long long) H[i][0],(long long) L[i]),1));
}
DFS(0,0);
if(ans==1000000000) ans=-1;
return (int) ans;
}
