E. OneZeroTree
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It's Christmas time! You and your friends love Christmas, and you decide to go to see the Christmas Tree from your city fair. With this opportunity, you want to show off to your friends your programming skills.

The Christmas Tree can be represented as a Tree with $$$1 \leq N \leq 10^5$$$ vertices indexed from $$$1$$$ to $$$N$$$ (a connected graph with $$$N$$$ vertices and $$$N-1$$$ edges). Each node can be turned on or turned off. A configuration is defined as a simple path from vertex $$$x$$$ to vertex $$$y$$$ ($$$x \leq y$$$) in which every vertex can be turned on or off. Two configurations are different if their associated paths are different or if there is at least one vertex that has different states in the two configurations (i.e., it is turned on in one configuration and turned off in the other one). The cost of a configuration is the number of vertices that are turned on.

For each $$$k$$$ from $$$0$$$ to $$$N$$$, you need to find out the number of configurations of cost equal to $$$k$$$. Because this number can be very large, you need to compute it modulo $$$998244353$$$.

Input

The first line of the input will contain the number $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of vertices of the Tree. The following $$$N-1$$$ lines will contain two numbers $$$x_i$$$ ($$$1 \leq x_i \leq N$$$) and $$$y_i$$$ ($$$1 \leq y_i \leq N$$$) each, representing an edge between $$$x_i$$$ and $$$y_i$$$.

Output

You should output one line consisting of $$$N+1$$$ numbers, representing the answer for each $$$k$$$ from $$$0$$$ to $$$N$$$, in this order.

Example
Input
4
1 2
2 3
2 4
Output
10 19 12 3 0
Note

For k = 2 :

the path from 1 to 1 has 0 ways of turning on 2 vertices

the path from 2 to 2 has 0 ways of turning on 2 vertices

the path from 3 to 3 has 0 ways of turning on 2 vertices

the path from 4 to 4 has 0 ways of turning on 2 vertices

the path from 1 to 2 has 1 way of turning on 2 vertices

the path from 1 to 3 has 3 ways of turning on 2 vertices

the path from 1 to 4 has 3 ways of turning on 2 vertices

the path from 2 to 3 has 1 way of turning on 2 vertices

the path from 2 to 4 has 1 way of turning on 2 vertices

the path from 3 to 4 has 3 ways of turning on 2 vertices

In total there are 12 configurations with cost 2.