{"problem":{"name":"Deterministic Placing","description":{"content":"We have a tree with $N$ vertices, numbered $1, \\ldots, N$. For each $i=1,\\ldots,N-1$, the $i$\\-th edge connects Vertex $a_i$ and Vertex $b_i$.   An operation on this tree when at most one piece is put","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc142_d"},"statements":[{"statement_type":"Markdown","content":"We have a tree with $N$ vertices, numbered $1, \\ldots, N$. For each $i=1,\\ldots,N-1$, the $i$\\-th edge connects Vertex $a_i$ and Vertex $b_i$.  \nAn operation on this tree when at most one piece is put on each vertex is defined as follows.\n\n*   Simultaneously move every piece to one of the vertices adjacent to the one occupied by the piece.\n\nAn operation is said to be **good** when the conditions below are satisfied.\n\n*   Each edge is traversed by at most one piece.\n*   Each vertex will be occupied by at most one piece after the operation.\n\nTakahashi will put a piece on one or more vertices of his choice. Among the $2^N-1$ ways to put pieces, find the number of ones that satisfy the condition below, modulo $998244353$.\n\n*   For every non-negative integer $K$, the following holds.\n    *   It is possible to perform a good operation $K$ times.\n    *   Let $S_K$ be the set of vertices occupied by pieces just after $K$ good operations. Then, $S_K$ is unique.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq a_i \\lt b_i \\leq N$\n*   The given graph is a tree.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$\\vdots$\n$a_{N-1}$ $b_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc142_d","tags":[],"sample_group":[["3\n1 2\n1 3","2\n\nHere are the two ways to satisfy the condition.\n\n*   Put a piece on Vertex $1$ and Vertex $2$.\n*   Put a piece on Vertex $1$ and Vertex $3$.\n\nNote that he must put a piece on at least one vertex."],["7\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7","0\n\nThere might be no way to satisfy the condition."],["19\n9 14\n2 13\n1 3\n17 19\n13 18\n12 19\n4 5\n2 10\n4 9\n8 11\n3 15\n6 8\n8 10\n6 19\n9 13\n11 15\n7 17\n16 17","100"]],"created_at":"2026-03-03 11:01:14"}}