Gojo har ett träd med $n$ hörn. Han har lärt sig tekniken domänkomprimering, som fungerar på följande sätt:

• Först väljer han något hörn $v$ som inte tidigare tagits bort från grafen. Därefter, för varje par av hörn $u < w$ som är förbundna med $v$, lägger han till en oriktad kant $(u, w)$ om den inte redan fanns i grafen. Efter det raderar han $v$ från grafen tillsammans med alla kanter som är incidenta med det.

För varje $k$ ($1 \le k \le n$) är han intresserad av det totala antalet kanter i de återstående graferna över alla $\frac{n!}{(n-k)!}$ sätt att utföra operationerna. Eftersom svaren kan vara mycket stora, skriv ut dem modulo $998\,244\,353$.

Indata

Den första raden innehåller ett heltal $n$ ($2 \le n \le 10^5$) — antalet hörn i trädet.

Därefter följer $n - 1$ rader som innehåller par av heltal $u_i, v_i$ ($1 \le u_i, v_i \le n$) — beskrivningen av trädets kanter.

Utdata

Skriv ut $n$ heltal — det totala antalet kanter för varje $k$ modulo $998\,244\,353$.

Exempel

Indata 1

5
1 2
2 3
3 5
3 4

Utdata 1

16 44 60 0 0

Indata 2

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

Utdata 2

51 316 1596 6120 15720 20160 0 0