#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
//#define endl '\n'
using ll = long long;
#define pb push_back
#define pF first
#define pS second
#define SP <<' '<<
#define all(x) (x).begin(), (x).end()
const ll mod7 = 1e9+7, mod9= 998244353, MAX_N = 10000000;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<ll,ll>> adj[212345];
ll ans = 1e9, k, deleted[212345], sub[212345];
ll cn = 0;
vector<pair<ll, ll>> m(212345);
ll tim = 0;
void qDFS(ll i, ll p, ll sum, ll d) {
if (m[k-sum].pS == tim) {
ans = min(ans, m[k-sum].pF + d);
}
for (auto [j, c] : adj[i]) {
if (deleted[j] || j == p) continue;
qDFS(j, i, sum + c, d + 1);
}
}
void updDFS(ll i, ll p, ll sum, ll d) {
m[sum] = {min((m[sum].pS == tim ? m[sum].pF : (ll)1e9), d), tim};
for (auto [j, c] : adj[i]) {
if (deleted[j] || j == p) continue;
updDFS(j, i, sum + c, d + 1);
}
}
void solveDFS(ll i, ll p) {
for (auto [j, c] : adj[i]) {
if (deleted[j]) continue;
qDFS(j, i, c, 1);
updDFS(j, i, c, 1);
}
}
void initDFS(ll i, ll p) {
cn++;
sub[i] = 1;
for (auto [j, c] : adj[i]) {
if (j == p || deleted[j]) continue;
initDFS(j, i);
sub[i] += sub[j];
}
}
ll cenDFS(ll i, ll p) {
for (auto [j, c] : adj[i]) {
if (j == p || deleted[j] || sub[j] <= cn/2) continue;
return cenDFS(j, i);
}
return i;
}
void decompose(ll i) {
cn = 0;
initDFS(i, i);
ll cen = cenDFS(i, i);
tim++;
m[0] = {0, tim};
solveDFS(cen, cen);
deleted[cen] = true;
for (auto [j, c] : adj[cen]) {
if (deleted[j]) continue;
decompose(j);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
int n = N;
k = K;
for (int i=0; i<=n-2; i++) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
decompose(0);
return (ans == 1e9 ? -1 : ans);
}
