#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define ll long long
#define mod INT_MAX
const int N = 2e5 + 40, M = 1e6 + 9;
int n, k, ans = mod, siz[N], in[N], out[N], depth[N], flat[N], timer = 0;
ll euler[N];
vector < pair < int , int > > g[N];
vector < bool > virginity(N);
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;
}
void euler_tour(int bap, int dada, ll curr_val = 0, int dep = 0) {
in[bap] = ++timer;
flat[timer] = bap;
euler[bap] = curr_val;
depth[bap] = dep;
for(auto[cld, val] : g[bap]) {
if(cld == dada or virginity[cld]) continue;
euler_tour(cld, bap, val + curr_val, dep + 1);
}
out[bap] = timer;
}
void calculate_ans(int king) {
timer = 0;
euler_tour(king, king);
gp_hash_table < ll , int > gp;
gp[0] = 0;
for(auto[cld, val] : g[king]) {
// Query
for (int i = in[cld]; i <= out[cld]; i++)
{
// if(euler[i] > k) continue;
int v = flat[i];
ll need = k - euler[v];
auto it = gp.find(need);
if(it != gp.end()) {
ans = min(ans, depth[v] + gp[need]);
}
}
// Update
for(int i = in[cld]; i <= out[cld]; i++) {
//if(euler[i] > k) continue;
int v = flat[i];
auto it = gp.find(euler[v]);
if(it == gp.end()) {
gp[euler[v]] = depth[v];
}
else {
gp[euler[v]] = min(depth[v], gp[euler[v]]);
}
}
}
}
void solve_sub_prob(int curr) {
dfs(curr, curr);
int king = find(curr, curr, siz[curr] / 2);
calculate_ans(king);
virginity[king] = 1;
for(auto [cld, val] : g[king]) {
if(virginity[cld]) continue;
solve_sub_prob(cld);
}
}
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);
}
k = K;
solve_sub_prob(0);
if(ans == mod) ans = -1;
return ans;
}
// void solve()
// {
// cin >> n >> k;
// pair<int, int> pr[n + 9];
// for (int i = 1; i < n; i++)
// {
// cin >> pr[i].first >> pr[i].second;
// }
// for (int i = 1; i < n; i++)
// {
// int x; cin >> x;
// g[pr[i].first].push_back({pr[i].second,x});
// g[pr[i].second].push_back({pr[i].first, x});
// }
// solve_sub_prob(0);
// if (ans < mod)
// cout << ans << endl;
// else
// cout << -1 << endl;
// }
// int main()
// {
// solve();
// return 0;
// }
