A14703. Tree Coloring

You are given a rooted tree consisting of $n$ vertices numbered from $1$ to $n$ . The root of the tree is the vertex $1$ .

You have to color all vertices of the tree into $n$ colors (also numbered from $1$ to $n$ ) so that there is exactly one vertex for each color. Let $c_i$ be the color of vertex $i$ , and $p_i$ be the parent of vertex $i$ in the rooted tree. The coloring is considered beautiful if there is no vertex $k$ ( $k > 1$ ) such that $c_k = c_{p_k} - 1$ , i. e. no vertex such that its color is less than the color of its parent by exactly $1$ .

Calculate the number of beautiful colorings, and print it modulo $998244353$ .

The first line contains one integer $n$ ( $2 \le n \le 250000$ ) — the number of vertices in the tree.

Then $n-1$ lines follow, the $i$ -th line contains two integers $x_i$ and $y_i$ ( $1 \le x_i, y_i \le n$ ; $x_i \ne y_i$ ) denoting an edge between the vertex $x_i$ and the vertex $y_i$ . These edges form a tree.

Print one integer — the number of beautiful colorings, taken modulo $998244353$ .