{"problem":{"name":"Shrink the Tree","description":{"content":"You are given a tree $T$ with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge connects vertices $A_i$ and $B_i$. You can perform the following operation any number of times, possibly zero. *   Cho","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"wtf22_day1_c"},"statements":[{"statement_type":"Markdown","content":"You are given a tree $T$ with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge connects vertices $A_i$ and $B_i$.\nYou can perform the following operation any number of times, possibly zero.\n\n*   Choose two leaves $u$ and $v$ of $T$ such that the distance between them is odd. Then, remove $u$ and $v$ from $T$ (along with the incident edges).\n\nHere, a vertex is said to be a leaf when its degree is exactly one at the time of the operation. The distance between two vertices is the number of edges in the path connecting those vertices.\nFind the number, modulo $998244353$, of sets that can be the vertex set of $T$ after your operations.\n\n## Constraints\n\n*   $2 \\leq N \\leq 150$\n*   $1 \\leq A_i,B_i \\leq N$\n*   The input graph is a tree.\n*   All input values are integers.\n\n## Input\n\nThe input 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":"wtf22_day1_c","tags":[],"sample_group":[["4\n1 2\n2 3\n3 4","3\n\nPerforming zero operations yields the vertex set ${1,2,3,4}$.\nErasing the leaves $1$ and $4$ from $T$ yields the vertex set ${2,3}$.\nFrom this state, erasing the leaves $2$ and $3$ yields the vertex set ${}$."],["5\n2 1\n3 1\n4 1\n5 3","3"],["8\n2 1\n3 2\n4 1\n5 2\n6 5\n7 3\n8 7","11"],["24\n12 7\n14 4\n8 13\n24 13\n1 3\n4 9\n17 2\n1 21\n24 22\n11 1\n15 17\n22 5\n23 10\n24 12\n13 6\n12 16\n10 21\n19 22\n20 17\n4 20\n20 6\n10 18\n21 6","5359"]],"created_at":"2026-03-03 11:01:13"}}