{"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\u003eSloth is bad, mkay? So we decided to prepare a problem to punish lazy guys.\u003c/p\u003e\u003cp\u003eYou are given a tree, you should count the number of ways to remove an edge from it and then add an edge to it such that the final graph is a tree and has a perfect matching. Two ways of this operation are considered different if their removed edges or their added edges aren\u0027t the same. The removed edge and the added edge can be equal.\u003c/p\u003e\u003cp\u003eA perfect matching is a subset of edges such that each vertex is an endpoint of exactly one of these edges.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 5·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the number of vertices.\u003c/p\u003e\u003cp\u003eEach of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e lines contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e)\u0026nbsp;— the endpoints of one edge. It\u0027s guaranteed that the graph is a tree.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput a single integer\u0026nbsp;— the answer to the problem.\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\u003e4\n1 2\n2 3\n3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\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\u003e5\n1 2\n2 3\n3 4\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\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\u003e8\n1 2\n2 3\n3 4\n1 5\n5 6\n6 7\n1 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e22\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\u003eIn first sample, there are \u003cspan class\u003d\"tex-span\"\u003e8\u003c/span\u003e ways:\u003c/p\u003e\u003cul\u003e \u003cli\u003e edge between \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e turns to edge between \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e edge between \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e turns to edge between \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e edge between \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e turns to edge between \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e edge between \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e turns to edge between \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e edge between \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e turns to edge between \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e edge between \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e turns to edge between \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e edge between \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e turns to edge between \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e edge between \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e turns to edge between \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e. \u003cul\u003e\u003c/ul\u003e\u003c/li\u003e\u003c/ul\u003e"}}]}