Problem Description

Morenan is trapped in a maze, which can be represented as a directed graph with $n$ vertices and $m$ edges. Morenan is at the starting point $s$, and the exit of the maze is set at $t$. Unfortunately, Morenan's brain is quite small, and he can only randomly choose one of the outgoing directed edges from his current vertex to move to another vertex. This means the number of steps Morenan takes could be very long, infinite, or he might not even reach the exit. If he cannot reach the exit, the number of steps is considered infinite. However, you must find a way to calculate the expected number of steps Morenan will take.

Input Format

The first line contains four integers: $n$, $m$, $s$, and $t$.

The next $m$ lines each contain two integers $u$ and $v$, indicating a directed edge from $u$ to $v$.

Output Format

Output a floating-point number, rounded to three decimal places, representing the expected number of steps. If the expected number of steps is infinite, output INF.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3.000

Sample Input #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

Sample Output #2

9.500

Sample Input #3

2 0 1 2

Sample Output #3

INF

Notes

Additionally, 40% of the test cases have no cycles or self-loops in the graph.

For 100% of the data, $1\leq n\leq 10^4$, $0\leq m \leq 10^6$, and the size of any strongly connected component is guaranteed to be no more than $\boldsymbol{100}$.

见题面 Input 部分

见题面 Output 部分