#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
int d;
struct centroid{
vector<vector<pair<int,int>>> g;
vector<int> par, sz;
vector<ll> dis;
vector<bool> vis;
multiset<pair<ll, int>> st;
int n;
centroid (int _n){
init(_n);
}
void init(int _n){
n = _n;
g.assign(n, vector<pair<int,int>>());
par.assign(n, 0);
sz.assign(n, 0);
vis.assign(n, false);
dis.assign(n, 0ll);
}
void edge(int u, int v, int w){
g[u].push_back({v, w});
g[v].push_back({u, w});
}
int calc_size(int i, int p = -1){
if(vis[i]) return 0;
sz[i] = 1;
for(auto [u, w] : g[i]){
if(u == p) continue;
sz[i] += calc_size(u, i);
}
//cout << i << ": " << sz[i] << ' ' << endl;
return sz[i];
}
int find_centroid(int i, int p, int len){
//cout << "i " << i << ' ';
for(auto [u, w] : g[i]){
if(vis[u] || u == p) continue;
if(sz[u] > len/2) return find_centroid(u, i, len);
}
return i;
}
void decompose(int i = 0, int p = -1){
int c = find_centroid(i, -1, calc_size(i));
vis[c] = true;
par[c] = p;
//cout << c << endl;
dfs(c, -1, 0, 0, 1);
for(auto [u, w] : g[c]){
if(vis[u]) continue;
dfs(u, c, w, 1, -1);
calc(u, c, w, 1);
dfs(u, c, w, 1, 1);
}
dfs(c, -1, 0, 0, -1);
for(auto [u, w] : g[c]){
if(vis[u]) continue;
decompose(u, c);
}
}
int res = 1e9;
void dfs(int i, int p, ll cur, int len, int flag){
if(flag > 0){
//cout << flag << endl;
//cout << i << ' ' << cur << ' ' << len << endl;
st.insert({cur, len});
}else{
//cout << flag << endl;
//cout << i << ' ' << cur << ' ' << len << endl;
st.erase(st.find({cur, len}));
}
for(auto [u, w] : g[i]){
if(vis[u] || u == p) continue;
dfs(u, i, cur + w, len + 1, flag);
}
}
void calc(int i, int p, ll cur, int len){
if(cur > d) return;
auto it = st.lower_bound({d - cur, -1});
if(it != st.end() && it->ff == d - cur){
res = min(res, it->ss + len);
}
for(auto [u, w] : g[i]){
if(vis[u] || u == p) continue;
calc(u, i, cur + w, len + 1);
}
}
};
int best_path(int n, int k, int way[][2], int len[])
{
d = k;
centroid g(n);
for(int i = 0; i < n - 1; i ++){
g.edge(way[i][0], way[i][1], len[i]);
}
g.decompose();
return g.res == 1e9 ? -1 : g.res;
}
