플래티넘 IVYou are given a tree with \(n\) vertices (\(0 \dots n-1\)) and weighted edges. Among all simple paths whose edge-length sum is exactly \(K\), output the minimum number of edges on such a path, or -1 if no path has total length exactly \(K\).
Note. This is an adaptation of an IOI function-implementation task to an interactive stdin/stdout problem. The test data is RiseOJ-generated (self-validated against an independent brute force), not the official IOI data.
Interaction / I/O protocol
Input. Line 1: \(n\) and \(K\). Each of the next \(n-1\) lines contains three integers \(a\), \(b\), \(w\) — an edge between \(a\) and \(b\) of length \(w\).
Output. Print one integer: the fewest edges, or -1.
Example. Edges (0,1,1) (0,2,2) (1,3,3), \(K=4\): the path \(0\!-\!1\!-\!3\) has length \(1+3=4\) using 2 edges, which is fewest.
- \(1 \le n \le 200{,}000\)
- \(1 \le K \le 10^{6}\)
- \(1 \le w \le 10^{6}\); the graph is a tree.
Line 1: \(n\) and \(K\). Each of the next \(n-1\) lines contains three integers \(a\), \(b\), \(w\) — an edge between \(a\) and \(b\) of length \(w\).
Print one integer: the fewest edges, or -1.