## WC '15 Contest 2 S3 - Revenge of the Sith

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
##### Woburn Challenge 2015-16 Round 2 - Senior Division
"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 chambers and corridors. The -th corridor connects chambers and , 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 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 of the points, and .
In a subset of those cases worth of the points, and .

#### Input Specification

The first line of input consists of two space-separated integers and .
The next lines each consist of two space-separated integers and , for .

#### Output Specification

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

#### 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 possible, equally-likely ordered pairs of starting chambers for Obi-Wan and Anakin. It so happens that for of them, the probability of an eventual encounter is (including the pairs and ), while for the other , it's (including the pairs and ).