Однажды горилла нашла дерево на $$$n$$$ вершинах. Корнем этого дерева является вершина $$$1$$$, а на рёбрах этого дерева записаны веса. Любая порядочная горилла захотела бы залезть на такое дерево и эта не стала исключением. Обратите внимание, что в этой задаче корень дерева находится наверху.
Горилла может начать свой путь в любой вершине с номером $$$v$$$ ($$$2 \le v \le n$$$). Изначально её усталость равна $$$1$$$. Когда горилла поднимается по ребру наверх (ближе к корню), её усталость умножается на вес этого ребра.
Горилла имеет выносливость $$$k$$$, поэтому она откажется идти по ребру, после которого её усталость станет строго больше $$$k$$$ и немедленно закончит путешествие. Если такое ребро не встретилось, горилла закончит путешествие в корне.
Назовём продолжительностью путешествия количество рёбер, по которым прошла горилла. Обозначим продолжительность путешествия из вершины $$$v$$$ как $$$d_v$$$.
Помогите горилле узнать числа $$$d_2, d_3, \ldots, d_n$$$. Другими словами, найдите продолжительности путешествия, если горилла будет начинать свой путь из вершины с номером $$$v$$$ ($$$2 \le v \le n$$$).
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Далее следует описание наборов.
В первой строке каждого набора даны целые числа $$$n, k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — количество вершин в дереве и выносливость гориллы.
В следующих $$$n - 1$$$ строках каждого набора даны целые числа $$$v, u, w$$$ ($$$1 \le v, u \le n$$$, $$$1 \le w \le k$$$) — концы соответствующего ребра в дереве и вес этого ребра.
Гарантируется, что заданный набор рёбер образует дерево. Также гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$n - 1$$$ целое число $$$d_2, d_3, \ldots, d_n$$$.
39 101 2 13 1 33 5 44 3 37 8 46 3 12 7 74 9 14 11 2 12 3 13 4 15 10000000002 1 10000000001 5 103 1 14 2 1000000000
1 1 2 1 2 2 1 3 1 2 3 1 1 1 1
Дерево в первом наборе входных данных первого теста выглядит так:
