Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict
from collections import deque


class UnionFindTree:
    '''
    Union Find Tree
    '''

    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


_ncr = {}


def ncr(n, r):
    if n < r:
        return 0
    k = "{}:{}".format(n, r)
    if k not in _ncr:
        _ncr[k] = math.factorial(n) // (math.factorial(n - r) *
                                        math.factorial(r))
    return _ncr[k]


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = ncr(N, 2)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += ncr(nx, 2) + ncr(ny, 2)
        total -= ncr(n, 2)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Fixed submission:
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}

    def make(self, x):
        self.p[x] = x

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if x >= y:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            return x


_ncr = {}


def ncr(n, r):
    if n < r:
        return 0
    k = "{}:{}".format(n, r)
    if k not in _ncr:
        _ncr[k] = math.factorial(n) // (math.factorial(n - r) *
                                        math.factorial(r))
    return _ncr[k]


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = ncr(N, 2)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += ncr(nx, 2) + ncr(ny, 2)
        total -= ncr(n, 2)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Fixed submission:
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}

    def make(self, x):
        self.p[x] = x

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if x >= y:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            return x


_ncr = {}


def ncr(n, r):
    if n < r:
        return 0
    k = "{}:{}".format(n, r)
    if k not in _ncr:
        _ncr[k] = math.factorial(n) // (math.factorial(n - r) *
                                        math.factorial(r))
    return _ncr[k]


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = ncr(N, 2)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    
    if x != y:
        n = h.get(x, 1) + h.get(y, 1)
        total += ncr(h.get(x, 1), 2) + ncr(h.get(y, 1), 2)
        total -= ncr(n, 2)

        if x in h:
            del h[x]
        if y in h:
            del h[y]
        h[a] = n
    

for v in ans:
    print(v)

Fixed submission:
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}

    def make(self, x):
        self.p[x] = x

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if x >= y:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            return x


_ncr = {}


def ncr(n, r):
    if n < r:
        return 0
    k = "{}:{}".format(n, r)
    if k not in _ncr:
        _ncr[k] = math.factorial(n) // (math.factorial(n - r) *
                                        math.factorial(r))
    return _ncr[k]


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.reverse()

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = []
total = ncr(N, 2)
now = 0
for i in range(M):
    ans.append(total)

    a, b = ab[i]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        n = h.get(x, 1) + h.get(y, 1)
        total += ncr(h.get(x, 1), 2) + ncr(h.get(y, 1), 2)
        total -= ncr(n, 2)

        if x in h:
            del h[x]
        if y in h:
            del h[y]
        h[a] = n

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

Fixed submission:
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}

    def make(self, x):
        self.p[x] = x

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if x >= y:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            return x


_ncr = {}


def ncr(n, r):
    if n < r:
        return 0
    k = "{}:{}".format(n, r)
    if k not in _ncr:
        _ncr[k] = math.factorial(n) // (math.factorial(n - r) *
                                        math.factorial(r))
    return _ncr[k]


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.reverse()

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = []
total = ncr(N, 2)
now = 0
for i in range(M):
    ans.append(total)

    a, b = ab[i]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        n = h.get(x, 1) + h.get(y, 1)
        total += ncr(h.get(x, 1), 2) + ncr(h.get(y, 1), 2)
        total -= ncr(n, 2)

        if x in h:
            del h[x]
        if y in h:
            del h[y]
        h[a] = n

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

Fixed submission:
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}

    def make(self, x):
        self.p[x] = x

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if x >= y:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            return x


def ncr(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.reverse()

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = []
total = ncr(N, 2)
now = 0
for i in range(M):
    ans.append(total)

    a, b = ab[i]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        n = h.get(x, 1) + h.get(y, 1)
        total += ncr(h.get(x, 1), 2) + ncr(h.get(y, 1), 2)
        total -= ncr(n, 2)

        if x in h:
            del h[x]
        if y in h:
            del h[y]
        h[a] = n

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

Fixed submission:
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def ncr(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.reverse()

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = []
total = ncr(N, 2)
for i in range(M):
    now = 0
    for k, v in h.items():
        now += ncr(v, 2)
    ans.append(total - now)

    a, b = ab[i]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        n = h.get(x, 1) + h.get(y, 1)
        if x in h:
            del h[x]
        if y in h:
            del h[y]
        h[a] = n

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

Fixed submission:
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def ncr(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.reverse()

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = []
total = ncr(N, 2)
for i in range(M):
    now = 0
    for k, v in h.items():
        now += ncr(v, 2)
    ans.append(total - now)

    a, b = ab[i]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        n = h.get(x, 1) + h.get(y, 1)
        h[x] = 0
        h[y] = 0
        h[a] = n

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

Fixed submission:
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def ncr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.reverse()

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

ans = []
total = ncr(N, 2)
for i in range(M):
    h = defaultdict(int)
    for k in utf.p.keys():
        h[utf.find(k)] += 1

    now = 0
    for k, v in h.items():
        if v > 1:
            now += ncr(v, 2)
    ans.append(total - now)
    utf.unite(*ab[i])

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

Fixed submission:
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def ncr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.reverse()

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

ans = []
total = ncr(N, 2)
for i in range(M):
    h = defaultdict(int)
    for k in utf.p.keys():
        h[utf.find(k)] += 1

    now = 0
    for k, v in h.items():
        if v > 1:
            now += ncr(v, 2)
    ans.append(total - now)
    utf.unite(*ab[i])

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

Fixed submission:
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)