Gojo har et tre med $n$ noder. Han har lært teknikken domenekomprimering, som fungerer på følgende måte:

• Først velger han en node $v$ som ikke tidligere har blitt slettet fra grafen. Deretter, for hvert par av noder $u < w$ som er forbundet med $v$, legger han til en urettet kant $(u, w)$ hvis den ikke allerede fantes i grafen. Etter det sletter han $v$ fra grafen sammen med alle kanter som er insidente til den.

For hver $k$ ($1 \le k \le n$) er han interessert i det totale antallet kanter i de gjenværende grafene over alle de $\frac{n!}{(n-k)!}$ måtene å utføre operasjonene på. Siden svarene kan bli svært store, skriv dem ut modulo $998\,244\,353$.

Inndata

Den første linjen inneholder et heltall $n$ ($2 \le n \le 10^5$) — antallet noder i treet.

De neste $n - 1$ linjene inneholder par av heltall $u_i, v_i$ ($1 \le u_i, v_i \le n$) — beskrivelsen av kantene i treet.

Utdata

Skriv ut $n$ heltall — det totale antallet kanter for hver $k$ modulo $998\,244\,353$.

Eksempler

Inndata 1

5
1 2
2 3
3 5
3 4

Utdata 1

16 44 60 0 0

Inndata 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