B. Lowest Common Ancestor
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Malzahar loves the trees. One day, He found a tree with $$$n$$$ vertices rooted in $$$1$$$ in SYSU.

He wants to know the expectations of the depth of the LCA if he chooses $$$k$$$ different vertices randomly for all $$$k$$$ in $$$\{1,2,\cdots, n\}$$$.

Noted that:

  • A tree is an undirected connected graph with $$$n$$$ vertices and $$$n-1$$$ edges.
  • The depth of a vertex $$$x$$$ is defined as the number of vertices in the shortest path from $$$x$$$ to $$$1$$$.
  • A vertex $$$y$$$ is $$$x$$$'s ancestor if and only if $$$y$$$ is in the shortest path from $$$x$$$ to $$$1$$$.
  • The lowest common ancestor(LCA) of some vertices $$$x_1,x_2,\cdots,x_k(k\geq 1)$$$ is a vertex $$$z$$$ such that the depth of $$$z$$$ is largest and $$$z$$$ is all the ancestors of $$$x_1,x_2,\cdots,x_k$$$ in the tree.

Since the answer may be large, print it after modulo $$$998244353$$$.

It can be shown that the expectation can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q\not \equiv 0 \pmod {998244353}$$$. You should output the integer equal to $$$p\times q^{-1} \bmod {998244353}$$$. In other words, output such an integer $$$x$$$ that $$$0\le x \lt 998244353$$$ and $$$x\cdot q \equiv p \pmod {998244353}$$$.

Input

The first line contains two integers $$$n$$$ ($$$1\le n \le 5\times 10^5$$$) - the number of vertices of the tree.

The second line to the $$$n$$$-th line, each line contains two integers $$$x,y$$$ ($$$1\le x,y\le n,x\neq y$$$), denoting an edge in the tree.

Output

Output $$$n$$$ integers and the $$$k$$$-th integer denotes the expectation (modulling $$$998244353$$$) of the depth of the LCA if Malzahar chooses $$$k$$$ different vertices randomly.

Examples
Input
7
1 2
1 3
4 5
5 6
1 4
4 7
Output
570425347 332748119 484861544 370776475 1 1 1
Input
4
1 2
1 3
3 4
Output
2 166374060 1 1