H. Guide Map
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Byteland has $$$n$$$ cities, and there is a bidirectional road between any two cities. There are exactly $$$(n-2)$$$ roads with scenery, and if properly built scenery on one more road, one can always travel from one city to the others only through roads with scenery.

Little Q is initially located in the city $$$1$$$ with a guide map in his hand, showing some of the roads in Byteland, and starts his journey in Byteland. Assuming he is currently in the city $$$u$$$:

  • If he can walk along a road on the guide map to a city $$$v$$$ that he has not yet visited, he will choose the smallest such $$$v$$$ and walk along the road to city $$$v$$$. Note that city $$$1$$$ is visited initially;
  • Otherwise, he will return along the road he took to reach city $$$u$$$ for the first time, unless he is already in city $$$1$$$, in which case the journey ends immediately.

Little Q wants to visit all the sceneries while traveling on no more than one different road without sceneries. You need to help him calculate how many different guide maps can satisfy his requirements. Two guide maps are considered different if and only if there is a road on one map that does not appear on the other.

Since the answer may be large, output it modulo $$$998\,244\,353$$$.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \times 10^5$$$), indicating the number of cities.

Then $$$(n-2)$$$ lines follow, the $$$i$$$-th of which contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), indicating that the $$$i$$$-th scenery is on the road between the $$$u$$$-th and the $$$v$$$-th cities. It is guaranteed that if properly built scenery on one more road, one can always travel from one city to the others only through roads with scenery.

Output

Output a line containing an integer, indicating the number of different guide maps modulo $$$998\,244\,353$$$.

Examples
Input
4
1 4
2 3
Output
6
Input
2
Output
2
Note

For the first sample case, one of the feasible guide maps shows $$$4$$$ roads $$$(1,4)$$$, $$$(2,3)$$$, $$$(1,2)$$$, and $$$(1,3)$$$. Little Q will visit the cities $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 1$$$ in order following this guide map and visit the sceneries on roads $$$(1,4)$$$ and $$$(2,3)$$$ while traveling on only one road $$$(1,2)$$$ without sceneries.

For the second sample case, there is no road with scenery, and thus a feasible guide map can not only include but also exclude the only existing road $$$(1,2)$$$.