Problem p03108 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import sys
# ----------------------------------------------------------------
# Use Solve Function

class UnionFind:
    def __init__(self, n):
        # ノードとリストのインデックスを一致させるために長さN+1のリストを作成
        self.par = [i for i in range(n+1)]
        self.size = [1 for i in range(n+1)]
        self.rank = [0] * (n+1)

    def __str__(self):
        return ' '.join(map(str,self.par))

    def tree_size(self, x):
        x = self.find(x)
        return self.size[x]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
# A,B = map(int, input().split(' '))
N,M = map(int, input().split(' '))
NLIST = []
for i in range(M):
    A,B = map(int, input().split(' '))
    NLIST.append((A,B))

res = N * (N-1) // 2
R = [res]
uf = UnionFind(N)

NLIST.reverse()
for i in range(M-1):
    x = NLIST[i]
    n1 = x[0]
    n2 = x[1]

    if not uf.same_check(n1,n2):
        res -= uf.tree_size(n1) * uf.tree_size(n2)
        uf.unite(n1,n2)
    R.append(res)

R.reverse()
for i in range(M):
    print(R[i])
# for i in range(M-1, -1, -1):
#     print(R[i])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
# ----------------------------------------------------------------
# Use Solve Function

class UnionFind:
    def __init__(self, n):
        # ノードとリストのインデックスを一致させるために長さN+1のリストを作成
        self.par = [i for i in range(n+1)]
        self.size = [1 for i in range(n+1)]
        self.rank = [0] * (n+1)

    def __str__(self):
        return ' '.join(map(str,self.par))

    def tree_size(self, x):
        x = self.find(x)
        return self.size[x]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

def solve(lines):
    N,M = map(int, lines.pop(0).split(' '))
    NLIST = []
    for i in range(M):
        A,B = map(int, lines.pop(0).split(' '))
        NLIST.append((A,B))

    res = N * (N-1) // 2
    R = str(res) + '\n'
    uf = UnionFind(N)

    for i in range(M-1, 0, -1):
        x = NLIST[i]
        n1 = x[0]
        n2 = x[1]

        if not uf.same_check(n1,n2):
            res -= uf.tree_size(n1) * uf.tree_size(n2)
            uf.unite(n1,n2)
        R = str(res) + '\n' + res

    print(R)
    #R.reverse()
    #for i in range(M):
    #    print(R[i])
    # for i in range(M-1, -1, -1):
    #     print(R[i])


lines = [x.strip() for x in sys.stdin.readlines()]
solve(lines)