### ** forkintheroad**

### forkintheroad

### Problem Statement

There is a cave consisting of `N` rooms and `M` one-directional passages. The rooms are numbered `1` through `N`.

Takahashi is now in Room `1`, and Room `N` has the exit. The `i`-th passage connects Room `s`_{i} and Room `t`_{i} (`s`_{i} < `t`_{i}) and can only be traversed in the direction from Room `s`_{i} to Room `t`_{i}. It is known that, for each room except Room `N`, there is at least one passage going from that room.

Takahashi will escape from the cave. Each time he reaches a room (assume that he has reached Room `1` at the beginning), he will choose a passage uniformly at random from the ones going from that room and take that passage.

Aoki, a friend of Takahashi's, can block one of the passages (or do nothing) before Takahashi leaves Room `1`. However, it is not allowed to block a passage so that Takahashi is potentially unable to reach Room `N`.

Let `E` be the expected number of passages Takahashi takes before he reaches Room `N`. Find the value of `E` when Aoki makes a choice that minimizes `E`.

### Constraints

`2 ≤ N ≤ 600`
`N-1 ≤ M ≤ N(N-1)/2`
`s`_{i} < t_{i}
- If
`i != j`, `(s`_{i}, t_{i}) ≠ (s_{j}, t_{j}). **(Added 21:23 JST)**
- For every
`v = 1, 2, ..., N-1`, there exists `i` such that `v = s`_{i}.

### Input

Input is given from Standard Input in the following format:

`N` `M`
`s`_{1} `t`_{1}
`:`
`s`_{M} `t`_{M}

### Output

Print the value of `E` when Aoki makes a choice that minimizes `E`.
Your output will be judged as correct when the absolute or relative error from the judge's output is at most `10`^{-6}.

### Sample Input 1

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

### Sample Output 1

1.5000000000

If Aoki blocks the passage from Room `1` to Room `2`, Takahashi will go along the path `1`

→ `3`

→ `4`

with probability `\frac{1}{2}` and `1`

→ `4`

with probability `\frac{1}{2}`. `E = 1.5` here, and this is the minimum possible value of `E`.

### Sample Input 2

3 2
1 2
2 3

### Sample Output 2

2.0000000000

Blocking any one passage makes Takahashi unable to reach Room `N`, so Aoki cannot block a passage.

### Sample Input 3

10 33
3 7
5 10
8 9
1 10
4 6
2 5
1 7
6 10
1 4
1 3
8 10
1 5
2 6
6 9
5 6
5 8
3 6
4 8
2 7
2 9
6 7
1 2
5 9
6 8
9 10
3 9
7 8
4 5
2 10
5 7
3 5
4 7
4 9

### Sample Output 3

3.0133333333