Race

Problem Source

IOI 2011

Problem Description

You are given a tree with $n$ vertices, each edge carrying a positive weight. Find a simple path whose total weight equals $k$, minimizing the number of edges on the path.

Input Format

The first line contains two integers $n, k$ ($1 \leq n \leq 2 \times 10^5,\ 1 \leq k \leq 10^6$).

The next $n - 1$ lines each contain three integers describing one undirected edge: its two endpoints and its weight. The weight is guaranteed to be a positive integer not exceeding $10^6$.

Note that the vertices are numbered starting from $0$.

Output Format

Output one integer: the minimum number of edges. If no such path exists, output -1.

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

2

Constraints

• $1 \leq n \leq 2 \times 10^5$
• $1 \leq k \leq 10^6$
• Edge weights are positive integers $\leq 10^6$
• Vertices are numbered from $0$