#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});
}
vector<pair<ll, ll>> dist(N);
auto dfs = [&](auto &&dfs, int u, int p = -1) -> void {
for (auto &[v, w] : adj[u]) {
if (v != p) {
dist[v] = {dist[u].first + w, dist[u].second + 1};
dfs(dfs, v, u);
}
}
};
ll best = LLONG_MAX;
for (int i = 0; i < N; i++) {
dist[i] = {0, 0};
dfs(dfs, i);
for (int j = 0; j < N; j++) {
if (dist[j].first == k) {
best = min(best, dist[j].second);
}
}
}
if (best == LLONG_MAX) best = -1;
return best;
}
