{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eEric is the teacher of graph theory class. Today, Eric teaches independent set and edge-induced subgraph.\u003c/p\u003e\u003cp\u003eGiven a graph $$$G\u003d(V,E)$$$, an \u003cspan class\u003d\"tex-font-style-it\"\u003eindependent set\u003c/span\u003e is a subset of vertices $$$V\u0027 \\subset V$$$ such that for every pair $$$u,v \\in V\u0027$$$, $$$(u,v) \\not \\in E$$$ (i.e. no edge in $$$E$$$ connects two vertices from $$$V\u0027$$$).\u003c/p\u003e\u003cp\u003eAn \u003cspan class\u003d\"tex-font-style-it\"\u003eedge-induced subgraph\u003c/span\u003e consists of a subset of edges $$$E\u0027 \\subset E$$$ and all the vertices in the original graph that are incident on at least one edge in the subgraph.\u003c/p\u003e\u003cp\u003eGiven $$$E\u0027 \\subset E$$$, denote $$$G[E\u0027]$$$ the edge-induced subgraph such that $$$E\u0027$$$ is the edge set of the subgraph. Here is an illustration of those definitions:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/fe5e5c0a700ba454a93057cbf68f82c7?v\u003d1715828505\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eIn order to help his students get familiar with those definitions, he leaves the following problem as an exercise:\u003c/p\u003e\u003cp\u003eGiven a tree $$$G\u003d(V,E)$$$, calculate the sum of $$$w(H)$$$ over all except null edge-induced subgraph $$$H$$$ of $$$G$$$, where $$$w(H)$$$ is the number of independent sets in $$$H$$$. Formally, calculate $$$\\sum \\limits_{\\emptyset \\not\u003d E\u0027 \\subset E} w(G[E\u0027])$$$.\u003c/p\u003e\u003cp\u003eShow Eric that you are smarter than his students by providing the correct answer as quickly as possible. Note that the answer might be large, you should output the answer modulo $$$998,244,353$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$n$$$ ($$$2 \\le n \\le 3 \\cdot 10^5$$$), representing the number of vertices of the graph $$$G$$$.\u003c/p\u003e\u003cp\u003eEach of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \\le u,v \\le n$$$, $$$u \\not\u003d v$$$), describing edges of the given tree.\u003c/p\u003e\u003cp\u003eIt is guaranteed that the given edges form a tree.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one integer, representing the desired value modulo $$$998,244,353$$$.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 2\n3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eFor the second example, all independent sets are listed below.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/6b9f5c1e822e9a3ee54e3566bffe2b12?v\u003d1715828505\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}