409142: GYM103446 G Edge Groups

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.

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 < 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 one line containing one integer, denoting the number of valid dividing schemes modulo $$$998244353$$$.

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

3

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\}$$$