Gojo 有一樖有 $n$ 個頂點嘅樹。佢學識咗領域壓縮（domain compression）技術，運作方式如下：

• 首先，佢揀一個之前未喺圖入面刪走嘅頂點 $v$。跟住，對於同 $v$ 相連嘅每一對頂點 $u < w$，如果圖入面之前冇無向邊 $(u, w)$，佢就加一條無向邊 $(u, w)$。之後，佢將頂點 $v$ 連埋所有同佢相連嘅邊由圖入面擦走。

對於每個 $k$（$1 \le k \le n$），佢想知道喺全部 $\frac{n!}{(n-k)!}$ 種做操作嘅方式入面，剩低嘅圖嘅邊數總和。因為答案可能好大，請將佢哋對 $998\,244\,353$ 取模之後輸出。

輸入格式

第一行包含一個整數 $n$（$2 \le n \le 10^5$）—— 樹入面頂點嘅數量。

接住落嚟嘅 $n - 1$ 行包含一對對整數 $u_i, v_i$（$1 \le u_i, v_i \le n$）—— 樹入面邊嘅描述。

輸出格式

輸出 $n$ 個整數 —— 每個 $k$ 嘅邊數總和對 $998\,244\,353$ 取模之後嘅結果。

範例

輸入 1

5
1 2
2 3
3 5
3 4

輸出 1

16 44 60 0 0

輸入 2

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

輸出 2

51 316 1596 6120 15720 20160 0 0