Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M = map(int, input().split())

m = map(int,read().split())
ST = zip(m,m)
 
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
 
for s,t in ST:
    edge_out[s].append(t)
    edge_in[t].append(s)
    

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Fixed submission:
N, M = map(int, input().split())
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
for i in range(M):
    s, t = map(int, input().split())
    edge_out[s].append(t)
    edge_in[t].append(s)

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

m = map(int,read().split())
ST = zip(m,m)
 
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
 
for s,t in ST:
    edge_out[s].append(t)
    edge_in[t].append(s)
    

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Fixed submission:
N, M = map(int, input().split())
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
for i in range(M):
    s, t = map(int, input().split())
    edge_out[s].append(t)
    edge_in[t].append(s)

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, M = map(int, input().split())
edge = [[] for i in range(N)]
for i in range(M):
    s, t = map(int, input().split())
    edge[s].append(t)

edge_sum = [len(edge[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = np.zeros(N + 1, dtype = np.float64) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + dp[np.array(edge[i])].sum()/edge_sum[i]

E = [dp[1]]

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    to = np.array(edge[i])
    x = to[np.argmax(dp[to])] #iからxへの道を塞ぐ
    dp[i] = 1 + (dp[to].sum() - dp[x])/(edge_sum[i] - 1)
    for j in range(i - 1, 0, - 1):
        dp[j] = 1 + dp[np.array(edge[j])].sum()/edge_sum[j]
    E.append(dp[1])
print(min(E))

Fixed submission:
N, M = map(int, input().split())
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
for i in range(M):
    s, t = map(int, input().split())
    edge_out[s].append(t)
    edge_in[t].append(s)

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
ST = np.array(read().split(), dtype=np.int64)
S = ST[::2]
T = ST[1::2]

edge = np.zeros((N + 1, N + 1), dtype=np.int64)
edge[S, T] = 1
edge_sum = np.sum(edge, axis=1) # edge_sum[i] = iから出ている道の本数

dp = np.zeros(N + 1, dtype = np.float64) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + (edge[i][i + 1:]*dp[i + 1:]).sum()/edge_sum[i]

E = [dp[1]]

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    to = np.where(edge[i] == 1)[0]
    x = to[np.argmax(dp[to])] #iからxへの道を塞ぐ
    edge[i][x] = 0
    edge_sum[i] -= 1
    for j in range(i, 0, - 1):
        dp[j] = 1 + (edge[j][j + 1:]*dp[j + 1:]).sum()/edge_sum[j]
    edge[i][x] = 1
    edge_sum[i] += 1
    E.append(dp[1])
print(min(E))

Fixed submission:
N, M = map(int, input().split())
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
for i in range(M):
    s, t = map(int, input().split())
    edge_out[s].append(t)
    edge_in[t].append(s)

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
ST = np.array(read().split(), dtype=np.int64)
S = ST[::2]
T = ST[1::2]

edge = np.zeros((N + 1, N + 1), dtype=np.int64)
edge[S, T] = 1
edge_sum = np.sum(edge, axis=1) # edge_sum[i] = iから出ている道の本数

dp = np.zeros(N + 1, dtype = np.float64) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + (edge[i][i + 1:]*dp[i + 1:]).sum()/edge_sum[i]

E = dp[1]

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    to = np.where(edge[i] == 1)[0]
    x = to[np.argmax(dp[to])] #iからxへの道を塞ぐ
    edge[i][x] = 0
    edge_sum[i] -= 1
    for j in range(i, 0, - 1):
        dp[j] = 1 + (edge[j][j + 1:]*dp[j + 1:]).sum()/edge_sum[j]
    edge[i][x] = 1
    edge_sum[i] += 1
    E = min(E, dp[1])
print(E)

Fixed submission:
N, M = map(int, input().split())
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
for i in range(M):
    s, t = map(int, input().split())
    edge_out[s].append(t)
    edge_in[t].append(s)

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
ST = np.array(read().split(), dtype=np.int64)
S = ST[::2]
T = ST[1::2]

edge = np.zeros((N + 1, N + 1), dtype=np.int64)
edge[S, T] = 1
edge_sum = np.sum(edge, axis=1) # edge_sum[i] = iから出ている道の本数

dp = np.zeros(N + 1, dtype = np.float64) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = (edge_sum[i] + (edge[i][i + 1:]*dp[i + 1:]).sum())/edge_sum[i]

E = dp[1]
#print(E)

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    to = np.where(edge[i] == 1)[0]
    x = to[np.argmax(dp[to])] #iからxへの道を塞ぐ
    edge[i][x] = 0
    edge_sum[i] -= 1
    for j in range(i, 0, - 1):
        dp[j] = (edge_sum[j] + (edge[j][j + 1:]*dp[j + 1:]).sum())/edge_sum[j]
    edge[i][x] = 1
    edge_sum[i] += 1
    E = min(E, dp[1])
print(E)

Fixed submission:
N, M = map(int, input().split())
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
for i in range(M):
    s, t = map(int, input().split())
    edge_out[s].append(t)
    edge_in[t].append(s)

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
ST = np.array(read().split(), dtype=np.int64)
S = ST[::2]
T = ST[1::2]

edge = np.zeros((N + 1, N + 1), dtype=np.int64)
edge[S, T] = 1
edge_sum = np.sum(edge, axis=1) # edge_sum[i] = iから出ている道の本数

dp = np.zeros(N + 1, dtype = np.float64) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = (edge_sum[i] + (edge[i][i + 1:]*dp[i + 1:]).sum())/edge_sum[i]

E = dp[1]


for j in range(M):
    s, t = S[j], T[j]
    # jから道が1本しか出ていない時道を塞ぐことはできない
    if edge_sum[s] == 1:
        continue
    # 道s→tを塞ぐ時
    edge[s][t] = 0
    edge_sum[s] -= 1
    for i in range(N - 2, 0, - 1):
        dp[i] = (edge_sum[i] + (edge[i][i + 1:]*dp[i + 1:]).sum())/edge_sum[i] # ここの計算量ってN?
    E = min(E, dp[1])
    edge[s][t] = 1
    edge_sum[s] += 1
    
print(E)

Fixed submission:
N, M = map(int, input().split())
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
for i in range(M):
    s, t = map(int, input().split())
    edge_out[s].append(t)
    edge_in[t].append(s)

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)