题目描述

高桥君有一天从青木君那里得到了如下问题。

• 给定一棵有 $N$ 个顶点的树和一个整数 $K$。树的顶点编号为 $1,2,\ldots,N$，每条边用 $(a_i, b_i)$ 表示。
• 对于顶点集合 $S$，定义 $f(S)$ 为包含 $S$ 的所有顶点的最小连通子树的顶点数。
• 从树中选择 $K$ 个顶点的方法有 $_N C_K$ 种。对于每种选择，将选中的顶点集合记为 $S$，求所有 $f(S)$ 的总和。
• 答案可能很大，请输出对 $924844033$（素数）取模的结果。

对高桥君来说，这个问题太简单了。因此，他决定对于 $K=1,2,\ldots,N$ 的所有情况都解答这个问题。

输入格式

输入通过标准输入给出，格式如下：

$N$ $a_1$ $b_1$ $a_2$ $b_2$ : $a_{N-1}$ $b_{N-1}$

输出格式

输出 $N$ 行。第 $i$ 行输出 $K=i$ 时问题的答案对 $924844033$ 取模的结果。

样例 1

输入

3
1 2
2 3

输出

3
7
3

样例 2

输入

4
1 2
1 3
1 4

输出

4
15
13
4

样例 3

输入

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

输出

7
67
150
179
122
45
7

说明/提示

限制条件

• $2 \leq N \leq 200,\!000$
• $1 \leq a_i, b_i \leq N$
• 给定的图为一棵树

样例解释 1

上图展示了 $K=2$ 的情况。粉色的顶点为选中的顶点，被红色圈出的部分为包含这些顶点的最小连通子树。

由 ChatGPT 4.1 翻译