{"problem":{"name":"Tree Vertices XOR","description":{"content":"You are given a tree with $N$ vertices. The vertices are numbered from $1$ to $N$, and the $i$\\-th edge connects vertices $u_i$ and $v_i$. Initially, on each vertex of the tree is written number $1$. ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc052_f"},"statements":[{"statement_type":"Markdown","content":"You are given a tree with $N$ vertices. The vertices are numbered from $1$ to $N$, and the $i$\\-th edge connects vertices $u_i$ and $v_i$.\nInitially, on each vertex of the tree is written number $1$.\nIn one operation, you can do the following:\n\n*   Choose any vertex $v$ of the tree. Let $X$ be the **XOR** of the values written in the neighbors of $v$. Then, if the number written on $v$ is $a_v$, replace it by $(a_v\\ \\mathrm{XOR}\\ X)$.\n\nYou can perform this operation any finite (maybe zero) number of times. How many configurations can you achieve? As this number can be large, output it modulo $998244353$.\nTwo configurations are called different if there exists a vertex $v$, such that the numbers written in $v$ in these configurations are different.\n\n## Constraints\n\n*   $3 \\le N \\le 2\\cdot 10^5$\n*   $1\\le u_i, v_i \\le N$\n*   $u_i \\neq v_i$\n*   The input represents a valid tree.\n\n## Input\n\nInput 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":"agc052_f","tags":[],"sample_group":[["4\n1 2\n2 3\n3 4","10\n\nWe can get the following configurations ($abcd$ means vertices $1,2,3,4$ have $a,b,c,d$ written on them): $1111$, $1110$, $1100$, $1000$, $0111$, $0110$, $0100$, $0011$, $0010$, $0001$."],["5\n1 2\n1 3\n1 4\n1 5","24"],["6\n1 3\n2 3\n3 4\n4 5\n4 6","40"],["9\n1 2\n2 3\n1 4\n4 5\n1 6\n6 7\n7 8\n8 9","255"]],"created_at":"2026-03-03 11:01:14"}}