#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <unordered_map>
#include "race.h"
#define hyathu main
#define popcorn __builtin_popcount
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr int mmb = 2e5 + 69;
const ld pi = atan(1) * 4;
int f[mmb], v[mmb * 2];
ll w[mmb * 2];
int p[mmb];
unordered_map <ll, int> dist;
ll d[mmb], K;
int h[mmb];
int ans = 2e9;
int el[mmb], in[mmb], ot[mmb], cnt;
void prepare(int i){
in[i] = ++cnt;
el[cnt] = i;
for(int id = f[i]; id < f[i + 1]; ++id){
int nx = v[id];
ll ad = w[id];
if(nx == p[i]) continue;
p[nx] = i;
d[nx] = d[i] + ad;
h[nx] = h[i] + 1;
prepare(nx);
}
ot[i] = cnt;
}
void dfs(int i){
int bigboi = -1, bigcnt = 0;
for(int id = f[i]; id < f[i + 1]; ++id){
int nx = v[id];
ll ad = w[id];
if(nx == p[i]) continue;
if(ot[nx] - in[nx] + 1 > bigcnt){
bigcnt = ot[nx] - in[nx] + 1;
bigboi = nx;
}
}
for(int id = f[i]; id < f[i + 1]; ++id){
int nx = v[id];
if(nx == p[i] || nx == bigboi) continue;
dfs(nx);
dist.clear();
}
if(bigboi != -1)
dfs(bigboi);
for(int id = f[i]; id < f[i + 1]; ++id){
int nx = v[id];
if(nx == p[i] || nx == bigboi) continue;
for(int j = in[nx]; j <= ot[nx]; ++j){
int nd = el[j];
auto it = dist.find(K + 2 * d[i] - d[nd]);
if(it != dist.end())
ans = min(ans, h[nd] + it->second - 2 * h[i]);
}
for(int j = in[nx]; j <= ot[nx]; ++j){
int nd = el[j];
auto res = dist.emplace(d[nd], h[nd]);
if(!res.second)
res.first->second = min(res.first->second, h[nd]);
}
}
auto it = dist.find(K + d[i]);
if(it != dist.end())
ans = min(ans, it->second - h[i]);
auto res = dist.emplace(d[i], h[i]);
if(!res.second)
res.first->second = min(res.first->second, h[i]);
}
int best_path(int n, int k, int h[][2], int l[]){
fill(p, p + n, -1);
K = k;
for(int i = 0; i < n - 1; ++i){
++f[h[i][0]];
++f[h[i][1]];
}
for(int i = 1; i <= n; ++i)
f[i] += f[i - 1];
for(int i = 0; i < n - 1; ++i){
v[--f[h[i][0]]] = h[i][1];
w[f[h[i][0]]] = l[i];
v[--f[h[i][1]]] = h[i][0];
w[f[h[i][1]]] = l[i];
}
prepare(0);
dfs(0);
return (ans == 2e9 ? -1 : ans);
}
