Cat and Mouse in the Enchanted Forest

In a magical forest there are N scenic spots numbered from 1 to N connected by bidirectional roads. A clever cat, Congcong, is determined to catch the cute mouse, Keke. When Congcong obtains a GPS machine, she can determine Keke’s exact location. At time 0, Keke is at scenic spot M and Congcong is at a given initial spot. In each time unit the following happens:

1. Congcong moves first. She always moves from her current position C to an adjacent spot that is strictly closer to Keke’s current location (i.e. the shortest‐path distance decreases). If there are several choices she picks the one with the smallest index. Moreover, because she is so eager, after her first move in the same time unit, if she has not caught Keke yet, she makes an additional move following the same rule (i.e. she again moves to an adjacent spot closer to Keke’s current location, with tie broken by smallest index).
2. Then Keke moves. At his turn Keke will move from his current spot to one of its adjacent spots or choose to remain in place. If there are P adjacent spots then all P+1 choices are equally likely (each with probability \( \frac{1}{P+1} \)).

If at any moment (i.e. immediately after Congcong’s moves or after Keke’s move) they are on the same scenic spot, Keke is caught. Cinderella wants to know the expected number of steps (each move of the cat is counted as one step) that Congcong will take until she catches Keke, averaged over the randomness in Keke’s moves.

Note on cat's movement: Let nxt(u,v) denote the function that returns the adjacent scenic spot of u (choosing the smallest index in case of ties) that lies on a shortest path from u to v (i.e. whose distance to v is \(d(u,v)-1\)). In each time unit if the cat is at u and the mouse at v (with \(u\neq v\)) then:

• If \(d(u,v)=1\), Congcong moves directly to v and catches Keke in 1 step.
• If \(d(u,v)=2\), then the cat moves from u to \(X=\text{nxt}(u,v)\) (which cannot be v because \(d(u,v)=2\)) and then moves from X to v in the second step, so 2 steps in total.
• If \(d(u,v)\ge 3\), let \(X=\text{nxt}(u,v)\) and \(Y=\text{nxt}(X,v)\). The cat uses 2 steps this time unit to move from \(u\) to \(Y\). Then the mouse moves: if scenic spot v has P neighbors then Keke will move to one of \(v\) or each of its adjacent spots with probability \(\frac{1}{P+1}\). Thus the process transitions to a new state \((Y,m')\), where \(m'\) is one of \(\{v\}\cup{\rm neighbors}(v)\). The expected number of additional cat steps is then averaged over these possibilities.

Your task is to compute the expected number of cat steps required to catch Keke, given the forest layout and the initial positions. It is guaranteed that the forest (graph) is connected and the cat’s strategy always moves it closer to Keke’s current location.

Input/Output Note: All formulas must be typeset using LaTeX notation. For example, use \(\frac{1}{P+1}\) for fractions.

inputFormat

The input begins with two integers N and E on the first line, representing the number of scenic spots and the number of roads, respectively.

The second line contains two integers M and C, where M (\(\le N\)) is the initial scenic spot of the mouse and C is the initial scenic spot of the cat.

Then follow E lines; each line contains two integers \(u\) and \(v\) indicating that there is an undirected road connecting scenic spots \(u\) and \(v\).

Note: It is guaranteed that the graph is connected.

outputFormat

Output a single floating point number — the expected number of cat steps until the mouse is caught. The answer should be accurate up to at least 6 decimal places.

sample

4 3
4 1
1 2
2 3
3 4

2.5