Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind():
    def __init__(self,size):
        self.table = [[-1,1] for _  in range(size)] # root, count
    def find(self,x):
        while self.table[x][0] >= 0:
            x = self.table[x][0]
        root = x
        while self.table[x][0] >= 0:
            x = self.table[x][0]
            self.table[x][0] = root
        return root
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1][0] != self.table[s2][0]:
                if self.table[s1][0] < self.table[s2][0]:
                    self.table[s2][0] = s1
                    self.table[s1][1] += self.table[s2][1]
                else:
                    self.table[s1][0] = s2
                    self.table[s2][1] += self.table[s1][1]
            else:
                self.table[s1][0] += -1
                self.table[s2][0] = s1
                self.table[s1][1] += self.table[s2][1]
        return


N, M = map(long, raw_input().split())
uf = UnionFind(N)
V = [map(long, raw_input().split()) for _ in range(M)]

answers = []
for v in reversed(V):
  ans = 0
  tree_sizes = []
  for t in uf.table:
    if t[0] < 0:
      tree_sizes.append(t[1])
  for i in range(len(tree_sizes)):
    for j in range(i+1, len(tree_sizes)):
      ans += tree_sizes[i]*tree_sizes[j]
  answers.append(ans)
  uf.union(v[0]-1, v[1]-1)
for a in reversed(answers):
  print a



Fixed submission:
class UnionFind():
    def __init__(self,size):
        self.table = [[-1,1] for _  in range(size)] # root, count
    def find(self,x):
        while self.table[x][0] >= 0:
            x = self.table[x][0]
        return x
    def union(self,x,y):
        szsz = 0
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            szsz = self.table[s1][1]*self.table[s2][1]
            if self.table[s1][0] != self.table[s2][0]:
                if self.table[s1][0] < self.table[s2][0]:
                    self.table[s2][0] = s1
                    self.table[s1][1] += self.table[s2][1]
                else:
                    self.table[s1][0] = s2
                    self.table[s2][1] += self.table[s1][1]
            else:
                self.table[s1][0] += -1
                self.table[s2][0] = s1
                self.table[s1][1] += self.table[s2][1]
        return szsz


N, M = map(long, raw_input().split())
uf = UnionFind(N)
V = [map(long, raw_input().split()) for _ in range(M)]

ans = N*(N-1)/2
answers = []
for v in reversed(V):
  answers.append(ans)
  szsz = uf.union(v[0]-1, v[1]-1)
  ans -= szsz
for a in reversed(answers):
  print a

Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind():
    def __init__(self,size):
        self.table = [[-1,1] for _  in range(size)] # root, count
    def find(self,x):
        while self.table[x][0] >= 0:
            x = self.table[x][0]
        return x
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1][0] != self.table[s2][0]:
                if self.table[s1][0] < self.table[s2][0]:
                    self.table[s2][0] = s1
                    self.table[s1][1] += self.table[s2][1]
                else:
                    self.table[s1][0] = s2
                    self.table[s2][1] += self.table[s1][1]
            else:
                self.table[s1][0] += -1
                self.table[s2][0] = s1
                self.table[s1][1] += self.table[s2][1]
        return


N, M = map(long, raw_input().split())
uf = UnionFind(N)
V = [map(long, raw_input().split()) for _ in range(M)]

answers = []
for v in reversed(V):
  ans = 0
  tree_sizes = []
  for t in uf.table:
    if t[0] < 0:
      tree_sizes.append(t[1])
  for i in range(len(tree_sizes)):
    for j in range(i+1, len(tree_sizes)):
      ans += tree_sizes[i]*tree_sizes[j]
  answers.append(ans)
  uf.union(v[0]-1, v[1]-1)
for a in reversed(answers):
  print a



Fixed submission:
class UnionFind():
    def __init__(self,size):
        self.table = [[-1,1] for _  in range(size)] # root, count
    def find(self,x):
        while self.table[x][0] >= 0:
            x = self.table[x][0]
        return x
    def union(self,x,y):
        szsz = 0
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            szsz = self.table[s1][1]*self.table[s2][1]
            if self.table[s1][0] != self.table[s2][0]:
                if self.table[s1][0] < self.table[s2][0]:
                    self.table[s2][0] = s1
                    self.table[s1][1] += self.table[s2][1]
                else:
                    self.table[s1][0] = s2
                    self.table[s2][1] += self.table[s1][1]
            else:
                self.table[s1][0] += -1
                self.table[s2][0] = s1
                self.table[s1][1] += self.table[s2][1]
        return szsz


N, M = map(long, raw_input().split())
uf = UnionFind(N)
V = [map(long, raw_input().split()) for _ in range(M)]

ans = N*(N-1)/2
answers = []
for v in reversed(V):
  answers.append(ans)
  szsz = uf.union(v[0]-1, v[1]-1)
  ans -= szsz
for a in reversed(answers):
  print a