Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import deque

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M=LI()
RES = [-1]*(N+1)
RES[N] = 0.0

MP=[[] for i in range(N+1)]
for _ in range(M):
    i, j = LI()
    MP[i].append(j)

for i in range(N-1, 0, -1):
    div = len(MP[i])
    next_E = 0
    for j in MP[i]: next_E += RES[j] + 1
    RES[i] = next_E / div

result = RES[1]
RESN = [0]*(N+1)

for i in range(1, N-1):
    if len(MP[i]) == 1: continue

    max_j = max((RES[w],w) for w in MP[i])[1]
    for k in range(N-1, 0, -1):
        div = 0
        next_E = 0
        for j in MP[k]:
            if k != i or j != max_j:
                div += 1
                next_E += RESN[j] + 1
        RESN[k] = next_E / div
    result = min(result, RESN[1])

print(result)


Fixed submission:
def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)
 
    # 確率DP
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])
 
    # 期待値DP
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])
 
    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        # 各vに対して、辺vwのうちE[w]が最大のものを削除する
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)
 
    print(ans)
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import deque

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M=LI()
RES = [-1]*(N+1)
RES[N] = 0.0

MP=[[] for i in range(N+1)]
for _ in range(M):
    i, j = LI()
    MP[i].append(j)
# print(MP)

for i in range(N-1, 0, -1):
    div = len(MP[i])
    next_E = 0
    for j in MP[i]: next_E += RES[j] + 1
    RES[i] = next_E / div

len_1 = len(MP[1])

# print("len_1: {}".format(len_1))
# print(RES)

result = RES[1]
RESN = [0]*(N+1)
for i in range(1, N-1):
    skip = False
    max_j = max((RES[w],w) for w in MP[i])[1]

    for k in range(N-1, 0, -1):
        div = 0
        next_E = 0
        for j in MP[k]:
            if k != i or j != max_j:
                div += 1
                next_E += RESN[j] + 1
        if div == 0:
            skip = True
            break
        else:
            RESN[k] = next_E / div
    if not skip:
        result = min(result, RESN[1])

print(result)


Fixed submission:
def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)
 
    # 確率DP
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])
 
    # 期待値DP
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])
 
    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        # 各vに対して、辺vwのうちE[w]が最大のものを削除する
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)
 
    print(ans)
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import deque

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M=LI()
RES = [-1]*(N+1)
RES[N] = 0.0

MP=[[] for i in range(N+1)]
for _ in range(M):
    i, j = LI()
    MP[i].append(j)
# print(MP)

for i in range(N-1, 0, -1):
    div = len(MP[i])
    next_E = 0
    for j in MP[i]: next_E += RES[j] + 1
    RES[i] = next_E / div

len_1 = len(MP[1])

# print("len_1: {}".format(len_1))
# print(RES)

result = RES[1]
RESN = [0]*(N+1)
for i in range(1, N-1):
    skip = False
    max_j, max_value = 0, 0

    for j in MP[i]:
        if RES[j] > max_value:
            max_value = RES[j]
            max_j = j

    for k in range(N-1, 0, -1):
        div = 0
        next_E = 0
        for j in MP[k]:
            if k != i or j != max_j:
                div += 1
                next_E += RESN[j] + 1
        if div == 0:
            skip = True
            break
        else:
            RESN[k] = next_E / div
    if not skip:
        result = min(result, RESN[1])

print(result)


Fixed submission:
def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)
 
    # 確率DP
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])
 
    # 期待値DP
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])
 
    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        # 各vに対して、辺vwのうちE[w]が最大のものを削除する
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)
 
    print(ans)
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import deque

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M=LI()
RES = [-1]*(N+1)
RES[N] = 0.0

MP={}
for _ in range(M):
    i, j = LI()
    if not i in MP: MP[i] = []
    MP[i].append(j)
# print(MP)

for i in range(N-1, 0, -1):
    div = len(MP[i])
    next_E = 0
    for j in MP[i]: next_E += RES[j] + 1
    RES[i] = next_E / div

len_1 = len(MP[1])

# print("len_1: {}".format(len_1))
# print(RES)


result = 10.0**15
RESN = [0]*(N+1)
for i in range(1, N-1):
    skip = False
    max_j, max_value = 0, 0

    for j in MP[i]:
        if RES[j] > max_value:
            max_value = RES[j]
            max_j = j

    for k in range(N-1, 0, -1):
        div = 0
        next_E = 0
        for j in MP[k]:
            if k != i or j != max_j:
                div += 1
                next_E += RESN[j] + 1
        if div == 0:
            skip = True
            break
        else:
            RESN[k] = next_E / div
    if not skip:
        result = min(result, RESN[1])

print(min(result, RES[1]))


Fixed submission:
def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)
 
    # 確率DP
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])
 
    # 期待値DP
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])
 
    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        # 各vに対して、辺vwのうちE[w]が最大のものを削除する
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)
 
    print(ans)
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import deque

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y
def primes(n):
    P = [2]
    for L in range(3, n):
        isP = True
        for L2 in P:
            isP = isP and L%L2
            if not isP: break
        if isP: P.append(L)
    return P


N,M=LI()
RES = [-1]*(N+1)
RES[N] = 0.0

MP={}
for _ in range(M):
    i, j = LI()
    if not i in MP: MP[i] = []
    MP[i].append(j)
# print(MP)

for i in range(N-1, 0, -1):
    div = len(MP[i])
    next_E = 0
    for j in MP[i]: next_E += RES[j] + 1
    RES[i] = next_E / div

len_1 = len(MP[1])

# print("len_1: {}".format(len_1))
# print(RES)


result = 10.0**15
RESN = [0]*(N+1)
for i in range(1, N-1):
    skip = False
    for k in range(N+1): RESN[k] = -1
    RESN[N] = 0

    max_j, max_value = 0, 0

    for j in MP[i]:
        if RES[j] > max_value:
            max_value = RES[j]
            max_j = j

    for k in range(N-1, 0, -1):
        div = 0
        next_E = 0
        for j in MP[k]:
            if k != i or j != max_j:
                div += 1
                next_E += RESN[j] + 1
        if div == 0:
            skip = True
            break
        else:
            RESN[k] = next_E / div
    if not skip:
        result = min(result, RESN[1])

print(min(result, RES[1]))


Fixed submission:
def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)
 
    # 確率DP
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])
 
    # 期待値DP
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])
 
    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        # 各vに対して、辺vwのうちE[w]が最大のものを削除する
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)
 
    print(ans)
resolve()