Buggy python submission (verdict: Runtime Error):
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True
deg = adj.sum(axis=1)

ev = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  ev[i] = ev[adj[i]].mean() + 1.

prob = np.zeros(n, dtype=np.float)
prob[0] = 1.
for i in range(n - 1):
  prob[adj[i]] += prob[i] / deg[i]

decrease = 0.
for i in np.where(deg > 1)[0]:
  now = ev[adj[i]].mean()
  cut = (ev[adj[i]].sum() - ev[adj[i]].max()) / (deg[i] - 1)
  decrease = np.maximum(diff, now - cut)
    
print(ev[0] - decrease)

Fixed submission:
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True
deg = adj.sum(axis=1)

ev = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  ev[i] = ev[adj[i]].mean() + 1.

prob = np.zeros(n, dtype=np.float)
prob[0] = 1.
for i in range(n - 1):
  prob[adj[i]] += prob[i] / deg[i]

decrease = 0.
for i in np.where(deg > 1)[0]:
  now = ev[adj[i]].mean()
  cut = (ev[adj[i]].sum() - ev[adj[i]].max()) / (deg[i] - 1)
  decrease = np.maximum(decrease, (now - cut) * prob[i])
    
print(ev[0] - decrease)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True
deg = adj.sum(axis=1)

dp = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  dp[i] = dp[adj[i]].mean() + 1.
  
ans = dp[0]

for i in np.where(deg > 1)[0]:
  dp_i = dp.copy()
  dp_i[i] = (dp_i[adj[i]].sum() - dp_i[adj[i]].max()) / (deg[i] - 1) + 1.
  for j in range(i - 1, -1, -1):
    dp_i[j] = dp_i[adj[j]].mean() + 1.
  ans = np.minimum(ans, dp_i[0])
    
print(ans)

Fixed submission:
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True
deg = adj.sum(axis=1)

ev = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  ev[i] = ev[adj[i]].mean() + 1.

prob = np.zeros(n, dtype=np.float)
prob[0] = 1.
for i in range(n - 1):
  prob[adj[i]] += prob[i] / deg[i]

decrease = 0.
for i in np.where(deg > 1)[0]:
  now = ev[adj[i]].mean()
  cut = (ev[adj[i]].sum() - ev[adj[i]].max()) / (deg[i] - 1)
  decrease = np.maximum(decrease, (now - cut) * prob[i])
    
print(ev[0] - decrease)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True

dp = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  dp[i] = dp[adj[i]].mean() + 1.
  
ans = dp[0]

for i in np.where(adj.sum(axis=1) > 1)[0]:
  dp_i = dp.copy()
  dp_i[i] = (dp_i[adj[i]].sum() - dp_i[adj[i]].max()) / (adj[i].sum() - 1) + 1
  for j in range(i - 1, -1, -1):
    dp_i[j] = dp_i[adj[j]].mean() + 1
  ans = np.minimum(ans, dp_i[0])
    
print(ans)

Fixed submission:
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True
deg = adj.sum(axis=1)

ev = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  ev[i] = ev[adj[i]].mean() + 1.

prob = np.zeros(n, dtype=np.float)
prob[0] = 1.
for i in range(n - 1):
  prob[adj[i]] += prob[i] / deg[i]

decrease = 0.
for i in np.where(deg > 1)[0]:
  now = ev[adj[i]].mean()
  cut = (ev[adj[i]].sum() - ev[adj[i]].max()) / (deg[i] - 1)
  decrease = np.maximum(decrease, (now - cut) * prob[i])
    
print(ev[0] - decrease)

Buggy python submission (verdict: Runtime Error):
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True

dp = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  dp[i] = dp[adj[i]].mean() + 1.
  
ans = dp[0]

for i in np.where(adj.sum(axis=1) > 1)[0]:
  dp_i = dp.copy()
  dp_i[i] = (dp_i[adj[i]].sum() - dp_i[adj[i]].max()) / (adj[i].sum() - 1) + 1
  for j in range(i - 1, -1, -1):
    dp_i[j] = dp_i[adj[j]].mean() + 1
  ans = min[ans, dp_i[0]]
    
print(ans)

Fixed submission:
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True
deg = adj.sum(axis=1)

ev = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  ev[i] = ev[adj[i]].mean() + 1.

prob = np.zeros(n, dtype=np.float)
prob[0] = 1.
for i in range(n - 1):
  prob[adj[i]] += prob[i] / deg[i]

decrease = 0.
for i in np.where(deg > 1)[0]:
  now = ev[adj[i]].mean()
  cut = (ev[adj[i]].sum() - ev[adj[i]].max()) / (deg[i] - 1)
  decrease = np.maximum(decrease, (now - cut) * prob[i])
    
print(ev[0] - decrease)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True

dp = np.ones((n, n), dtype=np.float) * np.inf
dp[:, n - 1] = 0.
for i in range(n - 2, -1, -1):
  dp[n - 1, i] = dp[n - 1, adj[i]].mean() + 1
  
for i in np.where(adj.sum(axis=1) > 1)[0]:
  dp[i, i + 1:] = dp[n - 1, i + 1:]
  dp[i, i] = (dp[i, adj[i]].sum() - dp[i, adj[i]].max()) / (adj[i].sum() - 1) + 1
  for j in range(i - 1, -1, -1):
    dp[i, j] = dp[i, adj[j]].mean() + 1
    
print(dp[:, 0].min())

Fixed submission:
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True
deg = adj.sum(axis=1)

ev = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  ev[i] = ev[adj[i]].mean() + 1.

prob = np.zeros(n, dtype=np.float)
prob[0] = 1.
for i in range(n - 1):
  prob[adj[i]] += prob[i] / deg[i]

decrease = 0.
for i in np.where(deg > 1)[0]:
  now = ev[adj[i]].mean()
  cut = (ev[adj[i]].sum() - ev[adj[i]].max()) / (deg[i] - 1)
  decrease = np.maximum(decrease, (now - cut) * prob[i])
    
print(ev[0] - decrease)