#include "race.h"
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <set>
#include <deque>
#include <utility>
#include <sstream>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <algorithm>
#include <limits.h>
using namespace std ;
#define ff first
#define ss second
#define pb push_back
const int MAX_N = 3e5+2 ;
typedef pair<int,int> ii ;
vector <ii> G[MAX_N];
int depth[MAX_N];
int sz[MAX_N] ;
int ans = 1e9+7 ;
int k ;
int visit[MAX_N];
void calc ( int u, int p, int d ) {
depth[u] = d ;
sz[u] = 1;
for ( auto v:G[u] ) {
if ( visit[v.ff] || v.ff == p) continue ;
calc ( v.ff, u, d+1 ) ;
sz[u] += sz[v.ff] ;
}
}
int centroid ( int u, int p, int el ) {
int ok = 1, x = -1 ;
for ( auto v:G[u] ) {
if ( visit[v.ff] ) continue ;
if ( v.ff!=p ) {
// cout << el/2 << ' ' << v.ff << ' ' << sz[v.ff] << endl ;
ok &= (sz[v.ff] <= el/2) ;
x = max ( x, centroid(v.ff, u, el) ) ;
}
}
if ( ok && (el-sz[u]) <= el/2 ) x = max (x, u) ;
return x ;
}
map <int, int> mp ;
vector <ii> car ;
void doit ( int u, int p, int val ) {
if ( mp[k-val] != 0 ) ans = min ( ans, mp[k-val] + depth[u] - 2 ) ;
car.push_back ({val, depth[u]}) ;
for ( auto v:G[u] ) {
if ( v.ff==p || visit[v.ff] ) continue ;
doit ( v.ff, u, min ( 1000010, val + v.ss ) ) ;
}
}
int go ( int u ) {
calc ( u, -1, 1 ) ;
int root = centroid ( u, -1, sz[u] ) ;
//cout << "centroid = " << root << endl ;
calc ( root, -1, 1 ) ;
mp[0] = 1 ;
for ( auto v:G[root] ) {
if ( visit[v.ff] ) continue ;
doit ( v.ff, root, v.ss ) ;
for ( auto i:car ) {
if ( mp[i.ff] == 0 ) mp[i.ff] = i.ss ;
mp[i.ff] = min ( mp[i.ff], i.ss ) ;
}
car.clear() ;
}
mp.clear() ;
visit[root] = 1 ;
for ( auto v:G[root] ) {
if ( visit[v.ff] ) continue ;
go ( v.ff ) ;
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K ;
for ( int i = 0 ; i+1 < N ;++i ) {
G[H[i][0]].push_back ( {H[i][1], L[i]} ) ;
G[H[i][1]].push_back ( {H[i][0], L[i]} ) ;
}
go ( 0 ) ;
if ( ans > MAX_N ) ans = -1 ;
return ans;
}
