#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 10;
vector<pair<int, long long>> adj[NN];
long long dist[NN], depth[NN], tin[NN], tout[NN], timer, up[NN][20];
void dfs(int node, int parent) {
tin[node] = ++timer;
up[node][0] = parent;
for (int i = 1; i < 20; i++) {
up[node][i] = up[up[node][i - 1]][i - 1];
}
for (auto [u, w] : adj[node]) {
if (u == parent) continue;
depth[u] = depth[node] + 1;
dist[u] = dist[node] + w;
dfs(u, node);
}
tout[node] = timer;
}
bool herna(int a, int b) {
return tin[b] >= tin[a] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (herna(a, b)) return a;
if (herna(a, b)) return b;
for (int i = 19; i >= 0; i--) {
if (!herna(up[a][i], b)) {
a = up[a][i];
}
}
return up[a][0];
}
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] });
}
dfs(0, 0);
int ans = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int lc = lca(i, j);
long long D = dist[i] + dist[j] - 2 * dist[lc];
int dp = depth[i] + depth[j] - 2 * depth[lc];
if (D == K) {
ans = min(ans, dp);
}
}
}
return (ans == n ? -1 : ans);
}
