Problem p03108 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
 
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.size = [1 for _ in range(size)]
 
	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]
 
	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
 
		return
 
n, m = map(int, input().split())
brs = [list(map(int, input().split())) for _ in range(m)]
 
uf = UnionFind(n)
ans = [n*(n-1)//2]
for i in range(m-1, 0, -1):
	a, b = brs[i][0], brs[i][1]
	a, b = a-1, b-1
	s1, s2 = uf.find(a), uf.find(b)
	if s1 != s2:
		ans.append(ans[-1] - uf.size[s1]*uf.size[s2])
	else:
		ans.append(ans[-1])
	uf.union(s1, s2)
print(*list(reversed(ans)), sep="\n")

Buggy submission (verdict: Runtime Error):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]  # 親の値が更新され、更新された親の値が返る, 返るのは正の値

    def size(self, x):
        return -self.parents[self.find(x)]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.size(x) > self.size(y):
            x, y = y, x  # 処理を行う上で、必ずxのグループの要素数の方が多くあってほしい
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
brige = []
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    brige.append((a, b))

uf = UnionFind(N)
ans = [int(N*(N-1)//2)]*M

for i in reversed(range(1, M)):
    if uf.same(brige[i][0], brige[i][1]):
        ans[i-1] = ans[i]
    else:
        ans[i-1] = ans[i] - uf.size(brige[i][0]) * uf.size(brige[i][1])
        uf.union(brige[i][0], brige[i][1])
for i in range(M):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]  # 親の値が更新され、更新された親の値が返る, 返るのは正の値

    def size(self, x):
        return -self.parents[self.find(x)]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.size(x) > self.size(y):
            x, y = y, x  # 処理を行う上で、必ずxのグループの要素数の方が多くあってほしい
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
brige = []
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    brige.append((a, b))

uf = UnionFind(N)
ans = [int(N*(N-1)//2)]*M

for i in reversed(range(1, M)):
    if uf.same(brige[i][0], brige[i][1]):
        ans[i-1] = ans[i]
    else:
        ans[i-1] = ans[i] - uf.size(brige[i][0]) * uf.size(brige[i][1])
        uf.union(brige[i][0], brige[i][1])
for i in range(M):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]  # 親の値が更新され、更新された親の値が返る, 返るのは正の値

    def size(self, x):
        return -self.parents[self.find(x)]

    def union(self, x, y):
        if self.size(x) > self.size(y):
            x, y = y, x  # 処理を行う上で、必ずxのグループの要素数の方が多くあってほしい
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
brige = []
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    brige.append((a, b))

uf = UnionFind(N)
ans = [int(N*(N-1)//2)]*M

for i in reversed(range(1, M)):
    if uf.same(brige[i][0], brige[i][1]):
        ans[i-1] = ans[i]
    else:
        ans[i-1] = ans[i] - uf.size(brige[i][0]) * uf.size(brige[i][1])
        uf.union(brige[i][0], brige[i][1])
for i in range(M):
    print(ans[i])