Gojo hat einen Baum mit $n$ Knoten. Er hat die Technik der Domänenkompression erlernt, die wie folgt funktioniert:

• Zuerst wählt er einen Knoten $v$, der zuvor noch nicht aus dem Graphen gelöscht wurde. Als Nächstes fügt er für jedes Paar von Knoten $u < w$, die mit $v$ verbunden sind, eine ungerichtete Kante $(u, w)$ hinzu, sofern diese nicht bereits im Graphen enthalten war. Danach löscht er $v$ mitsamt allen zu ihm inzidenten Kanten aus dem Graphen.

Für jedes $k$ ($1 \le k \le n$) interessiert ihn die Gesamtzahl der Kanten in den verbleibenden Graphen über alle $\frac{n!}{(n-k)!}$ Möglichkeiten, die Operationen durchzuführen. Da die Antworten sehr groß sein können, gib sie modulo $998\,244\,353$ aus.

Eingabe

Die erste Zeile enthält eine ganze Zahl $n$ ($2 \le n \le 10^5$) — die Anzahl der Knoten im Baum.

Die nächsten $n - 1$ Zeilen enthalten Paare ganzer Zahlen $u_i, v_i$ ($1 \le u_i, v_i \le n$) — die Beschreibung der Kanten des Baumes.

Ausgabe

Gib $n$ ganze Zahlen aus — die Gesamtzahl der Kanten für jedes $k$ modulo $998\,244\,353$.

Beispiele

Eingabe 1

5
1 2
2 3
3 5
3 4

Ausgabe 1

16 44 60 0 0

Eingabe 2

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

Ausgabe 2

51 316 1596 6120 15720 20160 0 0