Problem p03108 (python)

Fixed submission:
import sys
input = sys.stdin.readline


class UnionFind:
    def __init__(self, N):
        self.Parent = [-1]*(N+1)
    #Aの親を探す。このときParent[A]は親の値からグループサイズに変わる。探索の最適化
    def root(self, A):
        if self.Parent[A] < 0: return A
        self.Parent[A] = self.root(self.Parent[A])
        return self.Parent[A]
    #Aが属しているグループのサイズを求める
    def size(self, A):
        return -self.Parent[self.root(A)]
    
    def connect(self,A,B):
        A = self.root(A)
        B = self.root(B)
        if A == B: return False
        
        if self.size(A) < self.size(B): A,B = B,A
        self.Parent[A] += self.Parent[B]
        self.Parent[B] = A
        return True



N,M = map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
Uni = UnionFind(N)
ans = [-1]*(M)
ans[M-1] = N*(N-1)//2 
for i in reversed(range(1,M)):
    ans[i-1] = ans[i]
    if Uni.root(AB[i][0]) != Uni.root(AB[i][1]):
        ans[i-1] -= Uni.size(AB[i][0])*Uni.size(AB[i][1])
    Uni.connect(AB[i][0], AB[i][1])
for i in range(M):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, M = map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

class UnionFind:
    def __init__(self, N):
        self.Parent = [-1]*N

    def root(self, A):
        if self.Parent[A] < 0: return A
        self.Parent[A] = self.root(self.Parent[A])
        return self.Parent[A]
    
    def size(self, A):
        return -self.Parent[self.root(A)]
    
    def connect(self, A, B):
        if self.root(A) == self.root(B): return False
        if self.size(A) < self.size(B): A,B = B,A

        self.Parent[A] += self.Parent[B]
        self.Parent[B] = self.root(A)
        return True

Uni = UnionFind(N+1)
ans = [0]*(M)
ans[M-1] = N*(N-1)//2

for i in reversed(range(1, M)):
    ans[i-1] = ans[i]
    if Uni.root(AB[i][0]) != Uni.root(AB[i][1]):
        ans[i-1] -= Uni.size(AB[i][0])*Uni.size(AB[i][1])
        Uni.connect(AB[i][0],AB[i][1])
for i in range(M):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, M = map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

class UnionFind:
    def __init__(self, N):
        self.Parent = [-1]*N

    def root(self, A):
        if self.Parent[A] < 0: return A
        self.Parent[A] = self.root(self.Parent[A])
        return self.Parent[A]
    
    def size(self, A):
        return -self.Parent[self.root(A)]
    
    def connect(self, A, B):
        if self.root(A) == self.root(B): return False
        if self.size(A) < self.size(B): A,B = B,A

        self.Parent[A] += self.Parent[B]
        self.Parent[B] = A
        return True

Uni = UnionFind(N+1)
ans = [0]*(M)
ans[M-1] = N*(N-1)//2

for i in reversed(range(1, M)):
    ans[i-1] = ans[i]
    if Uni.root(AB[i][0]) != Uni.root(AB[i][1]):
        ans[i-1] -= Uni.size(AB[i][0])*Uni.size(AB[i][1])
    Uni.connect(AB[i][0],AB[i][1])
for i in range(M):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, M = map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

class UnionFind:
    def __init__(self, N):
        self.Parent = [-1]*N

    def root(self, A):
        if self.Parent[A] < 0: return A
        self.Parent[A] = self.root(self.Parent[A])
        return self.Parent[A]
    
    def size(self, A):
        return -self.Parent[self.root(A)]
    
    def connect(self, A, B):
        if self.root(A) == self.root(B): return False
        if self.size(A) < self.size(B): A,B = B,A

        self.Parent[A] += self.Parent[B]
        self.Parent[B] = A
        return True

Uni = UnionFind(N+1)
ans = [0]*(M)
ans[M-1] = N*(N-1)//2

for i in reversed(range(1, M)):
    ans[i-1] = ans[i]
    if Uni.root(AB[i][0]) != Uni.root(AB[i][1]):
        ans[i-1] -= Uni.size(AB[i][0])*Uni.size(AB[i][1])
        Uni.connect(AB[i][0],AB[i][1])
for i in range(M):
    print(ans[i])