/**
* Author: Nicholas Winschel
* Created: 05.10.2023 22:07:36
**/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
int best_path(int N, int K, int H[][2], int L[]) {
V<bool> r(N);
vi s(N);
V<V<pi>> a(N);
if (K==0) return -1;
for (int i = 0; i < N-1; i++) {
a[H[i][0]].emplace_back(H[i][1],i);
a[H[i][1]].emplace_back(H[i][0],i);
}
auto dfs = [&](int n, int p, auto &&dfs) -> int {
s[n]=1;
for (auto e : a[n]) {
if (e.f != p && !r[e.f]) s[n] += dfs(e.f,n,dfs);
}
return s[n];
};
auto gc = [&](int n, int ms, int p, auto &&gc) -> int {
for (auto e : a[n]) {
if (e.f != p && !r[e.f]) {
if (s[e.f] * 2 > ms) return gc(e.f,ms,n,gc);
}
}
return n;
};
int best = N+1;
auto dnq = [&](int n, auto &&dnq) -> void {
int C = gc(n, dfs(n, -1, dfs), -1, gc);
// cout << "cent: " << C << endl;
V<map<ll, int>> cl(sz(a[C]));
map<ll, pi> bes;
auto ins= [&](ll d, int dep) {
// cout << "ins: " << d << " " << dep << endl;
if (!bes.count(d)) {
bes[d]={dep,N+1};
return;
}
if (bes[d].f >= dep) {
bes[d].s=bes[d].f;
bes[d].f=dep;
return;
}
if (bes[d].s >= dep) {
bes[d].s=dep;
return;
}
};
auto gn =[&](ll d, int dep) {
// cout << "gn: " << d << " " << dep << endl;
if (!bes.count(d)) return N+1;
// cout << "ret: " << (dep == bes[d].f ? bes[d].s : bes[d].f) << endl;
return (dep == bes[d].f ? bes[d].s : bes[d].f);
};
auto dfs2 =[&](int v, int p, int c, ll d, int dep, auto &&dfs2) -> void {
if (dep > best || d > K) return;
if (!cl[c].count(d)) cl[c][d]=dep;
cl[c][d] = min(cl[c][d], dep);
for (auto e : a[v]) {
if (e.f != p && !r[e.f]) {
dfs2(e.f, v, c, d+L[e.s], dep+1, dfs2);
}
}
};
for (int i = 0; i < sz(a[C]); i++) if (!r[a[C][i].f]) {
// cout << "dir: " << a[C][i].f << endl;
dfs2(a[C][i].f, C, i, (ll)L[a[C][i].s], 1, dfs2);
if (cl[i].count(K)) best = min(cl[i][K], best);
for (auto pr : cl[i]) {
ins(pr.f, pr.s);
}
}
for (int i = 0; i < sz(a[C]); i++) {
for (auto pr : cl[i]) {
best = min(best, pr.s+gn(K-pr.f,cl[i].count(K-pr.f) ? cl[i][K-pr.f] : -1));
}
}
r[C]=1;
for (auto e : a[C]) {
if (!r[e.f]) dnq(e.f, dnq);
}
};
dnq(0,dnq);
return best > N-1 ? -1 : best;
}
