Вам задано дерево, состоящее из \(n\) вершин и \(n - 1\) ребер, и у каждой вершины \(v\) есть свой счетчик \(c(v)\).
Первоначально в вершине \(s\) расположена фишка, и все счетчики, кроме \(c(s)\), равны \(0\); \(c(s)\) равен \(1\).
Ваша задача — переместить фишку в вершину \(t\). Для этого вы можете совершить следующую последовательность шагов. Пусть сейчас фишка расположена в вершине \(v\). За один шаг вы можете сделать следующее:
- выбрать одну из соседних вершин \(to\) вершины \(v\) равновероятно (\(to\) является соседней вершиной \(v\) тогда и только тогда, когда в дереве есть ребро \(\{v, to\}\));
- передвинуть фишку в вершину \(to\) и увеличить \(c(to)\) на \(1\).
Вы будете повторять данную операцию, пока не достигните вершины \(t\).
Для каждой вершины \(v\) вычислите математическое ожидание значения \(c(v)\) по модулю \(998\,244\,353\).
Выходные данные
Выведите \(n\) чисел: математические ожидания значений \(c(v)\) по модулю \(998\,244\,353\) для каждого \(v\) от \(1\) по \(n\).
Формально, пусть \(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}\).
Примечание
Дерево из первого примера показано ниже:
Посчитаем математическое ожидание
\(E[c(1)]\):
- \(P(c(1) = 0) = 0\), так как \(c(1)\) изначально равно \(1\).
- \(P(c(1) = 1) = \frac{1}{2}\), так как есть только одна последовательность шагов, приводящая к \(c(1) = 1\). Это \(1 \rightarrow 2 \rightarrow 3\) с вероятностью \(1 \cdot \frac{1}{2}\).
- \(P(c(1) = 2) = \frac{1}{4}\): единственный путь \(1 \rightarrow_{1} 2 \rightarrow_{0.5} 1 \rightarrow_{1} 2 \rightarrow_{0.5} 3\).
- \(P(c(1) = 3) = \frac{1}{8}\): единственный путь \(1 \rightarrow_{1} 2 \rightarrow_{0.5} 1 \rightarrow_{1} 2 \rightarrow_{0.5} 1 \rightarrow_{1} 2 \rightarrow_{0.5} 3\).
- \(P(c(1) = i) = \frac{1}{2^i}\) в общем случае.
В результате
\(E[c(1)] = \sum\limits_{i=1}^{\infty}{i \frac{1}{2^i}} = 2\).
Изображение дерева во втором тесте 
Изображение дерева в третьем тесте 
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 3
1 2
2 3
|
2 2 1
|
|
2
|
4 1 3
1 2
2 3
1 4
|
4 2 1 2
|
|
3
|
8 2 6
6 4
6 2
5 4
3 1
2 3
7 4
8 2
|
1 3 2 0 0 1 0 1
|