Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(e) for e in input().split(" ")]
d_node2setindex = {}
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
buf_sets = []
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    # print("a,b", a, b)
    if flagSkip is True:
        ans.append(0)
        continue
    
    idx_a = d_node2setindex.get(a, None)
    idx_b = d_node2setindex.get(b, None)
    # if len(buf_sets) > 0:
    #     for j, s in enumerate(buf_sets):
    #         if idx_a is None:
    #             if a in s:
    #                 idx_a = j 
    #         if idx_b is None:
    #             if b in s:
    #                 idx_b = j
    #         if idx_a is not None and idx_b is not None:
    #             break
    delta = 0
    if idx_a is None and idx_b is None:
        s_new = set([a, b])
        idx_set = len(buf_sets)
        d_node2setindex[a] = idx_set
        d_node2setindex[b] = idx_set
        buf_sets.append(s_new)
        delta = 1
    elif idx_a is not None and idx_b is None:
        delta = len(buf_sets[idx_a])
        buf_sets[idx_a].add(b)
        d_node2setindex[b] = idx_a
    elif idx_a is None and idx_b is not None:
        delta = len(buf_sets[idx_b])
        buf_sets[idx_b].add(a)
        d_node2setindex[a] = idx_b
    else:
        if idx_a != idx_b:
            s_a = buf_sets[idx_a]
            s_b = buf_sets[idx_b]
            delta = len(s_a) * len(s_b)
            [d_node2setindex.__setitem__(e, idx_a) for e in s_b]
            # for e in s_b:
            #     d_node2setindex[e] = idx_a
            # buf_sets[idx_a] = s_a | s_b
            buf_sets[idx_a].update(s_b)
            buf_sets[idx_b] = None
            # buf_sets.pop(idx_b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)


Fixed submission:
class UnionFindTree:
    def __init__(self, a_elements):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        class ZeroDict(dict):
            def __missing__(self, key):
                self[key] = 0
                return 0 

        class OneDict(dict):
            def __missing__(self, key):
                self[key] = 1 
                return 1 
        self.parents = KeyDict()
        self.ranks = ZeroDict()
        self.sizes = OneDict()

        if a_elements is not None:
            for e in a_elements:
                _ = self.parents[e]
                _ = self.ranks[e]

    def find_root(self, a_x):
        if self.parents[a_x] == a_x:
            return a_x

        self.parents[a_x] = self.find_root(self.parents[a_x])
        return self.parents[a_x]

    def unite(self, a_x, a_y):
        rx = self.find_root(a_x)
        ry = self.find_root(a_y)
        if rx == ry:
            return

        if self.ranks[rx] < self.ranks[ry]:
            self.parents[rx] = ry
            self.sizes[ry] = self.sizes[ry] + self.sizes[rx]
        else:
            self.parents[ry] = rx
            self.sizes[rx] = self.sizes[rx] + self.sizes[ry]
            if self.ranks[rx] == self.ranks[ry]:
                # find_root makes the depth of tree whose root is ry one
                # +1 indicates child ry
                self.ranks[rx] = self.ranks[rx] + 1
    
    def is_same(self, a_x, a_y):
        return self.find_root(a_x) == self.find_root(a_y)

N, M = [int(e) for e in input().split(" ")]
uft = UnionFindTree([i for i in range(1, N+1)])
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    if flagSkip is True:
        ans.append(0)
        continue
    
    ra = uft.find_root(a)
    rb = uft.find_root(b)
    delta = 0
    if ra != rb:
        size_a = uft.sizes[ra]
        size_b = uft.sizes[rb]
        delta = size_a * size_b
        uft.unite(a, b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(e) for e in input().split(" ")]
d_node2setindex = {}
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
buf_sets = []
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    # print("a,b", a, b)
    if flagSkip is True:
        ans.append(0)
        continue
    
    idx_a = d_node2setindex.get(a, None)
    idx_b = d_node2setindex.get(b, None)
    # if len(buf_sets) > 0:
    #     for j, s in enumerate(buf_sets):
    #         if idx_a is None:
    #             if a in s:
    #                 idx_a = j 
    #         if idx_b is None:
    #             if b in s:
    #                 idx_b = j
    #         if idx_a is not None and idx_b is not None:
    #             break
    delta = 0
    if idx_a is None and idx_b is None:
        s_new = set([a, b])
        idx_set = len(buf_sets)
        d_node2setindex[a] = idx_set
        d_node2setindex[b] = idx_set
        buf_sets.append(s_new)
        delta = 1
    elif idx_a is not None and idx_b is None:
        delta = len(buf_sets[idx_a])
        buf_sets[idx_a].add(b)
        d_node2setindex[b] = idx_a
    elif idx_a is None and idx_b is not None:
        delta = len(buf_sets[idx_b])
        buf_sets[idx_b].add(a)
        d_node2setindex[a] = idx_b
    else:
        if idx_a != idx_b:
            s_a = buf_sets[idx_a]
            s_b = buf_sets[idx_b]
            delta = len(s_a) * len(s_b)
            [d_node2setindex.__setitem__(e, idx_a) for e in s_b]
            # for e in s_b:
            #     d_node2setindex[e] = idx_a
            buf_sets[idx_a] = s_a | s_b
            buf_sets[idx_b] = None
            # buf_sets.pop(idx_b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)


Fixed submission:
class UnionFindTree:
    def __init__(self, a_elements):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        class ZeroDict(dict):
            def __missing__(self, key):
                self[key] = 0
                return 0 

        class OneDict(dict):
            def __missing__(self, key):
                self[key] = 1 
                return 1 
        self.parents = KeyDict()
        self.ranks = ZeroDict()
        self.sizes = OneDict()

        if a_elements is not None:
            for e in a_elements:
                _ = self.parents[e]
                _ = self.ranks[e]

    def find_root(self, a_x):
        if self.parents[a_x] == a_x:
            return a_x

        self.parents[a_x] = self.find_root(self.parents[a_x])
        return self.parents[a_x]

    def unite(self, a_x, a_y):
        rx = self.find_root(a_x)
        ry = self.find_root(a_y)
        if rx == ry:
            return

        if self.ranks[rx] < self.ranks[ry]:
            self.parents[rx] = ry
            self.sizes[ry] = self.sizes[ry] + self.sizes[rx]
        else:
            self.parents[ry] = rx
            self.sizes[rx] = self.sizes[rx] + self.sizes[ry]
            if self.ranks[rx] == self.ranks[ry]:
                # find_root makes the depth of tree whose root is ry one
                # +1 indicates child ry
                self.ranks[rx] = self.ranks[rx] + 1
    
    def is_same(self, a_x, a_y):
        return self.find_root(a_x) == self.find_root(a_y)

N, M = [int(e) for e in input().split(" ")]
uft = UnionFindTree([i for i in range(1, N+1)])
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    if flagSkip is True:
        ans.append(0)
        continue
    
    ra = uft.find_root(a)
    rb = uft.find_root(b)
    delta = 0
    if ra != rb:
        size_a = uft.sizes[ra]
        size_b = uft.sizes[rb]
        delta = size_a * size_b
        uft.unite(a, b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(e) for e in input().split(" ")]
d_node2setindex = {}
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
buf_sets = []
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    # print("a,b", a, b)
    if flagSkip is True:
        ans.append(0)
        continue
    
    idx_a = d_node2setindex.get(a, None)
    idx_b = d_node2setindex.get(b, None)
    # if len(buf_sets) > 0:
    #     for j, s in enumerate(buf_sets):
    #         if idx_a is None:
    #             if a in s:
    #                 idx_a = j 
    #         if idx_b is None:
    #             if b in s:
    #                 idx_b = j
    #         if idx_a is not None and idx_b is not None:
    #             break
    delta = 0
    if idx_a is None and idx_b is None:
        s_new = set([a, b])
        idx_set = len(buf_sets)
        d_node2setindex[a] = idx_set
        d_node2setindex[b] = idx_set
        buf_sets.append(s_new)
        delta = 1
    elif idx_a is not None and idx_b is None:
        delta = len(buf_sets[idx_a])
        buf_sets[idx_a].add(b)
        d_node2setindex[b] = idx_a
    elif idx_a is None and idx_b is not None:
        delta = len(buf_sets[idx_b])
        buf_sets[idx_b].add(a)
        d_node2setindex[a] = idx_b
    else:
        if idx_a != idx_b:
            s_a = buf_sets[idx_a]
            s_b = buf_sets[idx_b]
            delta = len(s_a) * len(s_b)
            [d_node2setindex.__setitem__(e, idx_a) for e in s_b]
            # for e in s_b:
            #     d_node2setindex[e] = idx_a
            buf_sets[idx_a] = s_a | s_b
            buf_sets[idx_b] = None
            # buf_sets.pop(idx_b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)


Fixed submission:
class UnionFindTree:
    def __init__(self, a_elements):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        class ZeroDict(dict):
            def __missing__(self, key):
                self[key] = 0
                return 0 

        class OneDict(dict):
            def __missing__(self, key):
                self[key] = 1 
                return 1 
        self.parents = KeyDict()
        self.ranks = ZeroDict()
        self.sizes = OneDict()

        if a_elements is not None:
            for e in a_elements:
                _ = self.parents[e]
                _ = self.ranks[e]

    def find_root(self, a_x):
        if self.parents[a_x] == a_x:
            return a_x

        self.parents[a_x] = self.find_root(self.parents[a_x])
        return self.parents[a_x]

    def unite(self, a_x, a_y):
        rx = self.find_root(a_x)
        ry = self.find_root(a_y)
        if rx == ry:
            return

        if self.ranks[rx] < self.ranks[ry]:
            self.parents[rx] = ry
            self.sizes[ry] = self.sizes[ry] + self.sizes[rx]
        else:
            self.parents[ry] = rx
            self.sizes[rx] = self.sizes[rx] + self.sizes[ry]
            if self.ranks[rx] == self.ranks[ry]:
                # find_root makes the depth of tree whose root is ry one
                # +1 indicates child ry
                self.ranks[rx] = self.ranks[rx] + 1
    
    def is_same(self, a_x, a_y):
        return self.find_root(a_x) == self.find_root(a_y)

N, M = [int(e) for e in input().split(" ")]
uft = UnionFindTree([i for i in range(1, N+1)])
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    if flagSkip is True:
        ans.append(0)
        continue
    
    ra = uft.find_root(a)
    rb = uft.find_root(b)
    delta = 0
    if ra != rb:
        size_a = uft.sizes[ra]
        size_b = uft.sizes[rb]
        delta = size_a * size_b
        uft.unite(a, b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(e) for e in input().split(" ")]
d_node2setindex = {}
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
buf_sets = []
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    # print("a,b", a, b)
    if flagSkip is True:
        ans.append(0)
        continue
    
    idx_a = d_node2setindex.get(a, None)
    idx_b = d_node2setindex.get(b, None)
    # if len(buf_sets) > 0:
    #     for j, s in enumerate(buf_sets):
    #         if idx_a is None:
    #             if a in s:
    #                 idx_a = j 
    #         if idx_b is None:
    #             if b in s:
    #                 idx_b = j
    #         if idx_a is not None and idx_b is not None:
    #             break
    delta = 0
    if idx_a is None and idx_b is None:
        s_new = set([a, b])
        idx_set = len(buf_sets)
        d_node2setindex[a] = idx_set
        d_node2setindex[b] = idx_set
        buf_sets.append(s_new)
        delta = 1
    elif idx_a is not None and idx_b is None:
        delta = len(buf_sets[idx_a])
        buf_sets[idx_a].add(b)
        d_node2setindex[b] = idx_a
    elif idx_a is None and idx_b is not None:
        delta = len(buf_sets[idx_b])
        buf_sets[idx_b].add(a)
        d_node2setindex[a] = idx_b
    else:
        if idx_a != idx_b:
            s_a = buf_sets[idx_a]
            s_b = buf_sets[idx_b]
            delta = len(s_a) * len(s_b)
            for e in s_b:
                d_node2setindex[e] = idx_a
            buf_sets[idx_a] = s_a | s_b
            buf_sets[idx_b] = None
            # buf_sets.pop(idx_b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

for a in reversed(ans):
    print(a)


Fixed submission:
class UnionFindTree:
    def __init__(self, a_elements):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        class ZeroDict(dict):
            def __missing__(self, key):
                self[key] = 0
                return 0 

        class OneDict(dict):
            def __missing__(self, key):
                self[key] = 1 
                return 1 
        self.parents = KeyDict()
        self.ranks = ZeroDict()
        self.sizes = OneDict()

        if a_elements is not None:
            for e in a_elements:
                _ = self.parents[e]
                _ = self.ranks[e]

    def find_root(self, a_x):
        if self.parents[a_x] == a_x:
            return a_x

        self.parents[a_x] = self.find_root(self.parents[a_x])
        return self.parents[a_x]

    def unite(self, a_x, a_y):
        rx = self.find_root(a_x)
        ry = self.find_root(a_y)
        if rx == ry:
            return

        if self.ranks[rx] < self.ranks[ry]:
            self.parents[rx] = ry
            self.sizes[ry] = self.sizes[ry] + self.sizes[rx]
        else:
            self.parents[ry] = rx
            self.sizes[rx] = self.sizes[rx] + self.sizes[ry]
            if self.ranks[rx] == self.ranks[ry]:
                # find_root makes the depth of tree whose root is ry one
                # +1 indicates child ry
                self.ranks[rx] = self.ranks[rx] + 1
    
    def is_same(self, a_x, a_y):
        return self.find_root(a_x) == self.find_root(a_y)

N, M = [int(e) for e in input().split(" ")]
uft = UnionFindTree([i for i in range(1, N+1)])
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    if flagSkip is True:
        ans.append(0)
        continue
    
    ra = uft.find_root(a)
    rb = uft.find_root(b)
    delta = 0
    if ra != rb:
        size_a = uft.sizes[ra]
        size_b = uft.sizes[rb]
        delta = size_a * size_b
        uft.unite(a, b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(e) for e in input().split(" ")]
d_node2setindex = {}
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
buf_sets = []
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    # print("a,b", a, b)
    if flagSkip is True:
        ans.append(0)
        continue
    
    idx_a = d_node2setindex.get(a, None)
    idx_b = d_node2setindex.get(b, None)
    # if len(buf_sets) > 0:
    #     for j, s in enumerate(buf_sets):
    #         if idx_a is None:
    #             if a in s:
    #                 idx_a = j 
    #         if idx_b is None:
    #             if b in s:
    #                 idx_b = j
    #         if idx_a is not None and idx_b is not None:
    #             break
    delta = 0
    if idx_a is None and idx_b is None:
        s_new = set([a, b])
        idx_set = len(buf_sets)
        d_node2setindex[a] = idx_set
        d_node2setindex[b] = idx_set
        buf_sets.append(s_new)
        delta = 1
    elif idx_a is not None and idx_b is None:
        delta = len(buf_sets[idx_a])
        buf_sets[idx_a].add(b)
        d_node2setindex[b] = idx_a
    elif idx_a is None and idx_b is not None:
        delta = len(buf_sets[idx_b])
        buf_sets[idx_b].add(a)
        d_node2setindex[a] = idx_b
    else:
        if idx_a != idx_b:
            s_a = buf_sets[idx_a]
            s_b = buf_sets[idx_b]
            delta = len(s_a) * len(s_b)
            for e in s_b:
                d_node2setindex[e] = idx_a
            buf_sets[idx_a] = s_a | s_b
            buf_sets[idx_b] = None
            # buf_sets.pop(idx_b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

for a in reversed(ans):
    print(a)


Fixed submission:
class UnionFindTree:
    def __init__(self, a_elements):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        class ZeroDict(dict):
            def __missing__(self, key):
                self[key] = 0
                return 0 

        class OneDict(dict):
            def __missing__(self, key):
                self[key] = 1 
                return 1 
        self.parents = KeyDict()
        self.ranks = ZeroDict()
        self.sizes = OneDict()

        if a_elements is not None:
            for e in a_elements:
                _ = self.parents[e]
                _ = self.ranks[e]

    def find_root(self, a_x):
        if self.parents[a_x] == a_x:
            return a_x

        self.parents[a_x] = self.find_root(self.parents[a_x])
        return self.parents[a_x]

    def unite(self, a_x, a_y):
        rx = self.find_root(a_x)
        ry = self.find_root(a_y)
        if rx == ry:
            return

        if self.ranks[rx] < self.ranks[ry]:
            self.parents[rx] = ry
            self.sizes[ry] = self.sizes[ry] + self.sizes[rx]
        else:
            self.parents[ry] = rx
            self.sizes[rx] = self.sizes[rx] + self.sizes[ry]
            if self.ranks[rx] == self.ranks[ry]:
                # find_root makes the depth of tree whose root is ry one
                # +1 indicates child ry
                self.ranks[rx] = self.ranks[rx] + 1
    
    def is_same(self, a_x, a_y):
        return self.find_root(a_x) == self.find_root(a_y)

N, M = [int(e) for e in input().split(" ")]
uft = UnionFindTree([i for i in range(1, N+1)])
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    if flagSkip is True:
        ans.append(0)
        continue
    
    ra = uft.find_root(a)
    rb = uft.find_root(b)
    delta = 0
    if ra != rb:
        size_a = uft.sizes[ra]
        size_b = uft.sizes[rb]
        delta = size_a * size_b
        uft.unite(a, b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(e) for e in input().split(" ")]
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
buf_sets = []
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    # print("a,b", a, b)
    if flagSkip is True:
        ans.append(0)
        continue
    
    idx_a = None
    idx_b = None
    if len(buf_sets) > 0:
        for j, s in enumerate(buf_sets):
            if idx_a is None:
                if a in s:
                    idx_a = j 
            if idx_b is None:
                if b in s:
                    idx_b = j
            if idx_a is not None and idx_b is not None:
                break
    delta = 0
    if idx_a is None and idx_b is None:
        s_new = set([a, b])
        buf_sets.append(s_new)
        delta = 1
    elif idx_a is not None and idx_b is None:
        delta = len(buf_sets[idx_a])
        # buf_sets[idx_a].add(a)
        buf_sets[idx_a].add(b)
    elif idx_a is None and idx_b is not None:
        delta = len(buf_sets[idx_b])
        buf_sets[idx_b].add(a)
        # buf_sets[idx_b].add(b)
    else:
        if idx_a != idx_b:
            s_a = buf_sets[idx_a]
            s_b = buf_sets[idx_b]
            delta = len(s_a) * len(s_b)
            buf_sets[idx_a] = s_a | s_b
            buf_sets.pop(idx_b)
    
    # for s in buf_sets:
    #     print(s)
    # print("---")

    # count = 0
    # for s in buf_sets:
    #     n = len(s)
    #     count = count + (n*(n-1)//2)
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

for a in reversed(ans):
    print(a)


Fixed submission:
class UnionFindTree:
    def __init__(self, a_elements):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        class ZeroDict(dict):
            def __missing__(self, key):
                self[key] = 0
                return 0 

        class OneDict(dict):
            def __missing__(self, key):
                self[key] = 1 
                return 1 
        self.parents = KeyDict()
        self.ranks = ZeroDict()
        self.sizes = OneDict()

        if a_elements is not None:
            for e in a_elements:
                _ = self.parents[e]
                _ = self.ranks[e]

    def find_root(self, a_x):
        if self.parents[a_x] == a_x:
            return a_x

        self.parents[a_x] = self.find_root(self.parents[a_x])
        return self.parents[a_x]

    def unite(self, a_x, a_y):
        rx = self.find_root(a_x)
        ry = self.find_root(a_y)
        if rx == ry:
            return

        if self.ranks[rx] < self.ranks[ry]:
            self.parents[rx] = ry
            self.sizes[ry] = self.sizes[ry] + self.sizes[rx]
        else:
            self.parents[ry] = rx
            self.sizes[rx] = self.sizes[rx] + self.sizes[ry]
            if self.ranks[rx] == self.ranks[ry]:
                # find_root makes the depth of tree whose root is ry one
                # +1 indicates child ry
                self.ranks[rx] = self.ranks[rx] + 1
    
    def is_same(self, a_x, a_y):
        return self.find_root(a_x) == self.find_root(a_y)

N, M = [int(e) for e in input().split(" ")]
uft = UnionFindTree([i for i in range(1, N+1)])
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    if flagSkip is True:
        ans.append(0)
        continue
    
    ra = uft.find_root(a)
    rb = uft.find_root(b)
    delta = 0
    if ra != rb:
        size_a = uft.sizes[ra]
        size_b = uft.sizes[rb]
        delta = size_a * size_b
        uft.unite(a, b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(e) for e in input().split(" ")]
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
buf_sets = []
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    # print("a,b", a, b)
    if flagSkip is True:
        ans.append(0)
        continue
    
    idx_a = None
    idx_b = None
    if len(buf_sets) > 0:
        for j, s in enumerate(buf_sets):
            if a in s:
                idx_a = j 
            if b in s:
                idx_b = j
            if idx_a is not None and idx_b is not None:
                break
    if idx_a is None and idx_b is None:
        s_new = set([a, b])
        buf_sets.append(s_new)
    elif idx_a is not None and idx_b is None:
        buf_sets[idx_a].add(a)
        buf_sets[idx_a].add(b)
    elif idx_a is None and idx_b is not None:
        buf_sets[idx_b].add(a)
        buf_sets[idx_b].add(b)
    else:
        if idx_a != idx_b:
            s_a = buf_sets[idx_a]
            s_b = buf_sets[idx_b]
            buf_sets[idx_a] = s_a | s_b
            buf_sets.pop(idx_b)
    
    # for s in buf_sets:
    #     print(s)
    # print("---")

    count = 0
    for s in buf_sets:
        n = len(s)
        count = count + (n*(n-1)//2)
    d = maxValue - count
    ans.append(d)
    if d == 0:
        flagSkip = True

for a in reversed(ans):
    print(a)


Fixed submission:
class UnionFindTree:
    def __init__(self, a_elements):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        class ZeroDict(dict):
            def __missing__(self, key):
                self[key] = 0
                return 0 

        class OneDict(dict):
            def __missing__(self, key):
                self[key] = 1 
                return 1 
        self.parents = KeyDict()
        self.ranks = ZeroDict()
        self.sizes = OneDict()

        if a_elements is not None:
            for e in a_elements:
                _ = self.parents[e]
                _ = self.ranks[e]

    def find_root(self, a_x):
        if self.parents[a_x] == a_x:
            return a_x

        self.parents[a_x] = self.find_root(self.parents[a_x])
        return self.parents[a_x]

    def unite(self, a_x, a_y):
        rx = self.find_root(a_x)
        ry = self.find_root(a_y)
        if rx == ry:
            return

        if self.ranks[rx] < self.ranks[ry]:
            self.parents[rx] = ry
            self.sizes[ry] = self.sizes[ry] + self.sizes[rx]
        else:
            self.parents[ry] = rx
            self.sizes[rx] = self.sizes[rx] + self.sizes[ry]
            if self.ranks[rx] == self.ranks[ry]:
                # find_root makes the depth of tree whose root is ry one
                # +1 indicates child ry
                self.ranks[rx] = self.ranks[rx] + 1
    
    def is_same(self, a_x, a_y):
        return self.find_root(a_x) == self.find_root(a_y)

N, M = [int(e) for e in input().split(" ")]
uft = UnionFindTree([i for i in range(1, N+1)])
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    if flagSkip is True:
        ans.append(0)
        continue
    
    ra = uft.find_root(a)
    rb = uft.find_root(b)
    delta = 0
    if ra != rb:
        size_a = uft.sizes[ra]
        size_b = uft.sizes[rb]
        delta = size_a * size_b
        uft.unite(a, b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)