#include "race.h"
#include <vector>
#include <map>
#define MAXN 200000
struct myc {int x, y;};
std::map <long long, myc> val;
int timp;
std::vector < myc > g[MAXN];
int s[MAXN], k, h[MAXN];
int fiuMare[MAXN], t[MAXN];
long long u[MAXN];
int ans, cine;
bool tip;
void dfs(int x) {
s[x] = 1;
fiuMare[x] = x;
for (auto &y : g[x]) {
if (h[y.x] == 0) {
h[y.x] = h[x] + 1;
u[y.x] = u[x] + y.y;
t[y.x] = x;
dfs(y.x);
s[x] += s[y.x];
if (s[y.x] > s[fiuMare[x]] || fiuMare[x] == x)
fiuMare[x] = y.x;
}
}
}
inline void vezi(int x) {
if (ans == -1 || x < ans)
ans = x;
}
inline void baga(int x) {
myc &t = val[u[x]];
if (t.y != timp || t.x > h[x])
t = {h[x], timp};
}
void tot(int x) {
if (tip)
baga(x);
else {
int e = k + 2 * u[cine] - u[x];
if (e >= 0 && val[e].y == timp)
vezi(h[x] - 2 * h[cine] + val[e].x);
}
for (auto &y : g[x])
if (t[y.x] == x)
tot(y.x);
}
inline void solve(int x) {
bool ok = 1;
while (ok) {
for (auto &y : g[x]) {
if (t[y.x] == x && y.x != fiuMare[x]) {
cine = x;
tip = 0;
tot(y.x);
tip = 1;
tot(y.x);
}
}
baga(x);
int e = u[x] + k;
if (e >= 0 && val[e].y == timp)
vezi(val[e].x - h[x]);
if (t[x] != -1 && fiuMare[t[x]] == x)
x = t[x];
else
ok = 0;
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N - 1; i++)g[H[i][0]].push_back({H[i][1], L[i]}), g[H[i][1]].push_back({H[i][0], L[i]});
for (int i = 0; i < N; i++)
h[i] = 0;
int rad = 0;
h[rad] = 1;
u[rad] = 0;
t[rad] = -1;
dfs(rad);
ans = -1;
k = K;
for (int i = 0; i < N; i++) {
if (fiuMare[i] == i) {
timp++;
solve(i);
}
}
return ans;
}
