{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e\r\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e// \u003c![CDATA[\r\nMathJax.Hub.Config({tex2jax: {inlineMath: [[\u0027$\u0027,\u0027$\u0027], [\u0027\\\\(\u0027,\u0027\\\\)\u0027]]}});\r\n// ]]\u003e\u003c/script\u003e\r\n\u003cscript src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e\r\n\u003c/p\u003e\r\n\u003cp\u003eKing Graff, the ruler of the land of Feerie, has a problem - his nation is under attack! Luckily, he has an army at his disposal, composed of a whopping $S$ soldiers (where $S \u003d 2$).\u003c/p\u003e\r\n\u003cp\u003eFeerie consists of $N$ ($1 \\leq N \\leq 100,000$) towns (numbered $1..N$), and $M$ ($1 \\leq M \\leq 500,000$) roads. The $i$th road runs between distinct towns $A_i$ and $B_i$, in both directions. No pair of towns is directly connected by more than one road, but every pair of towns is connected by at least one path of connected roads. King Graff would like to position his two soldiers in two different towns to prepare for the impending assault - however, since he\u0027s not much of a strategist, he\u0027ll choose the towns at complete random.\u003c/p\u003e\r\n\u003cp\u003eGraff\u0027s only real concern is with his enemies using a divide-and-conquer strategy. His soldiers will be susceptible to this type of attack if there exists any single road that, if blocked, will prevent them from reaching each other by any system of connected roads. As the royal computer scientist, your job is to determine the probability that King Graff will be defeated.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eFirst line: 2 integers, $N$ and $M$\u003c/p\u003e\r\n\u003cp\u003eNext $M$ lines: 2 integers, $A_i$ and $B_i$, for $i \u003d 1..M$\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e1 real number (rounded to 5 decimal places), the probability that the two towns chosen by Graff can be disconnected by the removal of any single road\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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 4\r\n1 2\r\n1 3\r\n2 4\r\n4 1\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.50000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\r\n\u003ch4\u003eExplanation of Sample:\u003c/h4\u003e\r\n\u003cp\u003eThe map of Feerie is illustrated below:\u003c/p\u003e\r\n\u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/19157336bec7dc17bd1a2b1f69efeb52?v\u003d1726100904\" alt\u003d\"\"\u003e\u003c/p\u003e\r\n\u003cp\u003eKing Graff can make 6 possible choices as to where to place his soldiers, and three of those (the three with one of the soldiers being at town 3) result in defeat (if the road between towns 1 and 3 is destroyed). The probability of failure is then $3/6 \u003d 0.5$.\u003c/p\u003e\n\u003c/div\u003e"}}]}