Problem Statement

You are given a tree with N vertices. The vertices are numbered 1 through N, and the i-th edge connects vertex a_i and vertex b_i.
Solve the following problem for each $x=1,2,\ldots,N$:

• There are (2^N-1) non-empty subsets V of the tree's vertices. Find the number, modulo 998244353, of such V that the subgraph induced by V has exactly x connected components.

What is an induced subgraph?
Let S be the subset of the vertices of a graph G; then the subgraph of G induced by S is a graph whose vertex set is S and whose edge set consists of all edges of G whose both ends are contained in S.

Input

The input is given from Standard Input in the following format:
N
a_1 b_1
$\vdots$
a_{N-1} b_{N-1}

Output

Print N lines.
The i-th line should contain the answer for x=i.

Constraints

• $1 \leq N \leq 5000$
• $1 \leq a_i \lt b_i \leq N$
• The given graph is a tree.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

10
5
0
0

The induced subgraph will have two connected components in the following five cases and one in the others.

• V = {1,2,4}
• V = {1,3}
• V = {1,3,4}
• V = {1,4}
• V = {2,4}

Sample Input 2

2
1 2

Sample Output 2

3
0

Sample Input 3

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

Sample Output 3

140
281
352
195
52
3
0
0
0
0

见题面 Input 部分

见题面 Output 部分