#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
const int INF = 1e9;
vector <pair <int, int>> g[N];
int ans, k, used[N], dp[N][105];
void dfs(int v) {
used[v] = 1;
for (int i = 1; i <= k; i ++) dp[v][i] = INF;
for (auto i: g[v]) {
if (!used[i.first]) {
dfs(i.first);
for (int j = 1; j <= k; j ++) {
if (j - i.second >= 0) {
dp[v][j] = min(dp[v][j], dp[i.first][j-i.second] + 1);
}
}
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for (int i = 0; i < N; i ++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
int ans = INF;
vector <int> nodes = {0, N/6, N/5, N/4, N/3, N/2, N-1};
for (auto v: nodes) {
memset(used, 0, sizeof(used));
dfs(v);
for (int i = 0; i < N; i ++) {
ans = min(ans, dp[i][k]);
}
}
if (ans == INF) ans = -1;
return ans;
}
