Problem p03108 (python)

Fixed submission:
#!/usr/bin/env python3
import sys


class UnionFind(object):
    __slots__ = ["nodes"]

    def __init__(self, n: int):
        self.nodes = [-1]*n # 親: -(属するノード数), それ以外: (親ノードindex)

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x]) # compression
            return self.nodes[x]

    def has_same_root(self, x, y) -> bool:
        return self.find(x) == self.find(y)
    
    def size(self, x) -> int:
        return -self.nodes[self.find(x)]

    def unite(self, x: int, y: int) -> None:
        if self.has_same_root(x, y):
            return

        root_x, root_y = self.find(x), self.find(y)
        if self.nodes[root_x] < self.nodes[root_y]:
            bigroot, smallroot = (root_x, root_y)
        else: 
            bigroot, smallroot = (root_y, root_x)
        self.nodes[bigroot] += self.nodes[smallroot]
        self.nodes[smallroot] = bigroot


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    count = [0] # count[i]: 最後からi本目の橋が復活したときの互いに行き来できる島の組み合わせの数
    UFT = UnionFind(N)

    for i in range(1, M+1):
        a, b = A[-i], B[-i]
        if UFT.has_same_root(a, b):
            count.append(count[-1])
            continue
        count.append(count[-1] + UFT.size(a) * UFT.size(b))
        UFT.unite(a, b)

    for i in range(M):
        print(count[-1] - count[-(i+2)])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]" 
    B = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        A[i] = int(next(tokens))-1
        B[i] = int(next(tokens))-1
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys


class UnionFind(object):
    __slots__ = ["nodes"]

    def __init__(self, n: int):
        self.nodes = [-1]*n # 親: -(属するノード数), それ以外: (親ノードindex)

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x]) # compression
            return self.nodes[x]

    def has_same_root(self, x, y) -> bool:
        return self.find(x) == self.find(y)
    
    def size(self, x) -> int:
        return -self.nodes(self.find(x))

    def unite(self, x: int, y: int) -> None:
        if self.has_same_root(x, y):
            return

        root_x, root_y = self.find(x), self.find(y)
        if self.nodes[root_x] < self.nodes[root_y]:
            bigroot, smallroot = (root_x, root_y)
        else: 
            bigroot, smallroot = (root_y, root_x)
        self.nodes[bigroot] += self.nodes[smallroot]
        self.nodes[smallroot] = bigroot


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    count = [0] # count[i]: 最後からi本目の橋が復活したときの互いに行き来できる島の組み合わせの数
    UFT = UnionFind(N)

    for i in range(1, M+1):
        a, b = A[-i], B[-i]
        if UFT.has_same_root(a, b):
            count.append(count[-1])
            continue
        count.append(count[-1] + UFT.size(a) * UFT.size(b))
        UFT.unite(a, b)

    for i in range(M):
        print(count[-1] - count[-(i+2)])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]" 
    B = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        A[i] = int(next(tokens))-1
        B[i] = int(next(tokens))-1
    solve(N, M, A, B)

if __name__ == '__main__':
    main()