Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()


Fixed submission:
def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    ans = N
    for vRem in range(N):
        if outdegs[vRem] == 1: continue
        dp = [0] * N
        for v in reversed(range(N-1)):
            if v != vRem:
                dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
            else:
                sumDP, maxDP = 0, -1
                for v2 in adjL[v]:
                    sumDP += dp[v2]
                    if dp[v2] > maxDP:
                        maxDP = dp[v2]
                dp[v] = (sumDP-maxDP) / (outdegs[v]-1) + 1
        ans = min(ans, dp[0])

    print(ans)


solve()


Fixed submission:
def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
adjL = [set() for _ in range(N)]
outdegs = [0] * N
edges = []
for _ in range(M):
    s, t = map(int, input().split())
    s, t = s-1, t-1
    adjL[s].add(t)
    outdegs[s] += 1
    edges.append((s, t))

def func():
    ps = [0] * N
    ps[0] = 1
    ns = [0] * N
    es = [0] * N
    for v in range(N-1):
        p, e = ps[v], es[v]
        outdeg = outdegs[v]
        if p != 0:
            n = ns[v] = e / p
            if len(adjL[v]) == 0:
                return N

        for v2 in adjL[v]:
            ps[v2] += p / outdeg
            es[v2] += p * (n+1) / outdeg

    if ps[-1] != 0:
        return es[-1] / ps[-1]
    else:
        return N

ans = func()
for vFr, vTo in edges:
    adjL[vFr].remove(vTo)
    outdegs[vFr] -= 1

    num = func()

    adjL[vFr].add(vTo)
    outdegs[vFr] += 1

    ans = min(ans, num)

print(ans)


Fixed submission:
def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
adjL = [set() for _ in range(N)]
outdegs = [0] * N
edges = []
for _ in range(M):
    s, t = map(int, input().split())
    s, t = s-1, t-1
    adjL[s].add(t)
    outdegs[s] += 1
    edges.append((s, t))

def func():
    ps = [0] * N
    ps[0] = 1
    ns = [0] * N
    es = [0] * N
    for v in range(N-1):
        p, e = ps[v], es[v]
        outdeg = outdegs[v]
        if p != 0:
            n = ns[v] = e / p
            if len(adjL[v]) == 0:
                return N

        for v2 in adjL[v]:
            ps[v2] += p / outdeg
            es[v2] += p * (n+1) / outdeg

    if ps[-1] != 0:
        return es[-1] / ps[-1]
    else:
        return N

ans = func()
for vFr, vTo in edges:
    adjL[vFr].remove(vTo)
    outdegs[vFr] -= 1

    num = func()

    adjL[vFr].add(vTo)
    outdegs[vFr] += 1

    ans = min(ans, num)

print(ans)


Fixed submission:
def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()