#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
#define el '\n'
const int N = 1e6 + 24;
const ll INF = 1e18;
ll n, k;
vector<pair<ll, ll>> g[N];
ll h[N], d[N]; map<ll, ll> mp[N];
ll res;
void dfs(int u, int pre) {
for (auto [v, w]: g[u]) {
if (v == pre) continue;
d[v] = d[u] + w;
h[v] = h[u] + 1;
dfs(v, u);
}
// cout << u << ':' << d[u] << ' ' << h[u] << el;
}
void stl_dfs(int u, int pre) {
mp[u][d[u]] = h[u];
for (auto [v, w]: g[u]) {
if (v == pre) continue;
stl_dfs(v, u);
if (mp[u].size() < mp[v].size()) {
swap(mp[u], mp[v]);
}
for (auto [dv, hv]: mp[v]) {
if (mp[u].count(k - dv + 2 * d[u])) {
res = min(res, mp[u][k - dv + 2 * d[u]] + hv - 2 * h[u]);
}
if (mp[u].count(dv)) {
mp[u][dv] = min(mp[u][dv], hv);
}
else mp[u][dv] = hv;
}
}
// cout << u << "\n";
// for (auto [dv, hv]: mp[u]) {
// cout << dv << '/' << hv << el;
// }
if (mp[u].count(k + d[u])) {
// cout << "." << mp[u][k + d[u]] - h[u] << el;
res = min(res, mp[u][k + d[u]] - h[u]);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N; k = K;
for (int i = 1; i <= n - 1; i++) {
int u = H[i - 1][0], v = H[i - 1][1];
int w = L[i - 1];
u++, v++;
// cout << u << ' ' << v << ' ' << w << el;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
res = INF;
dfs(1, 0);
stl_dfs(1, 0);
return (res > n ? -1 : res);
}
