五条悟（Gojo）有一棵含有 $n$ 个节点的树。他学会了“领域压缩”技术，其工作原理如下：

• 首先，他选择一个之前未被从图中删除的节点 $v$。接着，对于与 $v$ 相连的每对节点 $u < w$，如果图中之前不存在无向边 $(u, w)$，则添加一条无向边 $(u, w)$。之后，他将节点 $v$ 连同所有与它相接的边从图中抹去。

对于每个 $k$ ($1 \le k \le n$)，他想知道在所有 $\frac{n!}{(n-k)!}$ 种进行 $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