Score : 1100 points
We have a tree G with N vertices numbered 1 to N. The i-th edge of G connects Vertex a_i and Vertex b_i.
Consider adding zero or more edges in G, and let H be the graph resulted.
Find the number of graphs H that satisfy the following conditions, modulo 998244353.
Input is given from Standard Input in the following format:
N a_1 b_1 \vdots a_{N-1} b_{N-1}
Print the answer.
6 1 6 2 1 5 2 3 4 2 3
3
For example, adding the edges (1, 5), (3, 5) in G satisfies the conditions.
3 1 2 2 3
1
The only graph H that satisfies the conditions is G.
9 1 2 2 3 4 2 1 7 6 1 2 5 5 9 6 8
27
19 2 4 15 8 1 16 1 3 12 19 1 18 7 11 11 15 12 9 1 6 7 14 18 2 13 12 13 5 16 13 7 1 11 10 7 17
78732