Gojo á tré með $n$ hnútum. Hann lærði tæknina svæðisþjöppun (domain compression), sem virkar á eftirfarandi hátt:

• Fyrst velur hann einhvern hnút $v$ sem ekki hefur áður verið eytt úr netinu. Næst, fyrir hvert par hnúta $u < w$ sem eru tengdir við $v$, bætir hann við óstefndum legg $(u, w)$ ef hann var ekki þegar í netinu. Eftir það strokar hann $v$ út úr netinu ásamt öllum leggjum sem liggja að honum.

Fyrir hvert $k$ ($1 \le k \le n$) hefur hann áhuga á heildarfjölda leggja í netunum sem eftir standa fyrir allar $\frac{n!}{(n-k)!}$ leiðirnar til að framkvæma aðgerðirnar. Þar sem svörin geta verið mjög stór skal prenta þau módúló $998\,244\,353$.

Inntak

Fyrsta línan inniheldur heiltölu $n$ ($2 \le n \le 10^5$) — fjölda hnúta í trénu.

Næstu $n - 1$ línur innihalda pör af heiltölum $u_i, v_i$ ($1 \le u_i, v_i \le n$) — lýsingu á leggjum trésins.

Úttak

Prentið $n$ heiltölur — heildarfjölda leggja fyrir hvert $k$ módúló $998\,244\,353$.

Dæmi

Inntak 1

5
1 2
2 3
3 5
3 4

Úttak 1

16 44 60 0 0

Inntak 2

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

Úttak 2

51 316 1596 6120 15720 20160 0 0