{"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\u003eLittle boy Igor wants to become a traveller. At first, he decided to visit all the cities of his motherland\u0026nbsp;— Uzhlyandia.\u003c/p\u003e\u003cp\u003eIt is widely known that Uzhlyandia has \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e cities connected with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e bidirectional roads. Also, there are no two roads in the country that connect the same pair of cities, but roads starting and ending in the same city can exist. Igor wants to plan his journey beforehand. Boy thinks a path is \u003cspan class\u003d\"tex-font-style-it\"\u003egood\u003c/span\u003e if the path goes over \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e - 2\u003c/span\u003e roads twice, and over the other \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e exactly once. The good path can start and finish in any city of Uzhlyandia.\u003c/p\u003e\u003cp\u003eNow he wants to know how many different good paths are in Uzhlyandia. Two paths are considered different if the sets of roads the paths goes over exactly once differ. Help Igor\u0026nbsp;— calculate the number of good paths.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e)\u003c/span\u003e\u0026nbsp;— the number of cities and roads in Uzhlyandia, respectively.\u003c/p\u003e\u003cp\u003eEach of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) that mean that there is road between cities \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIt is guaranteed that no road will be given in the input twice. That also means that for every city there is no more than one road that connects the city to itself.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint out the only integer\u0026nbsp;— the number of good paths in Uzhlyandia.\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\u003e5 4\n1 2\n1 3\n1 4\n1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\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 3\n1 2\n2 3\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\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\u003e2 2\n1 1\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\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 test case the good paths are: \u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2 → 1 → 3 → 1 → 4 → 1 → 5\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2 → 1 → 3 → 1 → 5 → 1 → 4\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2 → 1 → 4 → 1 → 5 → 1 → 3\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e3 → 1 → 2 → 1 → 4 → 1 → 5\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e3 → 1 → 2 → 1 → 5 → 1 → 4\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e4 → 1 → 2 → 1 → 3 → 1 → 5\u003c/span\u003e. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThere are good paths that are same with displayed above, because the sets of roads they pass over once are same: \u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2 → 1 → 4 → 1 → 3 → 1 → 5\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2 → 1 → 5 → 1 → 3 → 1 → 4\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2 → 1 → 5 → 1 → 4 → 1 → 3\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e3 → 1 → 4 → 1 → 2 → 1 → 5\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e3 → 1 → 5 → 1 → 2 → 1 → 4\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e4 → 1 → 3 → 1 → 2 → 1 → 5\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e and all the paths in the other direction. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThus, the answer is \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second test case, Igor simply can not walk by all the roads.\u003c/p\u003e\u003cp\u003eIn the third case, Igor walks once over every road.\u003c/p\u003e"}}]}