{"problem":{"name":"Zigzag Tree","description":{"content":"Given is a tree with $N$ vertices. The vertices are numbered $1$ to $N$, and the $i$\\-th edge connects Vertices $a_i$ and $b_i$. Find the number of sequences of positive integers $P = (P_1, P_2, \\ldot","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc130_d"},"statements":[{"statement_type":"Markdown","content":"Given is a tree with $N$ vertices. The vertices are numbered $1$ to $N$, and the $i$\\-th edge connects Vertices $a_i$ and $b_i$.\nFind the number of sequences of positive integers $P = (P_1, P_2, \\ldots, P_N)$ that satisfy the conditions below, modulo $998244353$.\n\n*   $1\\leq P_i\\leq N$\n*   $P_i\\neq P_j$ if $i\\neq j$.\n*   For $1\\leq a, b, c\\leq N$, if Vertices $a$ and $b$ are adjacent, and Vertices $b$ and $c$ are also adjacent, $P_a < P_b > P_c$ or $P_a > P_b < P_c$ holds.\n\n## Constraints\n\n*   $2\\leq N\\leq 3000$\n*   $1\\leq a_i, b_i\\leq N$\n*   The given graph is a tree.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$\\vdots$\n$a_{N-1}$ $b_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc130_d","tags":[],"sample_group":[["3\n1 2\n2 3","4\n\nThe $4$ sequences satisfying the conditions are:\n\n*   $P = (1, 3, 2)$\n*   $P = (2, 1, 3)$\n*   $P = (2, 3, 1)$\n*   $P = (3, 1, 2)$"],["4\n1 2\n1 3\n1 4","12"],["6\n1 2\n2 3\n3 4\n4 5\n5 6","122"],["9\n8 5\n9 8\n1 9\n2 5\n6 1\n7 6\n3 8\n4 1","19080"]],"created_at":"2026-03-03 11:01:13"}}