Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [[] for i in range(n-1)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
dp = [0]*n
sum_d = [0]*(n-1)
max_d = [0]*(n-1)
b = [0]*n
for i in range(n-2,-1,-1):
  for j in a[i]:
    sum_d[i] += dp[j] + 1
    b[i] += 1
    if max_d[i] < dp[j]+1 and len(a[i]) > 1:
      max_d[i] = dp[j]+1  
  dp[i] = sum_d[i] / b[i]
min_dp = dp[0]
for k in range(n-2):
  if b[k]==1:
    continue
  dp[k] = (sum_d[k]-max_d[k]) / (b[k]-1)
  for i in range(k-1,-1,-1):
    dp[i] = sum([dp[j] + 1 for j in a[i]]) / b[i]
  min_dp = min(min_dp,dp[0])
print(min_dp)

Fixed submission:
n, m = map(int, input().split())
a = [[] for i in range(n-1)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
dp = [0]*n
sum_d = [0]*(n-1)
max_d = [0]*(n-1)
b = [0]*n
for i in range(n-2,-1,-1):
  for j in a[i]:
    sum_d[i] += dp[j] + 1
    b[i] += 1
    if max_d[i] < dp[j]+1 and len(a[i]) > 1:
      max_d[i] = dp[j]+1  
  dp[i] = sum_d[i] / b[i]
min_dp = dp[0]
for k in range(n-2):
  if b[k]==1:
    continue
  ddp = [0]*k + [dp[k] - (sum_d[k]-max_d[k])/(b[k]-1)]
  for i in range(k-1,-1,-1):
    ddp[i] = sum([ddp[j] for j in a[i] if j <= k]) / b[i]
  min_dp = min(min_dp,dp[0] - ddp[0])
print(min_dp)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [[] for i in range(n)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
dp = [0]*n
count = 0
c = []
for i in range(n-2,-1,-1):
  b = 0
  max_count = 0
  max_dp = 0
  for j in a[i]:
    dp[i] += dp[j] + 1
    b += 1
    if max_dp < dp[j]:
      max_count, max_dp = count, dp[j]
    count += 1
  if b>1:
    c.append(max_count)
  dp[i] /= b
min_dp = dp[0]
for k in c:
  dp = [0]*n
  count = 0
  for i in range(n-2,-1,-1):
    b = 0
    for j in a[i]:
      if count != k or len(a[i]) == 1:
        dp[i] += dp[j] + 1
        b += 1
      count += 1
    dp[i] /= b
  min_dp = min(min_dp,dp[0])
print(min_dp)

Fixed submission:
n, m = map(int, input().split())
a = [[] for i in range(n-1)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
dp = [0]*n
sum_d = [0]*(n-1)
max_d = [0]*(n-1)
b = [0]*n
for i in range(n-2,-1,-1):
  for j in a[i]:
    sum_d[i] += dp[j] + 1
    b[i] += 1
    if max_d[i] < dp[j]+1 and len(a[i]) > 1:
      max_d[i] = dp[j]+1  
  dp[i] = sum_d[i] / b[i]
min_dp = dp[0]
for k in range(n-2):
  if b[k]==1:
    continue
  ddp = [0]*k + [dp[k] - (sum_d[k]-max_d[k])/(b[k]-1)]
  for i in range(k-1,-1,-1):
    ddp[i] = sum([ddp[j] for j in a[i] if j <= k]) / b[i]
  min_dp = min(min_dp,dp[0] - ddp[0])
print(min_dp)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [[] for i in range(n)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
min_dp = n
for k in range(m):
  dp = [0]*n
  count = 0
  for i in range(n-2,-1,-1):
    b = 0
    for j in a[i]:
      if count != k or len(a[i]) == 1:
        dp[i] += dp[j] + 1
        b += 1
      count += 1
    dp[i] /= b
  min_dp = min(min_dp,dp[0])
print(min_dp)

Fixed submission:
n, m = map(int, input().split())
a = [[] for i in range(n-1)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
dp = [0]*n
sum_d = [0]*(n-1)
max_d = [0]*(n-1)
b = [0]*n
for i in range(n-2,-1,-1):
  for j in a[i]:
    sum_d[i] += dp[j] + 1
    b[i] += 1
    if max_d[i] < dp[j]+1 and len(a[i]) > 1:
      max_d[i] = dp[j]+1  
  dp[i] = sum_d[i] / b[i]
min_dp = dp[0]
for k in range(n-2):
  if b[k]==1:
    continue
  ddp = [0]*k + [dp[k] - (sum_d[k]-max_d[k])/(b[k]-1)]
  for i in range(k-1,-1,-1):
    ddp[i] = sum([ddp[j] for j in a[i] if j <= k]) / b[i]
  min_dp = min(min_dp,dp[0] - ddp[0])
print(min_dp)