#include "race.h"
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
const int INF = 1e9, MAXN = 2e5+10;
int ans = MAXN;
map<long long, int> mp[MAXN];
vector<pair<int,int>> G[MAXN];
void dfs(int u, int p, int dep, long long d, long long k){
mp[u][d] = dep;
for(auto [v, w] : G[u]){
if(v == p) continue;
dfs(v, u, dep+1, d+w, k);
for(auto w : mp[v]){
long long tmp = k-w.first+2*dep;
if(mp[u].count(tmp)) ans = min(ans, w.second+mp[u][tmp]-2*dep);
}
for(auto w : mp[v]){
if(mp[u].count(w.first)) mp[u][w.first] = min(mp[u][w.first], w.second);
else mp[u][w.first] = w.second;
}
}
if(mp[u].count(k+d)) ans = min(ans, mp[u][k+d]-dep);
}
int best_path(int MAXN, int K, int H[][2], int L[])
{
for(int i = 0; i < MAXN-1; i++){
int u = H[i][0], v = H[i][1];
G[u].emplace_back(v, L[i]);
G[v].emplace_back(u, L[i]);
}
dfs(0, 0, 0, 0, K);
if(ans >= MAXN) ans = -1;
return ans;
}
