P15721 [JAG 2023 Summer Camp #3] Many-hued Tree

There is a tree with $N$ nodes numbered from $1$ to $N$. For each $i = 1, \ldots, N - 1$, the $i$-th edge connects node $u_i$ and node $v_i$. You are going to paint all nodes in distinct colors. Colors are represented by integers between $1$ and $N$. The assignment of colors on the tree is called good, if it is possible to complete the following operation $N - 1$ times repeatedly. - Select a pair of colors $(A, B)$ which satisfies the following two conditions. - $|A - B| = 1$. - There exists an edge which connects a node painted in color $A$ and a node painted in color $B$. - Change the color of all nodes currently painted in color $A$ to color $B$. Your task is to count the number of good assignments of colors on the tree modulo $998,244,353$.

The input consists of a single test case of the following format. $$ \begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \end{aligned} $$ The first line consists of an integer $N$, which satisfies $1 \leq N \leq 2,000$. Each of the $N - 1$ lines consists of two integers $u_i, v_i$, which satisfies $1 \leq u_i, v_i \leq N$. The given graph is guaranteed to be a tree.

Output in a line the number of assignments of colors on the given tree modulo $998,244,353$.