{"raw_statement":[{"iden":"problem statement","content":"There is a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge connects vertices $u_i$ and $v_i$.  \nAdditionally, there are $N$ pieces numbered $1$ to $N$. Initially, piece $i$ is placed on vertex $i$.  \nYou can perform the following operation any number of times, possibly zero:\n\n*   Choose one edge. Let vertices $u$ and $v$ be the endpoints of the edge, and swap the pieces on vertices $u$ and $v$. Then, delete the chosen edge.\n\nLet $a_i$ be the piece on vertex $i$. How many different possible sequences $(a_1, a_2, \\dots, a_N)$ exist when you finish performing the operation? Find the count modulo $998244353$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 3000$\n*   $1 \\leq u_i \\lt v_i \\leq N$\n*   The graph given in the input is a tree."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$"},{"iden":"sample input 1","content":"3\n1 2\n2 3"},{"iden":"sample output 1","content":"5\n\nFor example, the sequence $(a_1, a_2, a_3) = (2, 1, 3)$ can be obtained by the following steps:\n\n*   Choose the first edge, swap the pieces on vertices $1$ and $2$, and delete the edge. This results in $(a_1, a_2, a_3) = (2, 1, 3)$.\n*   Finish operating.\n\nAlso, the sequence $(a_1, a_2, a_3) = (3, 1, 2)$ can be obtained by the following steps:\n\n*   Choose the second edge, swap the pieces on vertices $2$ and $3$, and delete the edge. This results in $(a_1, a_2, a_3) = (1, 3, 2)$.\n*   Choose the first edge, swap the pieces on vertices $1$ and $2$, and delete the edge. This results in $(a_1, a_2, a_3) = (3, 1, 2)$.\n*   Finish operating.\n\nThe operation can yield the following five sequences:\n\n*   $(1, 2, 3)$\n*   $(1, 3, 2)$\n*   $(2, 1, 3)$\n*   $(2, 3, 1)$\n*   $(3, 1, 2)$"},{"iden":"sample input 2","content":"5\n2 5\n3 4\n1 3\n1 5"},{"iden":"sample output 2","content":"34"},{"iden":"sample input 3","content":"8\n4 5\n2 5\n3 6\n1 3\n1 8\n2 7\n2 8"},{"iden":"sample output 3","content":"799"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}