#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
vector<vector<pair<int, int>>> adj;
vector<bool> vis;
vector<int> dist, depth;
void dfs(int u) {
vis[u] = true;
for (auto &p : adj[u]) {
int w = p.second;
int v = p.first;
if (!vis[v]) {
dist[v] = dist[u] + w;
depth[v] = depth[u] + 1;
dfs(v);
}
}
}
int best_path(int n_, int k_, int edges_[][2], int length_[]) {
int n = n_, k = k_;
adj.resize(n);
vis.resize(n, false);
dist.resize(n);
depth.resize(n);
for (int i = 0; i < n - 1; ++i) {
int u = edges_[i][0], v = edges_[i][1], w = length_[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int res = 1e9;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dist[j] = 0;
depth[j] = 0;
vis[j] = false;
}
depth[i] = 0;
dist[i] = 0;
dfs(i);
for (int j = 0; j < n; ++j) {
if (dist[j] == k) {
res = min(res, depth[j]);
}
}
}
return (res == 1e9 ? -1 : res);
}
// int main() {
// int h[10][2] = {
// {0, 1},
// {0, 2},
// {2, 3},
// {3, 4},
// {4, 5},
// {0, 6},
// {6, 7},
// {6, 8},
// {8, 9},
// {8, 10}};
// int l[10] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
// cout << best_path(11, 12, h, l);
// return 0;
// }
