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 destination is $T$.

Unfortunately, Morenan is not very bright. He only moves by choosing one of the outgoing edges from his current vertex uniformly at random and moving to the next vertex. As a result, the number of steps Morenan takes could be very large, infinite, or he might never reach the destination. If he cannot reach the destination, the number of steps is considered to be infinity. You must find the expected number of steps Morenan takes.

Input

The first line contains four integers $N, M, S, T$.

Each of the next $M$ lines contains two integers $o_1, o_2$, representing a directed edge from $o_1$ to $o_2$.

Output

A single floating-point number, rounded to 3 decimal places, representing the expected number of steps. If the expected value is infinity, output INF.

Examples

Input 1

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

Output 1

3.000

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

Output 2

9.500

Input 3

2 0 1 2

Output 3

INF

Subtasks

Additionally, $40\%$ of the test cases are guaranteed to have no cycles and no self-loops.