#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> AdjList[200000];
bitset<200000> visited1[100];
bitset<200000> visited2[100];
int prv[100][200000];
int best_path(int N, int K, int H[][2], int L[]) {
for(int i = 0; i+1 < N; i++) {
AdjList[H[i][0]].push_back({L[i], H[i][1]});
AdjList[H[i][1]].push_back({L[i], H[i][0]});
}
queue<pair<pair<int, int>, pair<pair<int, int>, int>>> q;
for(int i = 0; i < N; i++)
q.push({{i, -1}, {{0, 0}, -1}});
int u, p, d, s, to;
while(!q.empty()) {
u = q.front().first.first;
p = q.front().first.second;
d = q.front().second.first.first;
s = q.front().second.first.second;
to = q.front().second.second;
q.pop();
for(auto v: AdjList[u]) {
if(v.second != p && (to == -1 || to == v.second)) {
if(d+v.first == K)
return s+1;
if(d+v.first > K) continue;
if(K <= 100) {
if(!visited1[d+v.first][v.second]) {
visited1[d+v.first][v.second]=1;
q.push({{v.second, u}, {{d+v.first, s+1}, -1}});
prv[d+v.first][v.second] = u;
} else if(!visited2[d+v.first][v.second] && prv[d+v.first][v.second] != u) {
visited2[d+v.first][v.second]=1;
q.push({{v.second, u}, {{d+v.first, s+1}, prv[d+v.first][v.second]}});
}
} else {
q.push({{v.second, u}, {{d+v.first, s+1}, -1}});
}
}
}
}
return -1;
}
