Buggy python 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()


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 python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    count = [0] # count[i]: 最後からi本目の橋が復活したときの互いに行き来できる島の組み合わせの数
    cluster_s = {i: set([i]) for i in range(N)} # クラスター: そのクラスターに所属している島
    cluster_p = [i for i in range(N)] # 各島が所属しているクラスター

    for i in range(1, M+1):
        a, b = A[-i], B[-i]
        if cluster_p[b] == cluster_p[a]:
            count.append(count[-1])
            continue
        count.append(count[-1] + len(cluster_s[cluster_p[a]]) * len(cluster_s[cluster_p[b]]))
        cluster_s[cluster_p[a]] |= cluster_s[cluster_p[b]]
        for island in cluster_s[cluster_p[b]]:
            cluster_p[island] = cluster_p[a]

    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()


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()