#include <bits/stdc++.h>
#include "race.h"
using namespace std;
// #include "grader.cpp"
#define all(x) x.begin(), x.end()
const int l = 20;
int best_path(int N, int K, int H[][2], int L[]) {
int n = N, k = K;
vector<vector<pair<int, int>>> adj(n);
for(int i = 0; i < n - 1; i++) {
auto [u, v] = H[i];
adj[u].emplace_back(v, L[i]);
adj[v].emplace_back(u, L[i]);
}
vector<int> tin(n), tout(n), d(n);
vector<long long> sd(n);
vector<vector<int>> jmp(n, vector<int>(l + 1));
int timer = 0;
auto dfs = [&](auto &&self, int v, int p) -> void {
jmp[v][0] = p;
for(int i = 1; i <= l; i++) {
jmp[v][i] = jmp[ jmp[v][i - 1] ][i - 1];
}
tin[v] = timer++;
for(auto [to, w] : adj[v]) {
if(to == p) continue;
sd[to] = sd[v] + w;
d[to] = d[v] + 1;
self(self, to, v);
}
tout[v] = timer++;
};
dfs(dfs, 0, 0);
auto upper = [&](int u, int v) {
return tin[v] > tin[u] && tout[v] < tout[u];
};
auto lca = [&](int u, int v) {
if(upper(u, v)) return u;
if(upper(v, u)) return v;
for(int i = l; i >= 0; i--) {
if(!upper(jmp[u][i], v)) u = jmp[u][i];
}
return jmp[u][0];
};
int ans = 1e9;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
int p = lca(i, j);
if(sd[i] + sd[j] - 2 * sd[p] == k) {
ans = min(ans, d[i] + d[j] - 2 * d[p]);
}
}
}
if(ans == 1e9) ans = -1;
return ans;
}
