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 si and Room ti (si < ti) and can only be traversed in the direction from Room si to Room ti. 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
  • si < ti
  • If i != j, (si, ti) ≠ (sj, tj). (Added 21:23 JST)
  • For every v = 1, 2, ..., N-1, there exists i such that v = si.

Input

Input is given from Standard Input in the following format:

N M
s1 t1
:
sM tM

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 134 with probability \frac{1}{2} and 14 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

Submitting to 'forkintheroad'


You're not logged in! Click here to login


Submitting .cpp to 'forkintheroad'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 2 Seconds
Memory Limit: 1024MB
No. of ACs: 1
Your best score: 0
Source: AtCoder

Subtask Score
1 100
2 0