Gojo は $n$ 頂点の木を持っています。彼は領域圧縮（domain compression）という技法を習得しました。これは次のように動作します。

• まず、それまでにグラフから削除されていない頂点 $v$ を 1 つ選ぶ。次に、$v$ に接続されている頂点の組 $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