{"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\u003eIn computer science, there is a method called \"Divide And Conquer By Node\" to solve some hard problems about paths on a tree. Let\u0027s desribe how this method works by function:\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003esolve\u003c/i\u003e(\u003ci\u003et\u003c/i\u003e)\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e is a tree): \u003c/p\u003e\u003col\u003e \u003cli\u003e Chose a node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e (it\u0027s common to chose weight-center) in tree \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e. Let\u0027s call this step \"Line A\". \u003c/li\u003e\u003cli\u003e Deal with all paths that pass \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Then delete \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e from tree \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e After that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e becomes some subtrees. \u003c/li\u003e\u003cli\u003e Apply \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003esolve\u003c/i\u003e\u003c/span\u003e on each subtree. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eThis ends when \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e has only one node because after deleting it, there\u0027s nothing. \u003c/p\u003e\u003cp\u003eNow, WJMZBMR has mistakenly believed that it\u0027s ok to chose any node in \"Line A\". So he\u0027ll chose a node at random. To make the situation worse, he thinks a \"tree\" should have the same number of edges and nodes! So this procedure becomes like that.\u003c/p\u003e\u003cp\u003eLet\u0027s define the variable \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etotalCost\u003c/i\u003e\u003c/span\u003e. Initially the value of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etotalCost\u003c/i\u003e\u003c/span\u003e equal to \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e. So, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003esolve\u003c/i\u003e(\u003ci\u003et\u003c/i\u003e)\u003c/span\u003e (now \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e is a graph): \u003c/p\u003e\u003col\u003e \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etotalCost\u003c/i\u003e \u003d \u003ci\u003etotalCost\u003c/i\u003e + (\u003ci\u003esize\u003c/i\u003e\u0026nbsp;\u003ci\u003eof\u003c/i\u003e\u0026nbsp;\u003ci\u003et\u003c/i\u003e)\u003c/span\u003e. The operation \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e\u003d\u003c/span\u003e\" means assignment. \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003eSize\u003c/i\u003e\u0026nbsp;\u003ci\u003eof\u003c/i\u003e\u0026nbsp;\u003ci\u003et\u003c/i\u003e)\u003c/span\u003e means the number of nodes in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Choose a node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e in graph \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e at random (uniformly among all nodes of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e). \u003c/li\u003e\u003cli\u003e Then delete \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e from graph \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e After that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e becomes some connected components. \u003c/li\u003e\u003cli\u003e Apply \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003esolve\u003c/i\u003e\u003c/span\u003e on each component. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eHe\u0027ll apply \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003esolve\u003c/i\u003e\u003c/span\u003e on a connected graph with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e nodes and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e edges. He thinks it will work quickly, but it\u0027s very slow. So he wants to know the expectation of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etotalCost\u003c/i\u003e\u003c/span\u003e of this procedure. Can you help him?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e3 ≤ \u003ci\u003en\u003c/i\u003e ≤ 3000\u003c/span\u003e) — the number of nodes and edges in the graph. Each of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contains two space-separated integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(0 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e - 1)\u003c/span\u003e indicating an edge between nodes \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eConsider that the graph nodes are numbered from \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003en\u003c/i\u003e - 1)\u003c/span\u003e. It\u0027s guaranteed that there are no self-loops, no multiple edges in that graph. It\u0027s guaranteed that the graph is connected.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single real number — the expectation of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etotalCost\u003c/i\u003e\u003c/span\u003e. Your answer will be considered correct if its absolute or relative error does not exceed \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e - 6\u003c/sup\u003e\u003c/span\u003e.\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\n3 4\n2 3\n2 4\n0 4\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13.166666666666666\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\n0 1\n1 2\n0 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6.000000000000000\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\n0 1\n1 2\n2 0\n3 0\n4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13.166666666666666\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\u003eConsider the second example. No matter what we choose first, the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etotalCost\u003c/i\u003e\u003c/span\u003e will always be \u003cspan class\u003d\"tex-span\"\u003e3 + 2 + 1 \u003d 6\u003c/span\u003e.\u003c/p\u003e"}}]}