Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

S = {}
DP = [0] * N
for i in range(N - 2, -1, -1):
  cnt = 0
  su = 0
  a = 0
  amax = 0
  for x in R[i]:
    t = DP[x] + 1
    if t >= amax:
      amax = DP[x] + 1
      a = x
    su += DP[x] + 1
    cnt += 1
  DP[i] = su / cnt
  S[i] = a

ans = DP[0]
for i in range(N - 1):
  DP = [0] * N
  for j in range(N - 2, -1, -1):
    A = []
    su = 0
    for x in R[j]:
      if i == j:
        if S[i] == x:
          continue
      A.append(DP[x] + 1)
      su += A[-1]
    if len(A) == 0:
      break
    DP[j] = su / len(A)
  else:
    ans = min(DP[0], ans)

print(ans)



Fixed submission:
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [0] * N
ans = N
D = [0] * N
for i in range(N - 2, -1, -1):
  ma = 0
  su = 0
  le = len(R[i])
  for j in R[i]:
    su += DP[j]
    ma = max(ma, DP[j])

  DP[i] = su / le + 1 
  if le == 1:
    D[i] = 0
  else:
    D[i] = DP[i] - (((su - ma) / (le - 1)) + 1)

P = [0] * N 
P[0] = 1
ma = 0
man = -1
for i in range(N - 1):
  t = P[i] / len(R[i])
  for j in R[i]:
    P[j] += t 
  t = P[i] * D[i]
  R[i].sort()
  if ma < t:
    ma = t
    man = i
 
if ma == -1:
  print(DP[0])
else:
  print(DP[0] - ma)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

ans = N
for i in range(N - 1):
  DP = [0] * N
  for j in range(N - 2, -1, -1):
    su = 0
    amax = 0
    cnt = 0
    for x in R[j]:
      amax = max(amax, DP[x] + 1)
      su += DP[x] + 1
      cnt += 1
    DP[j] = su / cnt
    if i == j and cnt != 1:
      DP[j] = (su - amax) / (cnt - 1)

  ans = min(ans, DP[0])
 
print(ans)

Fixed submission:
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [0] * N
ans = N
D = [0] * N
for i in range(N - 2, -1, -1):
  ma = 0
  su = 0
  le = len(R[i])
  for j in R[i]:
    su += DP[j]
    ma = max(ma, DP[j])

  DP[i] = su / le + 1 
  if le == 1:
    D[i] = 0
  else:
    D[i] = DP[i] - (((su - ma) / (le - 1)) + 1)

P = [0] * N 
P[0] = 1
ma = 0
man = -1
for i in range(N - 1):
  t = P[i] / len(R[i])
  for j in R[i]:
    P[j] += t 
  t = P[i] * D[i]
  R[i].sort()
  if ma < t:
    ma = t
    man = i
 
if ma == -1:
  print(DP[0])
else:
  print(DP[0] - ma)

Buggy python submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

ans = N
for i in range(N - 1):
  DP = [0] * N
  for j in range(N - 2, -1, -1):
    su = 0
    amax = 0
    cnt = 0
    for x in R[j]:
      amax = max(amax, DP[x] + 1)
      su += A[-1]
    DP[j] = su / cnt
    if i == j and cnt != 1:
      DP[j] = (su - amax) / (cnt - 1)

  ans = min(ans, DP[0])
 
print(ans)

Fixed submission:
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [0] * N
ans = N
D = [0] * N
for i in range(N - 2, -1, -1):
  ma = 0
  su = 0
  le = len(R[i])
  for j in R[i]:
    su += DP[j]
    ma = max(ma, DP[j])

  DP[i] = su / le + 1 
  if le == 1:
    D[i] = 0
  else:
    D[i] = DP[i] - (((su - ma) / (le - 1)) + 1)

P = [0] * N 
P[0] = 1
ma = 0
man = -1
for i in range(N - 1):
  t = P[i] / len(R[i])
  for j in R[i]:
    P[j] += t 
  t = P[i] * D[i]
  R[i].sort()
  if ma < t:
    ma = t
    man = i
 
if ma == -1:
  print(DP[0])
else:
  print(DP[0] - ma)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

ans = N
for i in range(N - 1):
  DP = [0] * N
  for j in range(N - 2, -1, -1):
    A = []
    su = 0
    for x in R[j]:
      A.append(DP[x] + 1)
      su += A[-1]
    DP[j] = su / len(A)
    if i == j and len(A) != 1:
      DP[j] = (su - max(A)) / (len(A) - 1)

  ans = min(ans, DP[0])
 
print(ans)

Fixed submission:
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [0] * N
ans = N
D = [0] * N
for i in range(N - 2, -1, -1):
  ma = 0
  su = 0
  le = len(R[i])
  for j in R[i]:
    su += DP[j]
    ma = max(ma, DP[j])

  DP[i] = su / le + 1 
  if le == 1:
    D[i] = 0
  else:
    D[i] = DP[i] - (((su - ma) / (le - 1)) + 1)

P = [0] * N 
P[0] = 1
ma = 0
man = -1
for i in range(N - 1):
  t = P[i] / len(R[i])
  for j in R[i]:
    P[j] += t 
  t = P[i] * D[i]
  R[i].sort()
  if ma < t:
    ma = t
    man = i
 
if ma == -1:
  print(DP[0])
else:
  print(DP[0] - ma)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [[0] * N for _ in range(N)]

for i in range(N - 2, -1, -1):
  A = []
  su = 0
  for x in R[i]:
    A.append(DP[x][0] + 1)
    su += A[-1]
  for j in range(i + 1):
    DP[i][j] = su / len(A)
  if len(A) != 1:
    DP[i][i] = (su - max(A)) / (len(A) - 1)
  
  for j in range(i + 1, N):
    su = 0
    for x in R[i]:
      su += DP[x][j] + 1
    DP[i][j] = su / len(R[i])

print(min(DP[0]))

Fixed submission:
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [0] * N
ans = N
D = [0] * N
for i in range(N - 2, -1, -1):
  ma = 0
  su = 0
  le = len(R[i])
  for j in R[i]:
    su += DP[j]
    ma = max(ma, DP[j])

  DP[i] = su / le + 1 
  if le == 1:
    D[i] = 0
  else:
    D[i] = DP[i] - (((su - ma) / (le - 1)) + 1)

P = [0] * N 
P[0] = 1
ma = 0
man = -1
for i in range(N - 1):
  t = P[i] / len(R[i])
  for j in R[i]:
    P[j] += t 
  t = P[i] * D[i]
  R[i].sort()
  if ma < t:
    ma = t
    man = i
 
if ma == -1:
  print(DP[0])
else:
  print(DP[0] - ma)