Woburn Challenge 2015-16 Round 2 - Senior Division

Problem III: Revenge of the Sith

“If you're not with me, then you're my enemy!”
“Only a Sith deals in absolute values.”

Obi-Wan Kenobi and Anakin Skywalker, once the best of friends, find themselves about to have a vicious duel on a volcanic planet in the Mustafar system. Their fight will take place in the Separatists' hideout, a base consisting of N (2 ≤ N ≤ 45,678) chambers and M (0 ≤ M ≤ 234,567) corridors. The i-th corridor connects chambers A_i and B_i, and can be traversed in either direction. No pair of chambers are directly connected by multiple corridors.

There's just one hold up – Obi-Wan and Anakin must find each other first. Anakin is waiting in a random chamber, and Obi-Wan is similarly about to land in a random chamber. With each of these locations chosen uniformly at random from the set of possible chambers, there are N² possible, equally-likely ordered pairs of starting chambers.

As soon as Obi-Wan lands in his chamber, he and Anakin will start looking for one another. Exactly once every minute, each of them will travel along a random corridor connected to their current chamber (chosen uniformly at random from the set of such corridors), unless their current chamber isn't connected to any corridors, in which case they'll stay where they are. If the two of them find themselves in the same chamber during any given minute, they'll commence their duel. Otherwise, they'll continue this process infinitely (Jedi do live for a long time). Note that, with the power of the Force, they each travel through their chosen corridor extremely quickly every minute – therefore, they can never meet up in a corridor, even if they both travel through the same one at the same time (in opposite directions).

What's the probability that Obi-Wan and Anakin will eventually meet up and actually have their duel?

In cases worth 40% of the points, N ≤ 1234 and M ≤ 4567.
In a subset of those cases worth 20% of the points, N ≤ 34 and M ≤ 456.

Input Format

The first line of input consists of two space-separated integers N and M.
The next M lines each consist of two space-separated integers A_i and B_i, for 1 = 1..M.

Output Format

Output a single real number between 0 and 1, the probability that Obi-Wan and Anakin will eventually duel.
Your answer must have an absolute error of no more than 10⁻⁶.

Sample Input

6 7
2 3
2 4
2 5
3 4
3 5
4 5
6 1

Sample Output

0.5

Explanation

There are 36 possible, equally-likely ordered pairs of starting chambers for Obi-Wan and Anakin. It so happens that for 18 of them, the probability of an eventual encounter is 100% (including the pairs (1, 1) and (2, 4)), while for the other 18, it's 0% (including the pairs (1, 6) and (5, 6)).

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 12, 2015
Author: SourSpinach

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

Comments (Search)