Gojo ha un albero con $n$ vertici. Ha imparato la tecnica della compressione del dominio, che funziona nel modo seguente:

• Per prima cosa, sceglie un vertice $v$ che non è stato precedentemente eliminato dal grafo. Successivamente, per ogni coppia di vertici $u < w$ collegati a $v$, aggiunge un arco non orientato $(u, w)$ se non era già presente nel grafo. Dopodiché, cancella $v$ dal grafo insieme a tutti gli archi incidenti a esso.

Per ogni $k$ ($1 \le k \le n$), è interessato al numero totale di archi nei grafi rimanenti per tutti gli $\frac{n!}{(n-k)!}$ modi di eseguire le operazioni. Poiché le risposte possono essere molto grandi, stampale modulo $998\,244\,353$.

Input

La prima riga contiene un intero $n$ ($2 \le n \le 10^5$) — il numero di vertici nell'albero.

Successivamente, $n - 1$ righe contengono coppie di interi $u_i, v_i$ ($1 \le u_i, v_i \le n$) — la descrizione degli archi dell'albero.

Output

Stampa $n$ interi — il numero totale di archi per ciascun $k$ modulo $998\,244\,353$.

Esempi

Input 1

5
1 2
2 3
3 5
3 4

Output 1

16 44 60 0 0

Input 2

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

Output 2

51 316 1596 6120 15720 20160 0 0