#3345. [SDOI2012]走迷宫

[SDOI2012]走迷宫

Description

Morenan被困在了一个迷宫里。迷宫可以视为N个点M条边的有向图,其中Morenan处于起点S,迷宫的终点设为T。可惜的是,Morenan非常的脑小, 他只会从一个点出发随机沿着一条从该点出发的有向边,到达另一个点。 这样,Morenan走的步数可能很长,也可能是无限,更可能到不了终点。 若到不了终点,则步数视为无穷大。 但你必须想方设法求出Morenan所走步数的期望值。

Format

Input

第1行4个整数,N,M,S,T

第[2, M+1]行每行两个整数o1, o2,表示有一条从o1到o2的边。

Output

一个浮点数,保留小数点3位,为步数的期望值。若期望值为无穷大,则输出"INF"。

【样例输入1】

6 6 1 6

1 2

1 3

2 4

3 5

4 6

5 6

【样例输出1】

3.000

【样例输入2】

9 12 1 9

1 2

2 3

3 1

3 4

3 7

4 5

5 6

6 4

6 7

7 8

8 9

9 7

【样例输出2】

9.500

【样例输入3】

2 0 1 2

【样例输出3】

INF

【数据范围】

测试点 N M Hint
[1, 6] <=10 <=100
[7, 12] <=200 <=10000
[13, 20] <=10000 <=1000000 保证强连通分量的大小不超过100

另外,均匀分布着40%的数据,图中没有环,也没有自环

Samples