#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int MX = 1200;
vector<vector<pair<int, int>>> adj(MX);
vector<bool> visited(MX, false);
pair<bool, int> dfs(int x, int K, int l = 0, int nh = 0)
{
if (visited[x])
{
return {false, nh};
}
if (l == K)
{
return {true, nh};
}
visited[x] = true;
int poss = false, rnh = 1E9;
for (pair<int, int> v : adj[x])
{
pair<bool, int> ret = dfs(v.first, K, l + v.second, nh + 1);
// cout << x << " " << y << " " << ret.first << " " << ret.second << "__________" << "\n";
if (ret.first)
{
poss = true;
rnh = min(ret.second, rnh);
}
}
return {poss, rnh};
}
int best_path(int N, int K, int H[][2], int L[])
{
for (int i = 0; i < N - 1; i++)
{
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
int ans = -1;
for (int i = 0; i < N; i++)
{
visited = vector<bool>(MX, false);
pair<bool, int>
ret = dfs(i, K);
// cout << i << " " << j << " " << ret.first << " " << ret.second << " \n";
if (ret.first)
{
if (ans == -1)
{
ans = ret.second;
}
else
{
ans = min(ans, ret.second);
}
}
}
return ans;
}
