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 deque
  
  N, M = map(int, input().split())
  G1, G2 = [[] for _ in range(N)], [[] for _ in range(N)]
  for i in range(M):
      a, b = map(int, input().split())
      G1[a - 1].append(b - 1)
      G2[b - 1].append(a - 1)
  
  
  def bfs(G, s):
      seen = [0] * N
      d = [0] * N
      prev = [-1] * N
      todo = deque()
      seen[s] = 1
      todo.append(s)
      while todo:
          a = todo.popleft()
          for b in G[a]:
              if seen[b] == 0:
                  seen[b] = 1
                  todo.append(b)
                  d[b] += d[a] + 1
                  prev[b] = a
      return d, prev
  
  
  d, prev = bfs(G2, N - 1)
  G3 = [{} for _ in range(N)]
  for i in range(N):
      if not G1[i]:
          continue
      MIN = min([d[j] for j in G1[i]])
      nmin = sum([1 if MIN == d[j] else 0 for j in G1[i]])
      for j in G1[i]:
          if len(G1[i]) == 1:
              p = 1
          elif d[j] == MIN:
              p = 1 / (len(G1[i]) - 1)
          else:
              p = (1 - 1 / (len(G1[i]) - nmin)) * (1 / (len(G1[i]) - 1))
          G3[i][j] = p
  
  inc = [len(G2[i]) for i in range(N)]
  
  
  def toposort(inc, out):
      # https://ikatakos.com/pot/programming_algorithm/graph_theory/topological_sort
      S = {i for i, c in enumerate(inc) if c == 0}
      L = []
      while S:
          n = S.pop()
          L.append(n)
          for m in out[n]:
              inc[m] -= 1
              if inc[m] == 0:
                  S.add(m)
      return L
  
  
  L = toposort(inc, G1)
  dp = [[0] * N for _ in range(N)]
  dp[0][0] = 1
  for v1 in L[:-1]:
      for v2 in G3[v1].keys():
          p = G3[v1][v2]
          for i in range(1, N):
              dp[v2][i] += dp[v1][i - 1] * p
  
  ans = 0
  for i in range(N):
      ans += i * dp[-1][i]
  
  print(ans)
  
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"}]