#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<vector<int>>> edg;
int curr = 0;
int r = 0;
int mn = 1e9;
bool found = 0;
int k;
vector<int> vis;
void dfs(int idx) {
if (curr == k) {
mn = min(r, mn);
found = 1;
return;
}
for (auto &i : edg[idx]) {
if (!vis[i[0]]) {
vis[i[0]] = 1;
curr += i[1];
r++;
dfs(i[0]);
r--;
curr -= i[1];
vis[i[0]] = 0;
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
edg.resize(N);
vis.resize(N);
for (int i = 0 ; i < N - 1; i++) {
edg[H[i][0]].push_back({H[i][1], L[i]});
edg[H[i][1]].push_back({H[i][0], L[i]});
}
for (int i = 0; i < N; i++) {
vis[i] = 1;
dfs(i);
vis[i] = 0;
}
return ((found) ? mn : -1);
}
