## King Graff's Defense

King 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 = 2).

Feerie consists of N (1 ≤ N ≤ 106) towns (numbered 1..N), and M (1 ≤ M ≤ 106) roads. The i-th road runs between distinct towns Ai and Bi, 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's not much of a strategist, he'll choose the towns at complete random.

Graff's 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.

### Input

Line 1: 2 integers, N and M
Next M lines: 2 integers, Ai and Bi, for i = 1..M

### Output

Line 1: 1 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

4 4
1 2
1 3
2 4
4 1

0.50000

### Explanation of Sample

The map of Feerie is illustrated below:

King 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 = 0.5.

Point Value: 15 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (0/0)
As I'm sure you can see from the submissions panel (sorry about that, by the way), I'm having issues with SIGABRT on cases 6 and 7. As far as I can tell, this is a memory issue. Problem is, even code to just read the input is failing. Any ideas as to what the issue is, and hints on how to fix it?

Thanks!

• (0/0)
I got TLE LOL

• (1/0)
The data structures into which you're inserting your input have quite a bit of memory overhead - try using something simpler!

• (0/0)
Thanks, this solved the issue! Never knew that set was memory hungry...

• (0/0)
It needs at least 8 extra bytes per node to store child pointers.