Escape

One night , when dandelion fell asleep , she finds herself in a big maze . Different with other mazes ,the exit of the maze is changing all the time . Now dandelion knows the maze is made up of N rooms , signed as 1,2 …n. Some of the rooms are connected with undirected ways . To escape from the maze as soon as possible , every time dandelion will move to the room which is nearest to the exit . If there are several rooms , she will choose the room with the smallest number .Meanwhile , to leave the maze more quickly ,during every unit time , after moving once if dandelion doesn’t reach the exit ,she can move once again . If dandelion still doesn’t reach the exit , the exit will move to any room that connected with it , or stay at the same room . The possibility is average . Now dandelion wants to know the average time she needs to escape from the maze. Can you help her?

There are several cases ,every case begins with two numbers n and m (1<=n,m<=1000),stands for the number of rooms and the number of the ways . The second line contains two numbers a and b ,stands for the room where dandelion and the exit exist at the beginning . Then m lines ,each line with two numbers p and q ,stands for there is a way between room p and room q.

For every case ,print the average time t (rounded to three places beyond the decimal point) dandelin needs to escape from the maze.

4 3
1 4
1 2
2 3
3 4
2 1
1 1
1 2

1.500
0.000

dandelion

曾是惊鸿照影来