G. Edge Groups
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an undirected connected graph of $$$n$$$ vertices and $$$n-1$$$ edges, where $$$n$$$ is guaranteed to be odd. You want to divide all the $$$n-1$$$ edges to $$$\frac{n-1}{2}$$$ groups under following constraints:

  • There are exactly 2 edges in each group
  • The 2 edges in the same group share a common vertex

Determine the number of valid dividing schemes modulo $$$998244353$$$. Two schemes are considered different if there are 2 edges that are in the same group in one scheme but not in the same group in the other scheme.

Input

The first line contains one integer $$$n\,(3\le n \le 10^5)$$$, denoting the number of vertices.

Following $$$n-1$$$ lines each contains two integers $$$u,v\,(1 \le u \lt v \le n)$$$, denoting that vertex $$$u,v$$$ are undirectedly connected by an edge.

It is guaranteed that $$$n$$$ is odd and that the given graph is connected.

Output

Output one line containing one integer, denoting the number of valid dividing schemes modulo $$$998244353$$$.

Example
Input
7
1 2
1 3
1 7
4 7
5 7
6 7
Output
3
Note

The 3 schemes are:

  • The 3 edge groups are $$$\{1\leftrightarrow 2, 1\leftrightarrow 3\}, \{1\leftrightarrow 7, 4\leftrightarrow 7\}, \{5\leftrightarrow 7, 6\leftrightarrow 7\}$$$
  • The 3 edge groups are $$$\{1\leftrightarrow 2, 1\leftrightarrow 3\}, \{1\leftrightarrow 7, 5\leftrightarrow 7\}, \{4\leftrightarrow 7, 6\leftrightarrow 7\}$$$
  • The 3 edge groups are $$$\{1\leftrightarrow 2, 1\leftrightarrow 3\}, \{1\leftrightarrow 7, 6\leftrightarrow 7\}, \{4\leftrightarrow 7, 5\leftrightarrow 7\}$$$