Problem p03108 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
 
N, M = map(int, input().split())
X = []
for _ in range(M):
    a, b = map(int, input().split())
    X.append((a-1, b-1))
X = X[::-1]
    
P = [-1] * N
CT = [1] * N
def pr(i):
    if P[i] < 0:
        return i
    t = pr(P[i])
    P[i] = t
    return t
 
ANS = [0] * M
ans = N * (N-1) // 2
ANS[-1] = ans
for m in range(M-1):
    a, b = X[m]
    pa = pr(a)
    pb = pr(b)
    
    if pa != pb:
        ans -= CT[pa] * CT[pb]
        P[pa] = pb
        CT[pb] += CT[pa]
 
    ANS[-m-2] = ans
 
for a in ANS:
    print(a)

Buggy submission (verdict: Runtime Error):

n,m = list(map(int, input().split()))
a = []
b = []
for _ in range(m):
    aa, bb = list(map(int, input().split()))
    a.append(aa-1)
    b.append(bb-1)

a = a[::-1]
b = b[::-1]

ans = int(n * (n - 1) /2)
ans_rec = [0] * m
ans_rec[-1] = ans

p = [-1 for i in range(n)]
size = [1 for i in range(n)]

def find(x):
#     print(x, p[x])
    px = p[x]
    if px <0:
        return x
    else:
        pxx = find(px)
        p[x] = pxx
        return pxx

for k in range(m-1):
    pa = find(a[k])
    pb = find(b[k])
    if pa == pb:
        pass
    else:
        ans -= size[pa] * size[pb]
        size[pa] += size[pb]
        p[pb] = pa
    ans_rec[- k - 2] = ans
for aa in ans_rec:
    print(aa)

Buggy submission (verdict: Runtime Error):
n,m = list(map(int, input().split()))
a = []
b = []
for _ in range(m):
    aa, bb = list(map(int, input().split()))
    a.append(aa-1)
    b.append(bb-1)

a = a[::-1]
b = b[::-1]

ans = int(n * (n - 1) /2)
ans_rec = [ans]

p = [-1 for i in range(n)]
size = [1 for i in range(n)]

def find(x):
#     print(x, p[x])
    px = p[x]
    if px <0:
        return x
    else:
        pxx = find(px)
        p[x] = pxx
        return pxx

for k in range(m-1):
    pa = find(a[k])
    pb = find(b[k])
    if pa == pb:
        pass
    else:
        ans -= size[pa] * size[pb]
        size[pa] += size[pb]
        p[pb] = pa
    ans_rec.append(ans)
for a in ans_rec[::-1]:
    print(a)

Buggy submission (verdict: Runtime Error):
from itertools import combinations
import numpy as np


n,m = list(map(int, input().split()))
a = []
b = []
for _ in range(m):
    aa, bb = list(map(int, input().split()))
    a.append(aa)
    b.append(bb)

# %%time
def saiki(now, reachable):
#     print(now)
    cand = copy.deepcopy(dic[now])
    cue = []
    cand = dic[now]
    while len(cand) > 0:
        c = cand[0]
        cand.pop(0)
        
#         print(cand)
        if c in reachable:
            pass
        else:
            reachable += [c]
            cand += saiki(c, reachable)
            
    return reachable

def saiki_check(now, reachable, reachable_check_target):
#     print(now)
    cue = []
    cand = copy.deepcopy(dic[now])
    ans = False
    while len(cand) > 0:
        c = cand[0]
        cand.pop(0)
        
#         print(cand)
        if c in reachable:
            pass
        else:
            reachable += [c]
            if c == reachable_check_target:
                ans = True
                break
            out = saiki_check(c, reachable, reachable_check_target)
            cand = cand + out[0]
            ans = out[1]
            if ans:
                break
    return reachable, ans
import copy
anss = [0]
for k_start in range(1, m + 1):
    dic = {}
    for k in range(1, n+1):
        dic[k] = []
    for k in range(k_start, m):
        dic[a[k]] += [b[k]]
        dic[b[k]] += [a[k]]
    cutted = [a[k_start-1], b[k_start-1]]
    
#     print(dic)
    if saiki_check(cutted[0], [cutted[0]], cutted[1])[1]:
#     print(dic)
#     reachable = []
        s = anss[-1]
#         print('a')
    else:
        nodes = list(range(1,n+1))
        rs = []
        while len(nodes) > 0:
            reachable = saiki(nodes[0], [nodes[0]])
#             print(reachable)
            for r in reachable:
                nodes.remove(r)
            rs.append(len(reachable))
    #     print(rs)
        s = 0
        for c in combinations(rs, 2):
            s += c[0] * c[1]
        anss.append(s)
#     aaaaa
    print(s)
#     aaaaa

Buggy submission (verdict: Runtime Error):
%%time
def saiki(now, reachable):
#     print(now)
    cand = copy.deepcopy(dic[now])
    cue = []
    cand = dic[now]
    while len(cand) > 0:
        c = cand[0]
        cand.pop(0)
        
#         print(cand)
        if c in reachable:
            pass
        else:
            reachable += [c]
            cand += saiki(c, reachable)
            
    return reachable

def saiki_check(now, reachable, reachable_check_target):
#     print(now)
    cue = []
    cand = copy.deepcopy(dic[now])
    ans = False
    while len(cand) > 0:
        c = cand[0]
        cand.pop(0)
        
#         print(cand)
        if c in reachable:
            pass
        else:
            reachable += [c]
            if c == reachable_check_target:
                ans = True
                break
            out = saiki_check(c, reachable, reachable_check_target)
            cand = cand + out[0]
            ans = out[1]
            if ans:
                break
    return reachable, ans
import copy
anss = [0]
for k_start in range(1, m + 1):
    dic = {}
    for k in range(1, n+1):
        dic[k] = []
    for k in range(k_start, m):
        dic[a[k]] += [b[k]]
        dic[b[k]] += [a[k]]
    cutted = [a[k_start-1], b[k_start-1]]
    
#     print(dic)
    if saiki_check(cutted[0], [cutted[0]], cutted[1])[1]:
#     print(dic)
#     reachable = []
        s = anss[-1]
#         print('a')
    else:
        nodes = list(range(1,n+1))
        rs = []
        while len(nodes) > 0:
            reachable = saiki(nodes[0], [nodes[0]])
#             print(reachable)
            for r in reachable:
                nodes.remove(r)
            rs.append(len(reachable))
    #     print(rs)
        s = 0
        for c in combinations(rs, 2):
            s += c[0] * c[1]
        anss.append(s)
#     aaaaa
    print(s)
#     aaaaa

Buggy submission (verdict: Runtime Error):
from itertools import combinations
import numpy as np

def saiki(now, reachable):
#     print(now)
    cue = []
    cand = dic[now]
    while len(cand) > 0:
        c = cand[0]
        cand.pop(0)
        if c in reachable:
            pass
        else:
            reachable += [c]
            cand += saiki(c, reachable)
            
    return reachable

n,m = list(map(int, input().split()))
a = []
b = []
for _ in range(m):
    aa, bb = list(map(int, input().split()))
    a.append(aa)
    b.append(bb)

for k_start in range(1, m + 1):
    dic = {}
    for k in range(1, n+1):
        dic[k] = []
    for k in range(k_start, m):
        dic[a[k]] += [b[k]]
        dic[b[k]] += [a[k]]

    nodes = list(range(1,n+1))

    rs = []
    while len(nodes) > 0:
        reachable = [nodes[0]]
        reachable = saiki(nodes[0], reachable)
        for r in reachable:
            nodes.remove(r)
        rs.append(len(reachable))
#     print(rs)
    s = 0
    for c in combinations(rs, 2):
        s += c[0] * c[1]
    print(s)