#include "race.h"
#include <bits/stdc++.h>
#define ll long long
const int mxn = 200005;
const int inf = 1e9;
using namespace std;
set<pair<ll,int> > s[mxn];
vector<pair<int,int> > g[mxn];
int n,k;
int ans;
void dfs(int x,int p,ll dis,int dep){
s[x].insert({dis,dep});
for(auto par : g[x]){
int y = par.first;
int z = par.second;
if(y == p)continue;
dfs(y,x,dis+z,dep+1);
if(s[x].size() < s[y].size())swap(s[x],s[y]);
for(auto par2 : s[y]){
int len= par2.first;
int cnt = par2.second;
ll q = k - len + 2*dis;
auto it = s[x].lower_bound({q,0});
if(it != s[x].end() && (*it).first == q){
ans = min(ans, (*it).second + cnt - 2 * dep);
}
}
s[x].insert(s[y].begin(),s[y].end());
}
}
int best_path(int _n, int _k, int H[][2], int L[]){
n = _n;
k = _k;
//vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n - 1; i++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
ans = n;
//vector<set<pair<ll, int>>> s(n);
// auto dfs = [&](auto dfs, int x, int p, ll dis, int dep) -> void {
// //s[x].emplace(dis, dep);
// s[x].insert({dis,dep});
// for (auto [y,z] : g[x]) {
// if (y == p) continue;
// dfs(dfs, y, x, dis + z, dep + 1);
// if (s[x].size() < s[y].size()) {
// swap(s[x], s[y]);
// }
// for (auto [len, cnt] : s[y]) {
// ll q = k - len + 2 * dis;
// auto it = s[x].lower_bound({q, 0});
// if (it != s[x].end() && (*it).first == q) {
// ans = min(ans, (*it).second + cnt - 2 * dep);
// }
// }
// s[x].insert(s[y].begin(), s[y].end());
// }
// };
dfs( 0, -1, 0, 0);
if (ans == n) {
ans = -1;
}
return ans;
}
//Pls work
