#include "race.h"
#include <bits/stdc++.h>
using namespace std;
template <class T> using v = vector<T>;
using int2 = pair<int, int>;
using ll = long long;
using ll2 = pair<ll, ll>;
#define f first
#define s second
#define all(x) begin(x), end(x)
struct Paths {
ll2 d = {0, 0};
unordered_map<ll, ll> m;
};
#define dbg(x) cerr << "[" << __LINE__ << "] " << #x << " = " << (x) << '\n';
void dfs(v<v<int2>> &adj, v<Paths> &paths, int &ans, int k, int node,
int prev) {
Paths cur;
for (auto next : adj[node]) {
if (next.f != prev) {
dfs(adj, paths, ans, k, next.f, node);
}
}
for (auto i : adj[node]) {
// dbg(node);
if (i.f != prev) {
for (auto j : adj[node]) {
if (i.f > j.f && j.f != prev) {
int2 i2 = i;
int2 j2 = j;
if (paths[i.f].m.size() < paths[j.f].m.size()) {
swap(i2, j2);
}
for (auto x : paths[i2.f].m) {
ll cost = x.f + paths[i2.f].d.f + i2.s + j2.s;
if (paths[j2.f].m.count(k - cost - paths[j2.f].d.f)) {
ans = min(ans, (int)(x.s + paths[i2.f].d.s +
paths[j2.f].m[k - cost - paths[j2.f].d.f] +
paths[j2.f].d.s + 2));
}
}
if (i2.s + j2.s == k) {
ans = min(ans, 2);
}
}
}
}
}
for (auto next : adj[node]) {
if (next.f != prev) {
#define p paths[next.f]
if (p.m.size() > cur.m.size()) {
p.m.swap(cur.m);
swap(p.d, cur.d);
cur.d.f += next.s;
cur.d.s += 1;
} else {
p.d.f += next.s;
p.d.s += 1;
}
// dbg(node);
// dbg(p.m.size());
for (auto x : p.m) {
ll cost = x.f + p.d.f;
// dbg(cost);
// dbg(cur.d.s);
ll vx = x.s + p.d.s;
if (cost < k && vx < ans) {
if (cur.m.count(cost - cur.d.f)) {
cur.m[cost - cur.d.f] = min(cur.m[cost], vx - cur.d.s);
} else {
cur.m[cost - cur.d.f] = vx - cur.d.s;
}
}
}
cur.m[next.s - cur.d.f] = 1 - cur.d.s;
// dbg(cur.m[next.s - cur.d.f]);
}
}
// dbg(cur.m.size());
if (cur.m.count(k - cur.d.f)) {
// dbg(node);
// dbg(cur.m[k - cur.d.f]);
ans = min(ans, (int)(cur.m[k - cur.d.f] + cur.d.s));
}
paths[node] = {cur.d, move(cur.m)};
}
int best_path(int N, int K, int H[][2], int L[]) {
int ans = INT_MAX;
v<v<int2>> adj(N);
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]});
}
v<Paths> paths(N);
dfs(adj, paths, ans, K, 0, -1);
if (ans == INT_MAX)
ans = -1;
return ans;
}
