{"raw_statement":[{"iden":"problem statement","content":"Given is a tree with $N$ vertices numbered $1$ through $N$.\nThe $i$\\-th edge connects Vertices $a_i$ and $b_i$.\nSnuke will label each vertex with `0` or `1` and each edge with `AND` or `OR`. Among the $2^{2N-1}$ ways to label the vertices and edges, find the number of ways that satisfy the following condition, modulo $998244353$.\nCondition: There exists a sequence of $N-1$ operations ending up with one vertex labeled `1`, where each operation consists of the steps below.\n\n*   Choose one edge and contract it. Here, let $x$ and $y$ be the labels of the erased vertices and $\\mathrm{op}$ be the label of the erased edge.\n*   If $\\mathrm{op}$ is `AND`, label the new vertex with $\\mathrm{AND}(x,y)$; if $\\mathrm{op}$ is `OR`, label the new vertex with $\\mathrm{OR}(x,y)$."},{"iden":"notes","content":"*   The operation $\\mathrm{AND}$ is defined as follows: $\\mathrm{AND}(0,0)=(0,1)=(1,0)=0,\\mathrm{AND}(1,1)=1$.\n*   The operation $\\mathrm{OR}$ is defined as follows: $\\mathrm{OR}(1,1)=(0,1)=(1,0)=1,\\mathrm{OR}(0,0)=0$.\n*   When contracting the edge connecting Vertex $s$ and Vertex $t$, we merge the two vertices while removing that edge. After the contraction, there is an edge connecting the new vertex and vertex $u$ if and only if there was an edge connecting $s$ and $u$ or connecting $t$ and $u$ before the contraction."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $2 \\leq N \\leq 10^{5}$\n*   $1 \\leq a_i, b_i \\leq N$\n*   The given graph is a tree."},{"iden":"input","content":"Input 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}$"},{"iden":"sample input 1","content":"2\n1 2"},{"iden":"sample output 1","content":"4"},{"iden":"sample input 2","content":"20\n7 3\n20 18\n16 12\n7 2\n10 5\n18 16\n16 3\n4 11\n7 15\n8 1\n6 1\n12 13\n15 5\n19 17\n7 1\n9 8\n7 17\n16 14\n11 7"},{"iden":"sample output 2","content":"283374562\n\n*   Remember to print the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}