Gojo tiene un árbol con $n$ vértices. Aprendió la técnica de compresión de dominio, que funciona de la siguiente manera:

• Primero, elige algún vértice $v$ que no haya sido eliminado previamente del grafo. A continuación, para cada par de vértices $u < w$ que están conectados con $v$, añade una arista no dirigida $(u, w)$ si no estaba previamente contenida en el grafo. Después de eso, borra $v$ del grafo junto con todas las aristas incidentes a él.

Para cada $k$ ($1 \le k \le n$), le interesa el número total de aristas en los grafos restantes para todas las $\frac{n!}{(n-k)!}$ formas de realizar las operaciones. Como las respuestas pueden ser muy grandes, imprímelas módulo $998\,244\,353$.

Entrada

La primera línea contiene un entero $n$ ($2 \le n \le 10^5$) — el número de vértices en el árbol.

A continuación, $n - 1$ líneas contienen pares de enteros $u_i, v_i$ ($1 \le u_i, v_i \le n$) — la descripción de las aristas del árbol.

Salida

Imprime $n$ enteros — el número total de aristas para cada $k$ módulo $998\,244\,353$.

Ejemplos

Entrada 1

5
1 2
2 3
3 5
3 4

Salida 1

16 44 60 0 0

Entrada 2

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

Salida 2

51 316 1596 6120 15720 20160 0 0