#include <bits/stdc++.h>
using namespace std;
template< class T, class T2 > inline bool chkmin( T& a, const T2& b ){ return a > b ? a = b, 1 : 0 ; }
#ifndef LOCAL
#define cerr if( false )cerr
#endif
#define out(x) #x << " = " << x << " "
typedef long long ll;
const int MAX_N = 1e6 + 42;
const ll mod = 1e9 + 7;
int n, k;
std::vector< std::pair< int , int >> v[MAX_N];
int l[MAX_N];
bool viz[MAX_N];
int sz[MAX_N];
void dfs( int x, int par = -1 ){
cerr << out( x ) << out( par ) << endl;
sz[x] = 1;
for( auto J : v[x] ){
int j = J.first;
if( j == par || viz[j] ) continue;
dfs( j, x );
sz[x] += sz[j];
}
}
int centroid( int x, int SZ, int par = -1 ){
cerr << out( x ) << out( SZ ) << endl;
for( auto J : v[x] ){
int j = J.first;
if( j == par || viz[j] ) continue;
if( sz[j] > ( SZ / 2 ) ) return centroid( j, SZ, x );
}
return x;
}
std::unordered_map< int , std::pair< int, int > >m;
ll nas = mod;
int tt = 0;
void findNas( int x, bool type, int len, int par = -1, int d = 1 ){
auto pos = m.find( k - len );
//if( pos != m.end() and ( pos->second.second < tt ) ) m.erase( pos );
if( type ){
if( pos != m.end() and ( pos->second.second >= tt ) ){
chkmin( nas, d + pos->second.first );
}
}else{
auto pos2 = m.find( len );
if( pos2 == m.end() || pos2->second.second < tt ) m[len] = { d, tt };
if( pos2 != m.end() and pos2->second.second == tt and pos2->second.first > d ){
m[len] = { d, tt };
}
}
for( auto J : v[x] ){
int j = J.first;
if( j == par || viz[j] ) continue;
findNas( j, type, len + J.second, x, d + 1 );
}
}
void centDecomp( int x, int par = -1 ){
cerr << out( x ) << endl;
dfs( x );
int c = centroid( x, sz[x] );
cerr << out( c ) << endl;
viz[c] = true;
for( auto J : v[c] ){
int j = J.first;
if( viz[j] ) continue;
findNas( j, true , J.second);
findNas( j, false, J.second );
}
tt ++;
for( auto J : v[c] ){
int j = J.first;
if( viz[j] ) continue;
centDecomp( j, c );
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for( int i=0 ; i < n-1 ; i ++ ){
int a = H[i][0];
int b = H[i][1];
v[a].push_back({ b, L[i] });
v[b].push_back({ a, L[i] });
}
m[0] = { 0, mod };
centDecomp( 0 );
if( nas == mod ) nas = -1;
return nas;
}
