National Olympiad in Informatics, China, 2005

In a magical forest, there lives a clever little cat named CongCong and a cute little mouse named KoKo. Although Cinderella likes them both very much, CongCong is after all still a cat, and KoKo is after all still a mouse. It doesn't change the fact that CongCong still dreams of eating KoKo all day long.

One day, CongCong has accidentally obtained a very useful device, known as the GPS, capable of accurately locating KoKo. With this device, eating KoKo will be a piece of cake. So, CongCong immediately prepares to set out to find KoKo. Meanwhile, poor KoKo has no idea that disaster is around the corner, and is still carelessly playing in the forest. After receiving news of this, the little rabbit has dutifully reported it to Cinderella. Cinderella has decided to stop CongCong as soon as possible in order to save KoKo, but she doesn't know whether there's enough time left.

The entire forest can be viewed as an undirected graph with ~N~ beautiful scenery locations numbered from ~1~ to ~N~. Little animals in the forest only rest and play at these scenery locations. Amongst the locations, there are roads connecting them.

In the moment when CongCong first obtained the GPS, KoKo was at location ~M~ ~(M \le N)~. Afterwards, for each unit of time, KoKo may choose to visit one (of possibly many) neighboring locations, or he may choose to remain stationary at a location. The probability of visiting these locations are equal. Let there be ~P~ neighboring locations of location ~M~. They are respectively locations ~R, S, \dots, Q~. If at time ~T~ KoKo is located at ~M~, then at time ~T+1~, KoKo has a ~\frac{1}{P+1}~ chance of being at ~R~, a ~\frac{1}{P+1}~ chance of being at ~S, \dots, Q~, a ~\frac{1}{P+1}~ chance of being at ~Q~, and finally a ~\frac{1}{P+1}~ chance of remaining stationary at ~M~.

We know that CongCong is very clever, so when she is at location ~C~, she will select a location which is closer to KoKo. If there are many such locations, she will choose the location with the smallest number label. Since CongCong wants to eat KoKo so badly, if after taking the first step she still hasn't eaten KoKo, then she can take another step towards KoKo in the same current time unit.

In each time unit, assume that CongCong moves first, and KoKo moves last. At any given moment, if CongCong and KoKo are located in the same scenery location, then poor KoKo will have been eaten.

Cinderella knows that on average, CongCong will be able to eat KoKo after taking only a few steps. You must quickly help Cinderella determine an answer.

Input Specification

The first line of input contains two space-separated integers ~N~ and ~E~, respectively representing the number of scenery locations in the forest and the number of roads that connect the locations.
The second line of input contains two space-separated integers ~C~ and ~M~, respectively representing the initial locations of CongCong and KoKo.
The remaining ~E~ lines each contain 2 integers. Line ~i+2~ contains two integers ~A_i~ and ~B_i~, indicating that there is a road between locations ~A_i~ and ~B_i~.
All roads are undirected - that is, if ~A~ can reach ~B~, then ~B~ can reach ~A~.
The input guarantees that for any two scenery locations, there will not be more than one road connecting them. Also, there will always be a direct or indirect path connecting CongCong and KoKo's locations.

Output Specification

Output a single real number - the average number of time units after which CongCong will eat KoKo, rounded and displayed to 3 decimal places.

Sample Input 1

4 3
1 4
1 2
2 3
3 4

Sample Output 1

1.500

Explanation 1

Initially, CongCong and KoKo are separately located at scenery locations 1 and 4.
In the 1st time unit, CongCong moves first, in the direction that makes her closer to KoKo (at location 4), arriving at location 2 and then location 3. It's assumed that the time taken to travel is negligible.
KoKo moves next, and there are two possibilities:
The first possibility is to go to location 3, arriving at the same location as CongCong and being eaten. The number of steps this takes is 1, and has a probability of ~\frac 1 2~.
The second possibility is to remain stationary at location 4 and not get eaten. This also has a probability of ~\frac 1 2~.
In the 2nd time unit, CongCong moves towards the even closer location of KoKo (location 4), only needing to take one step before arriving at the same location as him. In this case, CongCong will be able to eat KoKo in two steps.
Therefore, the average number of steps taken is ~1 \times \frac 1 2 + 2 \times \frac 1 2 = 1.5~ steps.

Sample Input 2

9 9
9 3
1 2
2 3
3 4
4 5
3 6
4 6
4 7
7 8
8 9

Sample Output 2

2.167

Explanation 2

The forest is depicted in the following figure:

Constraints

For all of the test cases, ~1 \le N~, ~E \le 1\,000~.
For test cases worth 50% of points, ~1 \le N \le 50~.

Problem translated to English by Alex.