26472번 - Tree Automorphism 다국어

There is an undirected tree named $T$ with $N$ vertices numbered $1$ to $N$. The edge between vertices $u$ and $v$ in $T$ is denoted by $\{u, v\}$.

Consider $P = (p_1, p_2, \dots , p_N)$ as a permutation of $(1, 2, \dots , N)$. Among the $N!$ possible permutations, compute the number of $P$s which satisfy the condition below.

• If $T$ has an edge $\{u, v\}$, then also has an edge $\{p_u, p_v\}$.

Since the answer may be very large, print the answer modulo $998\,244\,353$.

The input consists of a single test case of the following format.

$N$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_{N-1}$ $v_{N-1}$

The first line consists of an integer $N$ between $1$ and $100\,000$. This represents the number of vertices in the tree $T$.

The $i$-th of the following $N-1$ lines consists of two integers between $1$ and $N$. This represents that there is an edge $\{u_i, v_i\}$ in the tree $T$.

It is guaranteed that the given graph is a tree.

Output the answer modulo $998\,244\,353$ in a line.