Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Tree Elimination

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputVasya has a tree with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, and $$$n - 1$$$ edges numbered from $$$1$$$ to $$$n - 1$$$. Initially each vertex contains a token with the number of the vertex written on it.

Vasya plays a game. He considers all edges of the tree by increasing of their indices. For every edge he acts as follows:

- If both endpoints of the edge contain a token, remove a token from one of the endpoints and write down its number.
- Otherwise, do nothing.

The result of the game is the sequence of numbers Vasya has written down. Note that there may be many possible resulting sequences depending on the choice of endpoints when tokens are removed.

Vasya has played for such a long time that he thinks he exhausted all possible resulting sequences he can obtain. He wants you to verify him by computing the number of distinct sequences modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of vertices of the tree.

The next $$$n - 1$$$ lines describe edges of the tree. The $$$i$$$-th of these lines contains two integers $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — endpoints of the edge with index $$$i$$$. It is guaranteed that the given graph is indeed a tree.

Output

Print a single integer — the number of distinct sequences modulo $$$998\,244\,353$$$.

Examples

Input

5 1 2 1 3 1 4 1 5

Output

5

Input

7 7 2 7 6 1 2 7 5 4 7 3 5

Output

10

Note

In the first sample case the distinct sequences are $$$(1), (2, 1), (2, 3, 1), (2, 3, 4, 1), (2, 3, 4, 5)$$$.

Int the second sample case the distinct sequences are $$$(2, 6, 5, 3), (2, 6, 5, 7), (2, 6, 7, 2), (2, 6, 7, 5), (2, 7, 3), (2, 7, 5), (7, 1, 3), (7, 1, 5), (7, 2, 3), (7, 2, 5)$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/05/2020 04:56:38 (i3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|