#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
set < int > G[N];
int sz[N];
//int a[N * 10];
map < int , int > a;
int H[N][2] , L[N];
int K;
void getsize(int node , int par)
{
sz[node] = 1;
for(auto e : G[node])
{
int to = node ^ H[e][0] ^ H[e][1];
int c = L[e];
if(to != par)
{
getsize(to , node);
sz[node] += sz[to];
}
}
}
int find(int node , int par , int n)
{
for(auto e : G[node])
{
int to = node ^ H[e][0] ^ H[e][1];
int c = L[e];
if(to != par)
{
if(sz[to] > n / 2)
return find(to , node , n);
}
}
return node;
}
int ans = INT_MAX;
void get(int node , int par , int len , int h)
{
if(len <= K && a[K - len])
ans = min(ans , a[K - len] + h - 1);
if(len == K)
ans = min(ans , h - 1);
for(auto e : G[node])
{
int to = node ^ H[e][0] ^ H[e][1];
int c = L[e];
if(to != par)
get(to , node , len + c , h + 1);
}
}
void add(int node , int par , int len , int h)
{
if(len <= K)
{
if(a[len] == 0) a[len] = h - 1;
else a[len] = min(a[len] , h - 1);
}
for(auto e : G[node])
{
int to = node ^ H[e][0] ^ H[e][1];
int c = L[e];
if(to != par)
add(to , node , len + c , h + 1);
}
}
void solve(int root)
{
a.clear();
for(auto e : G[root])
{
int to = root ^ H[e][0] ^ H[e][1];
int c = L[e];
get(to , root , c , 2);
add(to , root , c , 2);
}
}
void decomp(int root)
{
getsize(root , 0);
int c = find(root , 0 , sz[root]);
solve(c);
for(auto e : G[c])
{
int to = c ^ H[e][0] ^ H[e][1];
G[to].erase(e);
decomp(to);
}
}
int best_path(int n , int k , int h[][2] , int l[])
{
K = k;
for(int i = 0 ; i < n - 1 ; i++)
{
H[i][0] = h[i][0];
H[i][1] = h[i][1];
L[i] = l[i];
}
for(int i = 0 ; i < n - 1 ; i++)
{
int x = H[i][0];
int y = H[i][1];
G[x].insert(i);
G[y].insert(i);
}
decomp(0);
if(ans == INT_MAX) ans = -1;
return ans;
}
