#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
int to,cost;
};
vector<edge>E[200000];
int N,K,res,c;
int tree_id[200000],subtree_size[200000],dist[200000];
ll cost[200000];
int get_centroid(int x,int from,int size,int id){
subtree_size[x]=0;
if(tree_id[x]!=id)return -1;
subtree_size[x]=1;
for(edge e:E[x]){
if(e.to==from)continue;
int p=get_centroid(e.to,x,size,id);
if(p!=-1)return p;
subtree_size[x]+=subtree_size[e.to];
}
int t=x;
if(size-subtree_size[x]<=size/2){
for(edge e:E[x]){
if(subtree_size[e.to]>size/2)t=-1;
}
}
else t=-1;
return t;
}
void dfs(int x,int from,int id){
if(tree_id[x]!=id)return;
for(edge e:E[x]){
if(e.to==from)continue;
dist[e.to]=dist[x]+1;
cost[e.to]=cost[x]+e.cost;
dfs(e.to,x,id);
}
}
void dfs2(vector<int>&v,int x,int from,int id){
if(tree_id[x]!=id)return;
v.push_back(x);
for(edge e:E[x]){
if(e.to==from)continue;
dfs2(v,e.to,x,id);
}
}
void F(vector<int>&v,int id){
if(v.empty())return;
c++;
for(int i:v){
tree_id[i]=id;
}
int cent=get_centroid(v.front(),v.front(),v.size(),id);
dist[cent]=cost[cent]=0;
dfs(cent,cent,id);
vector<vector<int>>vv;
for(edge e:E[cent]){
vv.push_back({});
dfs2(vv.back(),e.to,cent,id);
}
set<pair<pair<ll,int>,int>>st;
for(int i:v){
st.insert({{cost[i],dist[i]},i});
}
auto it=st.lower_bound({{K,-1},-1});
if(it!=st.end()&&it->first.first==K){
res=min(res,it->first.second);
}
for(vector<int>&V:vv){
for(int i:V){
st.erase({{cost[i],dist[i]},i});
}
for(int i:V){
auto it=st.lower_bound({{K-cost[i],-1},-1});
if(it!=st.end()&&it->first.first==K-cost[i]){
res=min(res,it->first.second+dist[i]);
}
}
for(int i:V){
st.insert({{cost[i],dist[i]},i});
}
}
for(vector<int>&V:vv){
F(V,c);
}
}
int best_path(int n, int k, int H[][2], int L[]){
N=n;
K=k;
res=0xE869120;
for(int i=0;i<N-1;i++){
E[H[i][0]].push_back({H[i][1],L[i]});
E[H[i][1]].push_back({H[i][0],L[i]});
}
vector<int>v;
for(int i=0;i<N;i++){
v.push_back(i);
}
F(v,c);
if(res==0xE869120)res=-1;
return res;
}
