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: from collections import defaultdict
  
  
  def main():
      N, M = list(map(int, input().split(" ")))
      adj_from = defaultdict(list)
      adj_to = defaultdict(list)
      for _ in range(M):
          S, T = list(map(lambda x: int(x) - 1, input().split(" ")))
          adj_from[T].append(S)
          adj_to[S].append(T)
      # 青木君が邪魔しない場合に、各edgeがカウントされる確率を求める
      dp = [[0] * N for _ in range(N)]  # P[s][t]: edge 's->t' がカウントされる確率
      for t in adj_to[0]:
          dp[0][t] += 1 / len(adj_to[0])
      for n in range(1, N):
          for t in adj_to[n]:
              dp[n][t] = sum([dp[f][n] for f in adj_from[n]]) / len(adj_to[n])
      sum_p = sum([sum(row) for row in dp])  # 青木君が邪魔しない場合のedge数の期待値
      # 青木君が邪魔した時の減少分を求める
      rem_p = 0
      for row in dp:
          # 出次数が1のnodeから出るedgeを除外するとNG
          if len([r for r in row if r != 0]) == 1:
              continue
          for r in row:
              rem_p = max(rem_p, r)
      print(sum_p - rem_p)
  
  
  if __name__ == "__main__":
      main()
  
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"}]