Горилла залезает на дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды горилла нашла дерево на $$$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

Примечание

Дерево в первом наборе входных данных первого теста выглядит так: