[SDOI2012] 走迷宫

题目描述

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

输入格式

第一行四个整数，\(n,m,s,t\)。

接下来 \(m\) 行，每行两个整数 \(u, v\) ，表示有一条从 \(u\) 到 \(v\) 的边。

输出格式

一个浮点数，保留小数点后 \(3\) 位，为步数的期望值。若期望值为无穷大，则输出INF。

样例 #1

样例输入 #1

6 6 1 6
1 2
1 3
2 4
3 5
4 6
5 6

样例输出 #1

3.000

样例 #2

样例输入 #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

样例输入 #3

2 0 1 2

样例输出 #3

INF

提示

另外，均匀分布着 \(40\%\) 的数据，图中没有环，也没有自环。

对于 \(100\%\) 的数据，\(1\leq n\leq 10^4\)，\(0\leq m \leq 10^6\)，保证强连通分量的大小不超过 \(\boldsymbol{100}\)。