#include <iostream>
#include <climits>
#include "race.h"
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
vector<vector<pair<int, long long>>> adjList;
int DFS(int currNode, int parentNode, int costUsed, int depth, int K)
{
//cout<<"curr node "<<currNode<<endl;
if(costUsed == K)
return depth;
if(costUsed > K)
return -1;
int bestL = INT_MAX;
for(auto node : adjList[currNode])
{
//cout<<"child: "<<node.first<<endl;
if(node.first == parentNode)
continue;
int l = DFS(node.first, currNode, costUsed+node.second, depth+1, K);
//cout<<"l = "<<l<<endl;
if(l < bestL && l!= -1)
{bestL = l;
//cout<<"new best L"<<endl;
}
}
if(bestL ==INT_MAX)
return -1;
return bestL;
}
int best_path(int N, int K, int H[][2], int L[])
{
adjList.resize(N);
for(int i =0; i<N-1; ++i)
{
adjList[H[i][0]].push_back({H[i][1], L[i]});
adjList[H[i][1]].push_back({H[i][0], L[i]});
}
////cout<<"here"<<endl;
int bestPath = INT_MAX;
for(int i =0 ; i<N; ++i)
{
int l = DFS(i, -1, 0, 0, K);
//////cout<<"DFS sur"<<endl;
if(l != -1 && l < bestPath)
bestPath = l;
}
////cout<<"there"<<endl;
if(bestPath == INT_MAX)
return -1;
return bestPath;
}
