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 numpy as np
  
  N, M = map(int, input().strip().split())
  R_table = [[False] * N for _ in range(N)]
  M_list = []
  for _ in range(M):
      s, t = map(int, input().strip().split())
      s -= 1
      t -= 1
      R_table[s][t] = True
      M_list.append((s, t))
  
  # print(R_table)
  
  
  def make_col(col, i):
      count = 0
      for j in range(N):
          if col[j]:
              count += 1
      if count == 0:
          return None
      m_col = []
      ratio = 1.0 / count
      for j in range(N):
          if col[j]:
              m_col.append(ratio)
          else:
              m_col.append(0.0)
      m_col[i] = -1.0
      return m_col
  
  
  def make_matrix(R_table):
      matrix = []
      for i in range(N - 1):
          matrix.append(make_col(R_table[i], i))
      matrix.append([0.0] * (N - 1) + [1.0])
      return np.array(matrix)
  
  
  v_one = np.array([-1.0] * (N - 1) + [0.0])
  
  
  def solve(matrix):
      # 	print(matrix)
      # 	print(v_one)
      s = np.linalg.solve(matrix, v_one)
      # 	print(s)
      return s
  
  
  matrix = make_matrix(R_table)
  min_dist = solve(matrix)[0]
  
  for s, t in M_list:
      org_col = matrix[s]
      tmp_col = list(R_table[s])
      tmp_col[t] = False
      tmp_col2 = make_col(tmp_col, s)
      if tmp_col2 != None:
          matrix[s] = np.array(tmp_col2)
          try:
              dist = solve(matrix)[0]
              if min_dist == None or dist < min_dist:
                  min_dist = dist
          except:
              pass
      matrix[s] = org_col
  
  print(min_dist)
  
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"}]