34266번 - Circle of Leaf 다국어

문제

Your friend has given you a rooted tree: a connected graph with $N$ nodes and $N-1$ edges. The nodes of the tree are numbered from 1ドル$ to $N,ドル with node 1ドル$ being the root of the tree and other nodes numbered arbitrarily.

However, you recently learned about the Ouroboros, an ancient mythical snake that eats its own tail, signifying a cycle with no beginning and end. You dislike the fact that the tree you were given has a very clear beginning at the root, and clear ends at its leaves, so you decide to completely change the structure of this tree into a new graph which you have named an Ouroboros Graph.

To construct this Ouroboros Graph, you take the leaves of the tree (the nodes with no direct children) and draw special "leaf" edges that connect every leaf directly to the root. If there is already an edge connecting a leaf to the root, you still add a duplicate edge.

With this special graph structure, you can now create lots of different trees by removing some subset of edges, and in the spirit of Ouroboros, the leaves and roots can change depending on which subset of edges you remove. How many different trees can you make by removing a subset of edges from the Ouroboros Graph? Two trees are considered different if one tree has an edge that the other tree does not. (If both a regular and a "leaf" edge connect the same pair of nodes, then they are distinguishable from each other and are considered different edges.) Since the number of trees can be large, compute the answer modulo 998ドル,244円,353円$.

입력

The first line of input contains a single integer $N$ (2ドル \leq N \leq 200,000円$), the number of nodes in the tree.

Each of the next $N-1$ lines contains two space separated integers $a$ and $b$ (1ドル \leq a,b \leq N$) specifying that an edge exists between parent node $a$ and child node $b$ in the tree. The input graph is indeed guaranteed to be a tree: there is a unique path of edges between every pair of nodes in the graph.

출력

Print the number of different trees modulo 998ドル,244円,353円$ that can be created by removing some subset of edges from the input tree's Ouroboros Graph.

제한

힌트