Gojolla on puu, jossa on $n$ solmua. Hän oppi alueen tiivistystekniikan (domain compression), joka toimii seuraavasti:

• Ensin hän valitsee jonkin solmun $v$, jota ei ole aiemmin poistettu verkosta. Seuraavaksi jokaiselle solmuun $v$ yhteydessä olevalle solmuparille $u < w$ hän lisää suuntaamattoman kaaren $(u, w)$, jos sitä ei vielä ollut verkossa. Tämän jälkeen hän poistaa solmun $v$ verkosta sekä kaikki siihen liittyvät kaaret.

Jokaiselle $k$ ($1 \le k \le n$) hän on kiinnostunut jäljelle jäävien verkkojen kaarien kokonaismäärästä yli kaikkien $\frac{n!}{(n-k)!}$ tavan suorittaa operaatiot. Koska vastaukset voivat olla hyvin suuria, tulosta ne modulo $998\,244\,353$.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($2 \le n \le 10^5$) — puun solmujen lukumäärän.

Seuraavat $n - 1$ riviä sisältävät kokonaislukupareja $u_i, v_i$ ($1 \le u_i, v_i \le n$) — puun kaarien kuvauksen.

Tuloste

Tulosta $n$ kokonaislukua — kaarien kokonaismäärä kullekin $k$ modulo $998\,244\,353$.

Esimerkit

Syöte 1

5
1 2
2 3
3 5
3 4

Tuloste 1

16 44 60 0 0

Syöte 2

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

Tuloste 2

51 316 1596 6120 15720 20160 0 0