Description

In a magical forest, there live a clever kitten Congcong and a cute little mouse Keke. Although Cinderella likes both of them very much, Congcong is still a cat and Keke is still a mouse, and one thing never changes: Congcong is always thinking about eating Keke.

One day, Congcong accidentally obtained a very useful device called a GPS, which can accurately locate Keke. With this device, it becomes easy for Congcong to catch Keke. So Congcong plans to set off immediately to find Keke. Poor Keke, unaware of the looming danger, is still playing in the forest without a care. Little Bunny "Guai Guai" hears about this and reports to Cinderella at once. Cinderella decides to stop Congcong as soon as possible to save Keke, but she does not know whether there is still enough time.

The entire forest can be regarded as an undirected graph with $N$ beautiful spots, numbered from $1$ to $N$. The little animals only rest and play at the spots. There are some roads connecting pairs of spots.

When Congcong gets the GPS, Keke is at spot $M$ ($M \le N$). In each subsequent time unit, Keke will choose one of the adjacent spots (possibly multiple) or stay at the current spot. The probabilities of these choices are equal. Suppose there are $P$ spots adjacent to spot $M$, namely spots $R$, $S$, …, $Q$. If at time $T$ Keke is at spot $M$, then at time $(T+1)$ Keke has a $1/(1 +P)$ chance to be at spot $R$, a $1/(1 +P)$ chance to be at spot $S$, …, a $1/(1 +P)$ chance to be at spot $Q$, and a $1/(1 +P)$ chance to remain at spot $M$.

We know Congcong is very smart, so when she is at spot $C$, she will choose an adjacent spot that is closer to Keke. If there are multiple such spots, she chooses the one with the smallest index. Because Congcong is eager to eat Keke, if she still has not caught Keke after taking the first step, she can take one more step toward Keke within the same time unit. Assume the time spent walking is ignored.

In each time unit, Congcong moves first and Keke moves afterward. At any time, if Congcong and Keke are at the same spot, then poor Keke is eaten.

Cinderella wants to know, on average, how many time units it will take for Congcong to eat Keke. You need to help Cinderella find the answer as quickly as possible.

Input Format

The first line contains two integers $N$ and $E$, separated by a space, representing the number of spots in the forest and the number of roads connecting adjacent spots.

The second line contains two integers $C$ and $M$, separated by a space, representing the initial spots of Congcong and Keke, respectively.

The next $E$ lines each contain two integers. On line $i+2$, the two integers $A_i$ and $B_i$ indicate that there is a road between spots $A_i$ and $B_i$. All roads are undirected, i.e., if one can go from $A$ to $B$, then one can also go from $B$ to $A$.

The input guarantees that there is no more than one direct road between any pair of spots, and that there is a path (direct or indirect) between Congcong and Keke.

Output Format

Output one real number, rounded to three decimal places, representing the expected number of time units after which Congcong will eat Keke.

4 3 
1 4 
1 2 
2 3 
3 4

1.500 

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

2.167

Hint

Sample Explanation 1:

Initially, Congcong and Keke are at spots 1 and 4, respectively.

At the first time unit, Congcong moves first. She moves toward Keke (spot 4), going to spot 2, then to spot 3; assume the time spent walking is ignored.

Keke then moves, with two possibilities: The first is moving to spot 3, in which case Congcong and Keke are at the same spot, Keke is eaten, the number of time units is $1$, and the probability is $0.5$. The second is staying at spot 4, not being eaten, with probability $0.5$.

At the second time unit, Congcong moves toward Keke (spot 4) and needs only one step to reach the same spot as Keke. Therefore, in this case, Congcong will eat Keke in two time units. Hence the expected number of time units is $1\times 1/2 + 2\times 1/2 =1.5$.

Sample Explanation 2:

The forest is shown below:

For 50% of the testdata, $1≤N≤50$. For all testdata, $1≤N,E≤1000$.

Translated by ChatGPT 5