Description

Morenan is trapped in a maze. The maze can be viewed as a directed graph with $n$ vertices and $m$ edges. Morenan starts at vertex $s$, and the exit of the maze is vertex $t$.

Unfortunately, Morenan is not very smart. From a vertex, he will randomly choose one outgoing directed edge from that vertex and move to the next vertex. In this way, the number of steps Morenan takes may be very large, may be infinite, and it is even possible that he will never reach the exit. If he cannot reach the exit, then the number of steps is considered infinite. You must find the expected number of steps Morenan takes.

Input Format

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

The next $m$ lines each contain two integers $u, v$, indicating that there is an edge from $u$ to $v$.

Output Format

Output one floating-point number, rounded to $3$ digits after the decimal point, representing the expected number of steps. If the expected value is infinite, output INF.

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

3.000

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

9.500

2 0 1 2

INF

Hint

In addition, for $40\%$ of the testdata (uniformly distributed), the graph has no cycles and no self-loops.

For $100\%$ of the testdata, $1\leq n\leq 10^4$, $0\leq m \leq 10^6$, and it is guaranteed that the size of each strongly connected component does not exceed $\boldsymbol{100}$.

Translated by ChatGPT 5