#include <bits/stdc++.h>
#define DIM 200010
#define INF 2000000000
#include "race.h"
using namespace std;
int n,k,ans;
vector <pair<int,int> > L[DIM];
int viz[DIM],s[DIM],mrk[DIM],dp[DIM],level[DIM];
map <int,int> mp,mp2;
void dfs (int nod, int &cnt){
viz[nod] = s[nod] = 1;
cnt++;
for (auto it : L[nod]){
int vecin = it.first;
if (!viz[vecin] && !mrk[vecin]){
dfs (vecin,cnt);
s[nod] += s[vecin];
}}}
int get_centroid (int nod, int n){
viz[nod] = 1;
int maxim = 0, heavy_son = 0;
for (auto it : L[nod]){
int vecin = it.first;
if (mrk[vecin] || viz[vecin])
continue;
if (s[vecin] > maxim)
maxim = s[vecin], heavy_son = vecin;
}
if (maxim <= n/2 && n - s[nod] <= n/2)
return nod;
else return get_centroid(heavy_son,n);
}
int solve (int nod){
memset (viz,0,sizeof viz);
memset (s,0,sizeof s);
int n = 0;
dfs (nod,n);
memset (viz,0,sizeof viz);
int sol = get_centroid (nod,n);
mrk[sol] = 1;
return sol;
}
void dfs2 (int nod, int tata, int cost, int level){
//dp[nod] = dp[tata] + cost;
//level[nod] = 1 + level[tata];
if (!mp2[cost])
mp2[cost] = level;
else mp2[cost] = min (mp2[cost],level);
for (auto it : L[nod]){
int vecin = it.first;
if (!mrk[vecin] && vecin != tata)
dfs2 (vecin,nod,cost + it.second,level+1);
}
}
void decompose (int nod){
int centroid = solve (nod);
mp.clear();
for (auto it : L[centroid]){
int vecin = it.first;
if (mrk[vecin])
continue;
mp2.clear();
//dp[centroid] = 0;
dfs2 (vecin,centroid,it.second,1);
for (auto it2 : mp2){
int cost = it2.first;
if (mp[k-cost])
ans = min (ans,mp[k-cost] + it2.second);
if (cost == k)
ans = min (ans,it2.second);
}
for (auto it2 : mp2){
int cost = it2.first;
if (!mp[cost])
mp[cost] = it2.second;
else mp[cost] = min (mp[cost],it2.second);
}
}
for (auto it : L[centroid]){
int vecin = it.first;
if (!mrk[vecin])
decompose (vecin);
}
}
int best_path (int N, int K, int h[][2], int l[]){
n = N, k = K;
ans = n+1;
int i,j,x,y;
for (i=0;i<n-1;i++){
x = h[i][0]+1, y = h[i][1]+1;
L[x].push_back(make_pair(y,l[i]));
L[y].push_back(make_pair(x,l[i]));
}
decompose (1);
if (ans == n+1)
return -1;
return ans;
}
