#include "race.h"
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[201000], Len[201000];
int n, LL, Res, D[201000], Dep[201000], C[201000], Q[201000], par[201000];
bool chk[201000];
int BFS(int a){
int h = 0, t = 0, x, i;
Q[++t] = a;
par[t] = D[t] = Dep[t] = 0, C[t] = 1;
while (h < t){
x = Q[++h];
for (i = 0; i < E[x].size(); i++){
if (!chk[E[x][i]] && Q[par[h]] != E[x][i]){
Q[++t] = E[x][i];
par[t] = h, D[t] = D[h] + Len[x][i], Dep[t] = Dep[h] + 1, C[t] = 1;
}
}
}
for (i = t; i>1; i--)C[par[i]] += C[i];
return t;
}
int get_mid(int SZ){
int i, M = SZ + 1, x;
for (i = 1; i <= SZ; i++){
if (M > C[i] && C[i] > SZ / 2)M = C[i], x = Q[i];
}
return x;
}
int w[1010000], Li[201000];
void Do(int a){
int SZ = BFS(a);
if (SZ == 1)return;
int m = get_mid(SZ), i, j, cnt = 0;
chk[m] = true;
for (i = 0; i < E[m].size(); i++){
if (!chk[E[m][i]])Do(E[m][i]);
}
for (i = 0; i < E[m].size(); i++){
if (chk[E[m][i]])continue;
SZ = BFS(E[m][i]);
for (j = 1; j <= SZ; j++){
D[j]+= Len[m][i], Dep[j]++;
if (D[j]>LL)continue;
if (D[j] == LL)Res = min(Res, Dep[j]);
else if (w[LL - D[j]])Res = min(Res, Dep[j] + w[LL - D[j]]);
}
for (j = 1; j <= SZ; j++){
if (D[j] <= LL && (w[D[j]] == 0 || w[D[j]] > Dep[j]))w[D[j]] = Dep[j], Li[cnt++] = D[j];
}
}
chk[m] = false;
for (i = 0; i < cnt; i++)w[Li[i]] = 0;
}
int best_path(int N, int K, int H[][2], int L[])
{
int i;
n = N, LL = K;
for (i = 0; i < n - 1; i++){
E[H[i][0]].push_back(H[i][1]);
E[H[i][1]].push_back(H[i][0]);
Len[H[i][0]].push_back(L[i]);
Len[H[i][1]].push_back(L[i]);
}
Res = n + 1;
Do(0);
return Res == n + 1 ? -1 : Res;
}
