Gojo ma drzewo o $n$ wierzchołkach. Nauczył się techniki kompresji domeny, która działa następująco:

• Najpierw wybiera pewien wierzchołek $v$, który nie został wcześniej usunięty z grafu. Następnie dla każdej pary wierzchołków $u < w$ połączonych z $v$ dodaje nieskierowaną krawędź $(u, w)$, jeśli nie znajdowała się ona wcześniej w grafie. Po tym wymazuje $v$ z grafu wraz ze wszystkimi incydentnymi do niego krawędziami.

Dla każdego $k$ ($1 \le k \le n$) interesuje go łączna liczba krawędzi w pozostałych grafach dla wszystkich $\frac{n!}{(n-k)!}$ sposobów wykonania operacji. Ponieważ odpowiedzi mogą być bardzo duże, wypisz je modulo $998\,244\,353$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($2 \le n \le 10^5$) — liczbę wierzchołków w drzewie.

Kolejne $n - 1$ wierszy zawiera pary liczb całkowitych $u_i, v_i$ ($1 \le u_i, v_i \le n$) — opis krawędzi drzewa.

Wyjście

Wypisz $n$ liczb całkowitych — łączną liczbę krawędzi dla każdego $k$ modulo $998\,244\,353$.

Przykład

Wejście 1

5
1 2
2 3
3 5
3 4

Wyjście 1

16 44 60 0 0

Wejście 2

8
1 2
2 3
2 4
4 5
4 7
7 8
6 7

Wyjście 2

51 316 1596 6120 15720 20160 0 0