output_description: 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}.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      s_1 t_1
      :
      s_M t_M
attempt: import sys
  
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  N, M = map(int, input().split())
  
  m = map(int, read().split())
  ST = zip(m, m)
  
  edge_out = [[] for i in range(N)]  # edge_out[i]はiから出ている道
  edge_in = [[] for i in range(N + 1)]  # edge_in[i]はiに行く道
  
  for s, t in ST:
      edge_out[s].append(t)
      edge_in[t].append(s)
  
  
  edge_sum = [len(edge_out[i]) for i in range(N)]  # edge_sum[i] = iから出ている道の本数
  
  dp = [0.0] * (N + 1)  # dp[i]はiからNへの距離の期待値
  dp[N - 1] = 1.0
  # 道を塞がない場合
  for i in range(N - 2, 0, -1):
      dp[i] = 1 + sum(dp[j] for j in edge_out[i]) / edge_sum[i]
  
  p_to_i = [0] * (N + 1)  # p_to_i[i]は1から各iへ到達する確率
  p_to_i[1] = 1
  for i in range(2, N + 1):
      p_to_i[i] = sum(p_to_i[j] / edge_sum[j] for j in edge_in[i])
  
  
  t = 0
  
  for i in range(1, N - 1):
      if edge_sum[i] == 1:
          continue
          # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
      t = max(
          t,
          p_to_i[i]
          * (
              dp[i]
              - 1
              - ((dp[i] - 1) * edge_sum[i] - max(dp[j] for j in edge_out[i]))
              / (edge_sum[i] - 1)
          ),
      )
  
  print(dp[1] - t)
  
problem_description: 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.
samples: [{"input": "4 6\n    1 4\n    2 3\n    1 3\n    1 2\n    3 4\n    2 4", "output": "1.5000000000\n    \n\nIf Aoki blocks the passage from Room 1 to Room 2, Takahashi will go along the\npath `1` \u2192 `3` \u2192 `4` with probability \\frac{1}{2} and `1` \u2192 `4` with\nprobability \\frac{1}{2}. E = 1.5 here, and this is the minimum possible value\nof E.\n\n* * *"}, {"input": "3 2\n    1 2\n    2 3", "output": "2.0000000000\n    \n\nBlocking any one passage makes Takahashi unable to reach Room N, so Aoki\ncannot block a passage.\n\n* * *"}, {"input": "10 33\n    3 7\n    5 10\n    8 9\n    1 10\n    4 6\n    2 5\n    1 7\n    6 10\n    1 4\n    1 3\n    8 10\n    1 5\n    2 6\n    6 9\n    5 6\n    5 8\n    3 6\n    4 8\n    2 7\n    2 9\n    6 7\n    1 2\n    5 9\n    6 8\n    9 10\n    3 9\n    7 8\n    4 5\n    2 10\n    5 7\n    3 5\n    4 7\n    4 9", "output": "3.0133333333"}]