#include "race.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int MAXK = 101;
const int MAX = 1e5 + 5;
const int LOGMAX = 19;
vector<pii> g[MAX];
int dist[MAX];
int height[MAX];
int timeIn[MAX], timeOut[MAX];
int t = 0;
int par[LOGMAX][MAX];
void dfs1(int node, int p, int h, int d){
par[0][node] = p;
height[node] = h;
dist[node] = d;
timeIn[node] = ++t;
for(auto to:g[node]){
if(to.first == p) continue;
dfs1(to.first, node, h + 1, d + to.second);
}
timeOut[node] = t;
}
bool isAncestor(int u, int v){
return timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v];
}
int lca(int u, int v){
if(isAncestor(u, v)) return u;
if(isAncestor(v, u)) return v;
for(int j = LOGMAX - 1; j >= 0; j--){
if(!isAncestor(par[j][u], v)){
u = par[j][u];
}
}
return par[0][u];
}
int k = 0;
set<pii> s;
int ans = MAX;
void dfs2(int node){
s.insert({dist[node], node});
auto itr = s.lower_bound({dist[node] - k, 0});
if(itr != s.end() && (itr->first) == (dist[node] - k)){
ans = min(ans, height[node] - height[itr->second]);
}
for(pii to:g[node]){
if(to.first == par[0][node]) continue;
dfs2(to.first);
}
s.erase({dist[node], node});
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
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]});
}
dfs1(0, 0, 0, 0);
for(int j = 1; j < LOGMAX; j++){
for (int i = 0; i < N; i++)
{
par[j][i] = par[j - 1][par[j - 1][i]];
}
}
dfs2(0);
if(ans == MAX) return -1;
else return ans;
}
