// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define ll long long
#define mod 1000000007
#define all(x) x.begin(), x.end()
template <typename T>
using super_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define O_O() ({ \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
})
// int dx[]= {-1, 1, 0, 0, -1,-1, 1, 1};
// int dy[]= { 0, 0,-1, 1, -1, 1,-1, 1};
const int N = 2e5 + 9, M = 1e6 + 9;
int n, k, arr[N], ans = mod, siz[N];
vector < pair < int , int > > g[N];
bitset < N > virginity;
void dfs(int bap, int dada) {
siz[bap] = 1;
for(auto [cld, val] : g[bap]) {
if(cld == dada or virginity[cld]) continue;
dfs(cld, bap);
siz[bap] += siz[cld];
}
}
int find(int bap, int dada, int sz) {
for(auto [cld, val] : g[bap]) {
if(cld == dada or virginity[cld]) continue;
if(siz[cld] > sz) return find(cld, bap, sz);
}
return bap;
}
gp_hash_table < int , int > Sum;
void query(int bap, int dada, int sum, int dep = 1) {
if(sum > k) return;
if(Sum.find(k - sum) != Sum.end()) {
ans = min(ans, dep + Sum[k - sum]);
// cerr << bap << ' ' << sum << ' ' << dep << ' ' << Sum[k - sum] << endl;
}
for(auto[cld, val] : g[bap]) {
if(cld == dada or virginity[cld]) continue;
query(cld, bap, sum + val, dep + 1);
}
}
void update(int bap, int dada, int sum, int dep = 1) {
if(sum > k) return;
int mx = Sum[sum];
if(mx == 0) mx = mod;
Sum[sum] = min(mod, dep);
for(auto[cld, val] : g[bap]) {
if(cld == dada or virginity[cld]) continue;
update(cld, bap, sum + val, dep + 1);
}
}
void calculate_ans(int king) {
Sum.clear();
Sum[0] = 0;
for(auto[cld, val] : g[king]) {
if(virginity[cld]) continue;
query(cld, cld, val);
update(cld, cld, val);
}
}
void solve_sub_prob(int curr) {
dfs(curr, curr);
int king = find(curr, curr, siz[curr] / 2);
virginity[king] = 1;
calculate_ans(king);
for(auto [cld, val] : g[king]) {
if(virginity[cld]) continue;
solve_sub_prob(cld);
}
}
void solve()
{
solve_sub_prob(1);
}
int best_path(int N, int K, int H[][2], int L[])
{
for (int i = 0; i < N - 1; ++i)
{
int u = H[i][0]++, v = H[i][1]++, w = L[i];
g[u].emplace_back(v, w), g[v].emplace_back(u, w);
}
n = N; k = K;
solve();
if(ans == mod) ans = -1;
return ans;
}
