Expected Steps in a Random Maze

Morenan is trapped in a maze which can be modeled as a directed graph with \(n\) nodes and \(m\) edges. He starts at node \(s\) and his goal is to reach node \(t\). Unfortunately, Morenan is not very bright; from any node, he randomly chooses one of the outgoing edges and follows it. Due to this behavior, the number of steps he takes may be very large, or even infinite if he is unable to reach \(t\). Your task is to compute the expected number of steps until he reaches \(t\). If there is a positive probability that \(t\) is never reached, then the expected number of steps is considered to be infinite.

Problem Details

• The maze is represented as a directed graph with \(n\) nodes and \(m\) edges.
• Morenan starts at node \(s\) and the target node is \(t\).
• At each node \(v\) (\(v \neq t\)), if there are \(d_v\) outgoing edges to nodes \(u_1, u_2, \dots, u_{d_v}\), the expected steps \(E(v)\) satisfy the equation \[ E(v) = 1 + \frac{E(u_1) + E(u_2) + \cdots + E(u_{d_v})}{d_v}. \]
• For the destination node \(t\), \(E(t) = 0\).
• If from the starting node \(s\) there is a nonzero probability that \(t\) is never reached, output infinity.

inputFormat

The first line contains four integers: \(n\), \(m\), \(s\) and \(t\) where \(n\) is the number of nodes, \(m\) is the number of edges, \(s\) is the starting node, and \(t\) is the target node.

Then \(m\) lines follow, each containing two integers \(u\) and \(v\) indicating a directed edge from \(u\) to \(v\). It is guaranteed that all numbers are positive and the nodes are labeled from 1 to \(n\).

outputFormat

If the expected number of steps is finite, output a floating point number representing the expected number of steps from \(s\) to \(t\). Otherwise, output the string infinity.

sample

3 3 1 3
1 2
2 3
1 3

1.5