#include <bits/stdc++.h>
#include "race.h"
using ll =long long;
//#define int ll
ll LINF=1000000000000000000;
int INF=1e9;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>
//#define int ll
using namespace std;
vector<vector<pi>>g;
int k;
int minimum=INF;
vi vinf={INF,-1};
void add(map<int,vii>&v,map<int,vii>&cv,int node,int dist){
for(auto itr=cv.begin();itr!=cv.end() && itr->first+dist<k+1;itr++){
auto itr2=v.find(itr->first+dist);
if(itr2==v.end()){
auto vect=vii(2,vi({INF,-1}));
v[itr->first+dist]=vect;
itr2=v.find(itr->first+dist);
}
if(itr2->second[0][0]>itr->second[1][0]+1){
itr2->second[0][0]=itr->second[1][0]+1;
itr2->second[0][1]=node;
if(itr2->second[0][0]<itr2->second[1][0]){
swap(itr2->second[0][0],itr2->second[1][0]);
swap(itr2->second[0][1],itr2->second[1][1]);
}
}
}
}
map<int,vii> dfs(int node,int parent){
map<int,vii>m;
m.insert(make_pair(0,vii({vi({INF,-1}),vi({0,node})})));
for(pi child:g[node]){
if(child.first==parent)continue;
auto cv=dfs(child.first,node);
add(m,cv,child.first,child.second);
cv.clear();
}
for(auto itr=m.begin();itr!=m.end();itr++){
auto itr2=m.find(k-itr->first);
if(itr2!=m.end()){
if(itr2->second[1][1]!=itr->second[1][1]){
minimum=min(minimum,itr2->second[1][0]+itr->second[1][0]);
}
else {
minimum=min(minimum,itr2->second[0][0]+itr->second[1][0]);
}
}
}
return m;
}
int best_path(int N, int K, int H[][2], int L[])
{
g.resize(N);
k=K;
for(int i=0;i<N-1;i++){
g[H[i][0]].push_back(make_pair(H[i][1],L[i]));
g[H[i][1]].push_back(make_pair(H[i][0],L[i]));
}
dfs(0,-1);
if(minimum==1e9)return -1;
return minimum;
}
