{"problem":{"name":"Swap on Tree","description":{"content":"There is a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge connects vertices $u_i$ and $v_i$.   Additionally, there are $N$ pieces numbered $1$ to $N$. Initially, piece $i$ is placed on v","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc171_c"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc171_c","tags":[],"sample_group":[["3\n1 2\n2 3","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)$"],["5\n2 5\n3 4\n1 3\n1 5","34"],["8\n4 5\n2 5\n3 6\n1 3\n1 8\n2 7\n2 8","799"]],"created_at":"2026-03-03 11:01:13"}}