#include "race.h"
#include <climits>
#include <vector>
#include <utility> // для pair
using namespace std;
// Рекурсивный DFS вне best_path
void dfs(int v, int p, int length, int edges, int K,
vector<vector<pair<int,int>>> &g, int &answer) {
if(length == K){
if(edges > 0) // путь хотя бы через одну дорогу
answer = min(answer, edges);
return;
}
if(length > K) return;
for(size_t i=0;i<g[v].size();i++){
int u = g[v][i].first;
int w = g[v][i].second;
if(u != p){
dfs(u, v, length + w, edges + 1, K, g, answer);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
vector<vector<pair<int,int>>> g(N);
for(int i=0;i<N-1;i++){
g[H[i][0]].push_back(make_pair(H[i][1], L[i]));
g[H[i][1]].push_back(make_pair(H[i][0], L[i]));
}
int answer = INT_MAX;
for(int i=0;i<N;i++){
dfs(i, -1, 0, 0, K, g, answer);
}
if(answer == INT_MAX) return -1;
return answer;
}
