E. Приключения Алисы в кроличьей норе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса находится на дне кроличьей норы! Кроличья нора может быть смоделирована как дерево$$$^{\text{∗}}$$$, у которого выход находится на вершине $$$1$$$, а Алиса начинает с некоторой вершины $$$v$$$. Она хочет выбраться из норы, но, к сожалению, Дама Червей приказала её казнить.

Каждую минуту подбрасывается обычная монета. Если выпадает орёл, Алиса может переместиться в любую вершину, смежную со своим текущим положением, а если решка, Дама Червей может перетащить Алису на смежную вершину по своему выбору. Если Алиса когда-либо окажется на любом из некорневых листьев$$$^{\text{†}}$$$ дерева, Алиса проигрывает.

Предполагая, что они обе действуют оптимально, для каждой начальной вершины $$$1\le v\le n$$$ вычислите вероятность того, что Алиса сможет убежать. Поскольку эти вероятности могут быть очень малыми, выведите их по модулю $$$998\,244\,353$$$.

Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что точный ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

$$$^{\text{∗}}$$$Дерево — это связный простой граф, который имеет $$$n$$$ вершин и $$$n-1$$$ рёбер.

$$$^{\text{†}}$$$Лист — это вершина, соединённая ровно с одним ребром.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — количество вершин в дереве.

$$$i$$$-я из следующих $$$n - 1$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$ и $$$x_i \neq y_i$$$) — рёбра дерева. Гарантируется, что заданные ребра образуют дерево.

Сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел в одной строке — вероятности того, что Алиса убежит, начиная с вершины $$$1, 2, \ldots, n$$$. Поскольку эти вероятности могут быть очень малыми, выведите их по модулю $$$998\,244\,353$$$.

Пример
Входные данные
2
5
1 2
1 3
2 4
3 5
9
1 2
2 3
4 5
5 6
7 8
8 9
2 4
5 7
Выходные данные
1 499122177 499122177 0 0 
1 499122177 0 332748118 166374059 0 443664157 720954255 0
Примечание

Для первого набора входных данных:

  1. Алиса убегает из корня (вершина $$$1$$$) по определению с вероятностью $$$1$$$.
  2. Алиса немедленно проигрывает из вершин $$$4$$$ и $$$5$$$, так как они являются листьями.
  3. Из других двух вершин Алиса убегает с вероятностью $$$\frac 12$$$, так как Дама перетащит её к листьям.