Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def calc(N, adj, ignore, dp, prevs):
    s, t = ignore
    if len(adj[s]) == 1:
        return float("Inf")
    if ignore[0] != -1:
        adj[s].remove(t)
    for i in range(prevs, -1, -1):
        dp[i] = 0.0
        n = len(adj[i])
        for nxt in adj[i]:
            dp[i] += (dp[nxt] + 1) / n
    if ignore[0] != -1:
        adj[s].add(t)

    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    x = [(-1, -1)] + [None] * M
    for i in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
        x[i+1] = (s-1, t-1)
    x.sort(reverse=True)
    ans = float("Inf")
    dp = [0.0] * (N)
    prevs = N - 1
    for ignore in x:
        tmp = calc(N, adj, ignore, dp, prevs)
        ans = min(ans, tmp)
        if tmp != float("inf"):
            prevs = ignore[0]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def calc(N, adj, dp, ignore):
    s, t = ignore
    for i in range(N-1, -1, -1):
        dp[i] = 0.0
        n = len(adj[i])
        if i == s:
            n -= 1
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
    dp1 = [0.0] * N
    ans = calc(N, adj, dp1, (-1, -1))
    dp2 = [0.0] * N
    for i in range(N-1, -1, -1):
        if len(adj[i]) <= 1:
            continue
        j = i
        mx = -1
        for nxt in adj[i]:
            if dp1[nxt] > mx:
                j = nxt
                mx = dp1[nxt]
        tmp = calc(N, adj, dp2, (i, j))
        ans = min(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def calc(N, adj, ignore, dp, prevs):
    s, t = ignore
    for i in range(prevs+1):
        dp[i] = 0.0
    for i in range(prevs, -1, -1):
        n = len(adj[i])
        if i == s:
            n -= 1
            if n == 0:
                return float("Inf")
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    x = [(-1, -1)] + [None] * M
    for i in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
        x[i+1] = (s-1, t-1)
    x.sort(reverse=True)
    ans = float("Inf")
    dp = [0.0] * (N)
    prevs = N - 1
    for ignore in x:
        tmp = calc(N, adj, ignore, dp, prevs)
        ans = min(ans, tmp)
        prevs = ignore[0]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def calc(N, adj, dp, ignore):
    s, t = ignore
    for i in range(N-1, -1, -1):
        dp[i] = 0.0
        n = len(adj[i])
        if i == s:
            n -= 1
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
    dp1 = [0.0] * N
    ans = calc(N, adj, dp1, (-1, -1))
    dp2 = [0.0] * N
    for i in range(N-1, -1, -1):
        if len(adj[i]) <= 1:
            continue
        j = i
        mx = -1
        for nxt in adj[i]:
            if dp1[nxt] > mx:
                j = nxt
                mx = dp1[nxt]
        tmp = calc(N, adj, dp2, (i, j))
        ans = min(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def calc(N, adj, ignore, dp, prevs):
    s, t = ignore
    for i in range(prevs+1):
        dp[i] = 0.0
    for i in range(prevs, -1, -1):
        n = len(adj[i])
        if i == s:
            n -= 1
            if n == 0:
                return float("Inf")
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    x = [(-1, -1)]
    for _ in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
        x.append((s-1, t-1))
    x.sort(reverse=True)
    ans = float("Inf")
    dp = [0.0] * (N)
    dp[N-1] = 0.0
    prevs = N - 1
    for ignore in x:
        tmp = calc(N, adj, ignore, dp, prevs)
        ans = min(ans, tmp)
        prevs = ignore[0]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def calc(N, adj, dp, ignore):
    s, t = ignore
    for i in range(N-1, -1, -1):
        dp[i] = 0.0
        n = len(adj[i])
        if i == s:
            n -= 1
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
    dp1 = [0.0] * N
    ans = calc(N, adj, dp1, (-1, -1))
    dp2 = [0.0] * N
    for i in range(N-1, -1, -1):
        if len(adj[i]) <= 1:
            continue
        j = i
        mx = -1
        for nxt in adj[i]:
            if dp1[nxt] > mx:
                j = nxt
                mx = dp1[nxt]
        tmp = calc(N, adj, dp2, (i, j))
        ans = min(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def calc(N, adj, ignore):
    dp = [0.0] * (N)
    dp[N-1] = 0.0
    s, t = ignore
    for i in range(N-2, -1, -1):
        n = len(adj[i])
        if i == s:
            n -= 1
            if n == 0:
                return float("Inf")
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    x = [(-1, -1)]
    for _ in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
        x.append((s-1, t-1))
    ans = float("Inf")
    for ignore in x:
        tmp = calc(N, adj, ignore)
        ans = min(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def calc(N, adj, dp, ignore):
    s, t = ignore
    for i in range(N-1, -1, -1):
        dp[i] = 0.0
        n = len(adj[i])
        if i == s:
            n -= 1
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
    dp1 = [0.0] * N
    ans = calc(N, adj, dp1, (-1, -1))
    dp2 = [0.0] * N
    for i in range(N-1, -1, -1):
        if len(adj[i]) <= 1:
            continue
        j = i
        mx = -1
        for nxt in adj[i]:
            if dp1[nxt] > mx:
                j = nxt
                mx = dp1[nxt]
        tmp = calc(N, adj, dp2, (i, j))
        ans = min(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()