CodeEff/ECCO huggingface dataset:
# Original solution
def comb(n):
    return n * (n - 1) // 2

class UnionFind():
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

    def cost(self):
        result = 0
        for i in range(len(self.table)):
            if self.table[i] < 0:
                result += comb(-self.table[i])
        return result


N, M = [int(i) for i in input().split()]

A = [0] * M
B = [0] * M
for i in range(M):
    A[M - i - 1], B[M - i - 1] = [int(i) - 1 for i in input().split()]

uf = UnionFind(N)

result = comb(N)
lst = [result]
for i in range(M - 1):
    uf.union(A[i], B[i])
    lst.append(result - uf.cost())

lst.reverse()

for li in lst:
    print(li)


# Optimized solution
class UnionFind:
    def __init__(self, size):
        self.data = [-1 for _ in range(size)]
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, M = [int(i) for i in input().split()]

A = [0] * M
B = [0] * M
for i in range(M):
    A[M - i - 1], B[M - i - 1] = [int(i) - 1 for i in input().split()]

uf = UnionFind(N)

result = N * (N - 1) // 2
lst = [result]
for i in range(M - 1):
    if not uf.same(A[i], B[i]):
        result -= uf.size(A[i]) * uf.size(B[i])
    lst.append(result)
    uf.union(A[i], B[i])

for i in range(M - 1, -1, -1):
    print((lst[i]))
# Original solution
N, M = [int(x) for x in input().split()]

A = []
B = []

for i in range(M):
    a, b = [int(x) for x in input().split()]
    A.append(a)
    B.append(b)

A.reverse()
B.reverse()

import math

Z = N * (N - 1) // 2

L = []
ans = []
for i in range(M):
    a, b = A[i], B[i]
    ia, ib = -1, -1
    for j in range(len(L)):
        if a in L[j]:
            ia = j
        if b in L[j]:
            ib = j
    if ia == -1 and ib == -1:
        L.append({a, b})
    elif ib != -1 and ia != -1 and ia != ib:
        L[ia] = L[ia].union(L[ib])
        del L[ib]
    elif ib != -1:
        L[ib].add(a)
    elif ia != -1:
        L[ia].add(b)
    else:
        print("Error?")

    # print(L)

    ans.append(Z - sum([(len(x) * (len(x) - 1)) // 2 for x in L]))

ans.reverse()
del ans[0]
ans.append(Z)

for a in ans:
    print(a)

# Optimized solution
import sys
sys.setrecursionlimit(100000)

N, M = [int(x) for x in input().split()]
g = 0

A = []
B = []

for i in range(M):
    a, b = [int(x) for x in input().split()]
    A.append(a)
    B.append(b)

A.reverse()
B.reverse()


# ----- Union Find -----------
PARENT = list(range( N + 1 ))
SIZE = [1] * (N + 1 )

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)


def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2
    global g
    g = g + SIZE[n2] * SIZE[n1]
    SIZE[n2] += SIZE[n1]
    SIZE[n1] = 0

Z = N * (N - 1) // 2

ans = []
for i in range(M):
    a, b = A[i], B[i]
    unite(a, b)
    # print(PARENT[1:])
    # print(SIZE[1:])
    # print(g)
    # print(Z - g)
    ans.append(Z - g)
    # print("----")

ans.reverse()
del ans[0]
for a in ans:
    print(a)
print(Z)
# Original solution
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
ab = [[int(x) for x in input().split()] for _ in range(m)][::-1]

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

from math import factorial

def cmb(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))
convinience = [0]

for i in ab:
    a, b = i
    res = convinience[-1]
    a -= 1
    b -= 1
    if find(a) == find(b):
        convinience.append(res)
        continue
    if size(a) > 1:
        res -= cmb(size(a), 2)
    if size(b) > 1:
        res -= cmb(size(b), 2)
    unite(a, b)
    res += cmb(size(a), 2)
    convinience.append(res)

convinience = convinience[1::][::-1] + [0]

ans = [0]
for i in range(m):
    ans.append(convinience[i] - convinience[i + 1] + ans[-1])
for i in ans[1:]:
    print(i)

# Optimized solution
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
ab = [[int(x) for x in input().split()] for _ in range(m)][::-1]

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

def cmb(n, k):
    return n * (n - 1) // 2
convinience = [0]

for i in ab:
    a, b = i
    res = convinience[-1]
    a -= 1
    b -= 1
    if find(a) == find(b):
        convinience.append(res)
        continue
    if size(a) > 1:
        res -= cmb(size(a), 2)
    if size(b) > 1:
        res -= cmb(size(b), 2)
    unite(a, b)
    res += cmb(size(a), 2)
    convinience.append(res)

convinience = convinience[1::][::-1] + [0]

ans = [0]
for i in range(m):
    ans.append(convinience[i] - convinience[i + 1] + ans[-1])
for i in ans[1:]:
    print(i)
# Original solution
n,m = list(map(int,input().split()))
ab = [list(map(int,input().split())) for _ in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


uf = UnionFind(n)
ans = [n*(n-1)//2]

for a,b in ab[::-1]:
    uf.union(a-1, b-1)
    tmp = n * (n-1) // 2
    for v in list(uf.all_group_members().values()):
        l = len(v)
        tmp -= l * (l-1) // 2
    ans.append(tmp)

for i in ans[-2::-1]:
    print(i)


# Optimized solution
n,m = list(map(int,input().split()))
ab = [list(map(int,input().split())) for _ in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


uf = UnionFind(n)
ans = [n*(n-1)//2]

for a,b in ab[::-1]:
    if not uf.same(a-1, b-1):
        ans.append(ans[-1] - uf.size(a-1) * uf.size(b-1))
    else:
        ans.append(ans[-1])
    uf.union(a-1, b-1)

for i in ans[-2::-1]:
    print(i)
# Original solution
n, m=list(map(int, input().split()))
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)
for i in range(m):
    a[i], b[i]=list(map(int, input().split()))
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])
    #print(g)

def Count_n_d(neighbor, start, search):
    visited = []
    stack = []
    stack.append(start)
    result = []
    while len(stack) > 0:
        next_city = stack.pop()
        if next_city in visited:
            continue
        result.append(next_city)
        visited.append(next_city)
        for nei in neighbor[next_city]:
            if nei==search:
                return [[]]                
            stack.append(nei)
    if search in result:
        return [[]]
    else:
        return [result]

def Count_n(neighbor, start, search):
    visited = []
    queue = []
    queue.append(start)
    result = []
    while len(queue) > 0:
        next_city = queue.pop(0)
        if next_city in visited:
            continue
        result.append (next_city)
        visited.append(next_city)
        for nei in neighbor[next_city]:
            queue.append(nei)
    if search in result:
        return [[]]
    else:
        return [result]
'''
print(g)
#print(Count(1,4,0))
for l in range(1,n+1):
    print('l,Count_n(g,l,0),len(Count_n(g,l,0))',l,Count_n(g,l,0),len(Count_n(g,l,0)[0]))
'''

ans=0
for i in range(m):
    g[a[i]].remove(b[i])
    g[b[i]].remove(a[i])
    cnt_a=len(Count_n(g,a[i],b[i])[0])
    if cnt_a==0:
        0
    else:
        ans+=cnt_a*len(Count_n_d(g,b[i],0)[0])
    print(ans)

# Optimized solution
import sys
sys.setrecursionlimit(100000)

n, m=list(map(int, input().split()))
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)

par=[i for i in range(n)]
cnt_con=[1 for i in range(n)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    #par[x]=root(x)
    #par[y]=root(y)
    if root(x)==root(y):
        0
    else:
        cnt_con[root(y)]+=cnt_con[root(x)]
        par[root(x)]=root(y)      
    return

for i in range(m):
    a[i], b[i]=list(map(int, input().split()))
    a[i], b[i]=a[i]-1, b[i]-1


tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
#ans[0]=0
#print('a,b=',a,b)
for i in range(m-1,-1,-1):
    ans[i]=tmp
    if root(a[i])==root(b[i]):
        0
    else:
        tmp-=cnt_con[root(a[i])]*cnt_con[root(b[i])]
    connect(a[i],b[i])
    #print('i,tmp',i,(a[i],b[i]),ans[i],tmp,par,cnt_con)
    

    
for i in range(m):
    print((ans[i]))
# Original solution
import itertools

n, m = list(map(int, input().split()))
pair = []
for i in range(m):
	pair.append(list(map(int, input().split())))
ans = []

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

u = UnionFind(n)
l = []
for i in range(1, n + 1):
	l.append(i)
c = list(itertools.combinations(l, 2))
for i in range(1, m + 1):
	count = 0
	for j in range(len(c)):
		if u.same_check(int(c[j][0]), int(c[j][1])) == False:
			count += 1
	ans.append(count)
	u.union(pair[-i][0], pair[-i][1])

ans.sort()
for i in range(m):
	print((ans[i]))

# Optimized solution
n, m = list(map(int, input().split()))
pair = []
for i in range(m):
	pair.append(list(map(int, input().split())))
pair = pair[::-1]
ans = []
ans.append(int(n*(n-1)/2))

class UnionFind:
    def __init__(self, n):
        self.par = [-1] * (n+1)
        self.rank = [0] * (n+1)

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

    def size(self, x):
        return -self.par[self.find(x)]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.size(x) < self.size(y):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        return

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

u = UnionFind(n)
for i in range(len(pair) - 1):
    if u.find(pair[i][0]) != u.find(pair[i][1]):
        ans.append(max(0, int(ans[i] - u.size(pair[i][0]) * u.size(pair[i][1]))))
    else:
        ans.append(ans[i])
    u.union(pair[i][0], pair[i][1])
ans = ans[::-1]
for i in range(len(ans)):
    print((ans[i]))
# Original solution
def top(L, node):
    current = node
    while L[current] != current:
        current = L[current]
    return current


def main():
    n, m = list(map(int, input().rstrip("\n").split(" ")))

    L = [0]
    counts = {}
    for i in range(1, n + 1):
        L.append(i)
        counts[i] = 1

    edges = []
    for j in range(m):
        a_b = list(map(int, input().rstrip("\n").split(" ")))
        edges.append(a_b)

    total = n * (n - 1) // 2

    answers = [total]
    for a, b in reversed(edges):
        a_top = top(L, a)
        b_top = top(L, b)
        if a_top == b_top:
            answers.append(total)
        else:
            total -= counts[a_top] * counts[b_top]
            answers.append(total)
            L[b_top] = a_top
            counts[a_top] += counts[b_top]


    for answer in reversed(answers[:-1]):
        print(answer)

if __name__ == '__main__':
    main()

# Optimized solution
def main():
    n, m = list(map(int, input().rstrip("\n").split(" ")))

    L = [0]
    counts = {}
    for i in range(1, n + 1):
        L.append(i)
        counts[i] = 1

    edges = []
    for j in range(m):
        a_b = list(map(int, input().rstrip("\n").split(" ")))
        edges.append(a_b)

    total = n * (n - 1) // 2

    answers = [total]
    for a, b in reversed(edges):
        current = a
        while L[current] != current:
            current = L[current]
        a_top = current
        current = b
        while L[current] != current:
            current = L[current]
        b_top = current
        if a_top == b_top:
            answers.append(total)
        else:
            total -= counts[a_top] * counts[b_top]
            answers.append(total)
            L[b_top] = a_top
            L[b] = a_top
            L[a] = a_top
            counts[a_top] += counts[b_top]

    for answer in reversed(answers[:-1]):
        print(answer)

if __name__ == '__main__':
    main()
# Original solution
class DisjointSet:
    def __init__(self,n):
        self.rank = [0]*n
        self.parent = [i for i in range(n)]
        self.siz = [1]*n

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

    def unite(self,x,y): 
        return self.link(self.findSet(x), self.findSet(y))

    def link(self,x,y):
        if self.rank[x] > self.rank[y]: 
            self.parent[y] = x
            self.siz[x] += self.siz[y]
        else:
            self.parent[x] = y
            self.siz[y] += self.siz[x]
            if self.rank[x] == self.rank[y]: self.rank[y] += 1

    def findSet(self,x):
        if x != self.parent[x]: 
            self.parent[x] = self.findSet(self.parent[x])
        return self.parent[x]

    def size(self,x):
        return self.siz[self.findSet(x)]

n,m = list(map(int,input().split()))
brg = [[int(i)-1 for i in input().split()] for _ in range(m)]
cnt = n*(n-1)//2
ans = [0]*m
ds = DisjointSet(n)
for i in range(m)[::-1]:
    ans[i] = cnt
    a,b = brg[i]
    if not ds.same(a,b):
        cnt -= ds.size(a)*ds.size(b)
        ds.unite(a,b)
print(("\n".join(map(str,ans))))

# Optimized solution
class DisjointSet:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.siz = [1]*n

    def root(self,x):
        if x != self.parent[x]: 
            self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

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

    def unite(self,x,y): 
        x = self.root(x)
        y = self.root(y)
        if x == y: 
            return
        if self.siz[x] < self.siz[y]: 
            x,y = y,x
        self.parent[y] = x
        self.siz[x] += self.siz[y]

    def size(self,x):
        return self.siz[self.root(x)]

n,m = list(map(int,input().split()))
brg = [[int(i)-1 for i in input().split()] for _ in range(m)]
cnt = n*(n-1)//2
ans = [0]*m
ds = DisjointSet(n)
for i in range(m)[::-1]:
    ans[i] = cnt
    a,b = brg[i]
    if not ds.same(a,b):
        cnt -= ds.size(a)*ds.size(b)
        ds.unite(a,b)
print(("\n".join(map(str,ans))))
# Original solution
n,m = [int(i) for i in input().split()]
ab = []
for i in range(m):
  ab.append([int(i)-1 for i in input().split()])

def find_index(c,eld):
  if c in eld[c]:
    return(c,len(eld[c]))
  else:
    return(eld[c][0],len(eld[eld[c][0]]))
           
eld = []
for i in range(n):
  eld.append([i])
stat = eld
ans = [int(len(eld)*(len(eld)-1)/2)]

for a,b in ab[1:][::-1]:
#  print(eld)
  a_index,a_size = find_index(a,eld)
  b_index,b_size = find_index(b,eld)
#  print(a_index,b_index)
  if a_index == b_index:
    ans.append(ans[-1])
    continue
  else:
    next = a_size * b_size
    ans.append(ans[-1] - next)

  if a_size >= b_size:
    eld[a_index].extend(eld[b_index])
    for i in eld[a_index][1:]:
      eld[i] = [a_index]
  else:
    eld[b_index].extend(eld[a_index])
    for i in eld[b_index][1:]:
      eld[i] = [b_index]

for i in ans[::-1]:
  print(i)

# Optimized solution
n,m = [int(i) for i in input().split()]
ab = []
for i in range(m):
  ab.append([int(i)-1 for i in input().split()])

def find_index(c,eld):
  if c in eld[c]:
    return(c,len(eld[c]))
  else:
    return(eld[c][0],len(eld[eld[c][0]]))
           
eld = []
for i in range(n):
  eld.append([i])
stat = eld
ans = [int(len(eld)*(len(eld)-1)/2)]

for a,b in ab[1:][::-1]:
#  print(eld)
  a_index,a_size = find_index(a,eld)
  b_index,b_size = find_index(b,eld)
#  print(a_index,b_index)
  if a_index == b_index:
    ans.append(ans[-1])
    continue
  else:
    next = a_size * b_size
    ans.append(ans[-1] - next)

  if a_size >= b_size:
    eld[a_index].extend(eld[b_index])
    for i in eld[b_index]:
      eld[i] = [a_index]
  else:
    eld[b_index].extend(eld[a_index])
    for i in eld[a_index]:
      eld[i] = [b_index]

for i in ans[::-1]:
  print(i)
# Original solution

import sys
import collections

n, m = list(map(int, sys.stdin.readline().split()))
p = list(range(n))
r = [1] * n


def li_(): return [int(x)-1 for x in sys.stdin.readline().split()]


def find(x):
    global p
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]


def union(x, y):
    x, y = find(x), find(y)
    if y > x:
        x, y = y, x
    p[y] = x
    r[x] += r[y]
    r[y] = r[x]


flist = [0] * m
elist = [0] * m
for i in range(m):
    flist[i], elist[i] = li_()

flist.reverse()
elist.reverse()

ans = [0] * m
ans[0] = int(n*(n-1)/2)

for i in range(m-1):
    a, b = flist[i], elist[i]
    if find(a) != find(b):
        ans[i + 1] = ans[i] - r[find(a)]*r[find(b)]
        union(a, b)
    else:
        ans[i+1] = ans[i]
    if ans[i+1] == 0:
        break

for i in range(m):
    print((ans[m-i-1]))


# Optimized solution

import sys
import collections

n, m = list(map(int, sys.stdin.readline().split()))
p = list(range(n))
r = [1] * n


def li_(): return [int(x)-1 for x in sys.stdin.readline().split()]


def find(x):
    global p
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]


def union(x, y):
    x, y = find(x), find(y)
    if y > x:
        x, y = y, x
    p[y] = x
    r[x] += r[y]
    r[y] = r[x]


flist = [0] * m
elist = [0] * m
for i in range(m):
    flist[i], elist[i] = li_()

flist.reverse()
elist.reverse()

ans = [0] * m
ans[-1] = int(n*(n-1)/2)

for i in range(m-1):
    a, b = flist[i], elist[i]
    if find(a) != find(b):
        ans[-i-2] = ans[-i-1] - r[find(a)]*r[find(b)]
        union(a, b)
    else:
        ans[-i-2] = ans[-i-1]
    if ans[-i-2] == 0:
        break

for i in range(m):
    print((ans[i]))