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