#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
int best_path(int N, int K, int H[][2], int L[]) {
ll k = K;
vector<vector<pair<int, ll>>> adj(N);
for (int i = 0; i < N - 1; i++) {
auto [u, v] = H[i];
ll w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
// [dist, count, at]
using state = tuple<ll, ll, ll>;
ll best = LLONG_MAX;
for (int i = 0; i < N; i++) {
queue<state> pq;
vector<bool> vis(N, false);
pq.push({0, 0, i});
bool found = false;
while (!pq.empty()) {
auto [dist, count, u] = pq.front(); pq.pop();
vis[u] = true;
for (auto &[v, w] : adj[u]) {
if (!vis[v] and dist + w <= k) {
if (dist + w == k) {
best = count;
found = true;
break;
}
pq.push({dist + w, count + 1, v});
}
}
if (found) break;
}
}
if (best == LLONG_MAX) best = -1;
return best;
}
