CodeEff/ECCO huggingface dataset:
# Original solution
from collections import Counter

maxn = 100000

n , m = list(map(int, input().split()))

par = [0] * n
rank = [0] * n

#初期化
for i in range(n):
    par[i] = i
    rank[i] = 0

#判定(一番上野根を求める)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
#結合
def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1

a = [0] * m
b = [0] * m
for i in range(m):
    a[i],b[i] = list(map(int,input().split()))
    a[i] -= 1
    b[i] -= 1
    
nn = [0]*(maxn+1)
for i in range(maxn+1):
    nn[i] = i * (i-1) // 2
    
dis = [0]*m
for i in range(m-1,-1,-1):
    ans = n*(n-1) // 2
    l = [find(j) for j in range(n)]
    ll = Counter(l)
    values, counts = list(zip(*ll.most_common()))
    for j in counts:
        ans -= nn[j]
    dis[i] = ans
    unite(a[i],b[i])
    
for i in range(m):
    print((dis[i]))

# Optimized solution
maxn = 100000

n , m = list(map(int, input().split()))

par = [0] * n
rank = [0] * n
siz = [1] * n

#初期化
for i in range(n):
    par[i] = i
    rank[i] = 0

#判定(一番上野根を求める)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
#結合
def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
        siz[ry] += siz[rx]
        siz[rx] = 0
    elif rank[rx] > rank[ry]:
        par[ry] = rx
        siz[rx] += siz[ry]
        siz[ry] = 0
    else:
        par[ry] = x
        siz[rx] += siz[ry]
        siz[ry] = 0
        rank[rx] += 1

a = [0] * m
b = [0] * m
for i in range(m):
    a[i],b[i] = list(map(int,input().split()))
    a[i] -= 1
    b[i] -= 1
    
nn = [0]*(maxn+1)
for i in range(maxn+1):
    nn[i] = i * (i-1) // 2
    
dis = [0]*m
ans = n*(n-1) // 2
dis[m-1] = ans
for i in range(m-1,0,-1):
    if find(a[i]) == find(b[i]):
        dis[i-1] = ans
    else:
        ans -= (siz[find(a[i])] * siz[find(b[i])])
        dis[i-1] = ans
        
    unite(a[i],b[i])
    
for i in range(m):
    print((dis[i]))
# Original solution
N,M=list(map(int,input().split()))
tree=[[]for i in range(N)]
bridge=[]
for i in range(M):
    A,B=list(map(int,input().split()))
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)
    bridge.append((A,B))
ans=[]
All=N*(N-1)//2
for a,b in bridge:
    ischecked=[0]*N
    tree[a-1].pop(0)
    tree[b-1].pop(0)
    x=0
    for i in range(N):
        if ischecked[i]==1:
            continue
        count=0
        q=[i]
        while q:
            now=q.pop()
            if ischecked[now]==1:
                continue
            ischecked[now]=1
            q.extend(tree[now])
            count+=1
        x+=count*(count-1)//2
    ans.append(All-x)
for i in ans:
    print(i)

# Optimized solution
N,M=list(map(int,input().split()))
bridge=[]
size=[1]*(N+1)
tree=list(range(N+1))
def find(a):
    x=tree[a]
    if a==x:
        return a
    y=find(x)
    tree[a]=y
    return y
for i in range(M):
    A,B=list(map(int,input().split()))
    bridge.append((A,B))
Ans=N*(N-1)//2
ans=[]
for a,b in bridge[::-1]:
    aroot=find(a)
    broot=find(b)
    if aroot==broot:
        ans.append(Ans)
        continue
    ans.append(Ans)
    sa=size[aroot]
    sb=size[broot]
    Ans-=sa*sb
    if sa>sb:
        tree[broot]=aroot
        size[aroot]+=sb
    else:
        tree[aroot]=broot
        size[broot]+=sa
for i in ans[::-1]:
    print(i)
# Original solution
import sys
sys.setrecursionlimit(2000)
n, m = map(int, input().split())
bridge = list(map(int, sys.stdin.read().split()))
total = n*(n-1)//2
ans =[total]
u = [-1]*(n+1)
size = [1]*(n+1)
rank = [1]*(n+1)
def check(x, y):
    return find(x) != find(y)

def find(x):
    if u[x] < 0 :
        u[x] = x
        return x
    else:
        return u[x]

for x , y in zip(bridge[-2::-2],bridge[::-2]):
    if check(x, y):
        X = find(x)
        Y = find(y)
        total -= size[X] * size[Y]
        ans += [total]
        if rank[X] == rank[Y]:
            u = [Y if x == X else x for x in u]
            rank =[x+1 if u[i] == Y else x for i, x in enumerate(rank)]
        else:
            if rank[X] > rank[Y]:
                X, Y = Y, X
            rank =[x+1 if u[i] == X else x for i, x in enumerate(rank)]
            u = [Y if x == X else x for x in u]
        size[Y] += size[X]

    else:
        ans += [total]

print(*ans[-2::-1], sep="\n")


# Optimized solution
import sys
n , m, *e = map(int,sys.stdin.read().split())
total = n*(n-1)//2
ans =[total]
u = [-1]*(n+1)

def find(x):
    if u[x] < 0 :
        return x
    else:
        return find(u[x])

for x , y in zip(e[-2:1:-2],e[:1:-2]):
    x = find(x)
    y = find(y)
    x, y = sorted((x, y))
    if x != y:
        total -= u[x] * u[y]
        u[x] += u[y]
        u[y] = x
    ans += [total]

print(*ans[::-1], sep="\n")
# Original solution
import sys
input = sys.stdin.readline

#木の根を求める
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x]==rank[y]:
                rank[x] += 1

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

########################################
#初期化
n,m = list(map(int,input().split()))

par = [0]*n #親
for i in range(n):
    par[i] = i
rank = [1]*n #深さ
size = [1]*n #size[i]:iを根とするグループのサイズ
edge2 = [[0] for i in range(m)]
for i in range(m):
    edge2[i] = list(map(int,input().split()))

edge = [[0] for i in range(m)]
for i in range(m):
    edge[i] = [edge2[m-1-i][0]-1,edge2[m-1-i][1]-1]
res = []
for i in range(m):
    fi = find(edge[i][0])
    se = find(edge[i][1])
    if fi == se:
        res.append(0)
    else:
        res.append(size[fi]*size[se])
        unite(fi,se)
ass = 0
for i in range(m):
    ass += res[m-1-i]
    print(ass)


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

#木の根を求める
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x]==rank[y]:
                rank[x] += 1

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

########################################
#初期化
n,m = list(map(int,input().split()))

par = [0]*n #親
for i in range(n):
    par[i] = i
rank = [1]*n #深さ
size = [1]*n #size[i]:iを根とするグループのサイズ

edge = [tuple(map(int,input().split())) for i in range(m)]
edge = edge[::-1]
for i in range(m):
    edge[i] = (edge[i][0]-1,edge[i][1]-1)

res = []
for i in range(m):
    fi = find(edge[i][0])
    se = find(edge[i][1])
    if fi == se:
        res.append(0)
    else:
        res.append(size[fi]*size[se])
        unite(fi,se)
ass = 0
for i in range(m):
    ass += res[m-1-i]
    print(ass)
# Original solution
import sys
input = sys.stdin.readline

#木の根を求める
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x]==rank[y]:
                rank[x] += 1

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

########################################
#初期化
n,m = list(map(int,input().split()))

par = [0]*n #親
for i in range(n):
    par[i] = i
rank = [1]*n #深さ
size = [1]*n #size[i]:iを根とするグループのサイズ

edge = [tuple(map(int,input().split())) for i in range(m)]
edge = edge[::-1]
for i in range(m):
    edge[i] = (edge[i][0]-1,edge[i][1]-1)

res = []
for i in range(m):
    fi = find(edge[i][0])
    se = find(edge[i][1])
    if fi == se:
        res.append(0)
    else:
        res.append(size[fi]*size[se])
        unite(fi,se)
ass = 0
for i in range(m):
    ass += res[m-1-i]
    print(ass)


# Optimized solution
#Union Find
import sys
input = sys.stdin.readline
 
n,m = list(map(int,input().split()))

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

#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:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x

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

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


edge = [tuple(map(int,input().split())) for i in range(m)]
edge = edge[::-1]
for i in range(m):
    edge[i] = (edge[i][0]-1,edge[i][1]-1)

res = []
for i in range(m):
    fi = find(edge[i][0])
    se = find(edge[i][1])
    if fi == se:
        res.append(0)
    else:
        res.append(size(fi)*size(se))
        unite(fi,se)
ass = 0
for i in range(m):
    ass += res[m-1-i]
    print(ass)
# Original solution
import collections

N, M = list(map(int, input().split()))
bridges = reversed([[int(i) for i in input().split()] for i in range(M)])

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

    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 x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            _y = self.par[y]
            for i in range(N):
              if self.par[i] == _y: self.par[i] = x

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

def solve():
  uf = UnionFind(N)
  ans = [str(N * (N - 1) // 2)]
  for bridge in bridges:
    uf.union(bridge[0] - 1, bridge[1] - 1)
    C = collections.Counter(uf.par)
    n = N
    a = 0
    for c in list(C.values()):
      n -= c
      a += n * c
    ans.append(str(a))
  ans.pop(-1)
  return '\n'.join(reversed(ans))

print((solve()))


# Optimized solution
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)

    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]

def solve():
    N, M = list(map(int, input().split()))
    bridges = [[int(i) - 1 for i in input().split()] for i in range(M)]
    ans = [N * (N - 1) // 2]

    uf = UnionFind(N)
    for bridge in reversed(bridges):
        A, B = bridge
        if uf.issame(A, B):
            ans.append(ans[-1])
        else:
            ans.append(ans[-1] - uf.size(A) * uf.size(B))
            uf.merge(A, B)
    ans.pop(-1)
    return '\n'.join(map(str, reversed(ans)))

print((solve()))
# Original solution
class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -1

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

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return 
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return self.root[self.Find_Root(x)] * (-1)

N, M = list(map(int, input().split()))
a, b = [],[]
for _ in range(M):
	at, bt = list(map(int, input().split()))
	a.append(at)
	b.append(bt)

solve = UnionFind(N)
ans = [0]
for i in reversed(list(range(M))):
	tmp = 0
	solve.Unite(a[i], b[i])
	for i in range(1,N+1):
		if solve.root[i] < -1:
			t = solve.root[i]*(-1)
			tmp += t*(t-1)//2
	ans.append(tmp)
			
tot = N*(N-1)//2

for i in range(1,len(ans)):
	print((tot-ans[-(i+1)]))

# Optimized solution
class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -1

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

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return 
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return self.root[self.Find_Root(x)] * (-1)

N, M = list(map(int, input().split()))
a, b = [],[]
for _ in range(M):
	at, bt = list(map(int, input().split()))
	a.append(at)
	b.append(bt)

solve = UnionFind(N)
ans = [0]
for i in reversed(list(range(M))):
	ca,cb = a[i],b[i]
	if solve.isSameGroup(ca,cb):
		ans.append(ans[-1])
		continue
	num_group_a = solve.Count(ca)
	num_group_b = solve.Count(cb)
	tmp = num_group_a * num_group_b
	solve.Unite(ca, cb)
	ans.append(ans[-1]+tmp)
			
tot = N*(N-1)//2

for i in range(2,M+2):
	print((tot-ans[-i]))
# Original solution
#!/usr/bin/env python3

from itertools import product


def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    for _ in range(m):
        ai, bi = list(map(int, input().split()))
        a.append(ai-1)
        b.append(bi-1)

    # 不便さのMAX
    result = [n * (n-1) // 2]

    chained = [{i} for i in range(n)]
    for j in range(m):
        i = m - 1 - j
        ai = a[i]
        bi = b[i]
        if ai not in chained[bi]:
            next_val = result[-1]
            for ac, bc in product(chained[ai], chained[bi]):
                chained[ac].add(bc)
                chained[bc].add(ac)
                next_val -= 1
            result.append(next_val)
        else:
            result.append(result[-1])
    result.reverse()
    for v in result[1:]:
        print(v)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3

from itertools import product


def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    for _ in range(m):
        ai, bi = list(map(int, input().split()))
        a.append(ai-1)
        b.append(bi-1)

    # 不便さのMAX
    result = [n * (n-1) // 2]
    labels = [i for i in range(n)]
    groups = {}
    for i in range(n):
        groups[i] = {i}


    for j in range(m):
        i = m - 1 - j
        ai = a[i]
        bi = b[i]
        if labels[ai] != labels[bi]:
            next_val = result[-1]
            label_a = labels[ai]
            label_b = labels[bi]
            next_val -= len(groups[label_a]) * len(groups[label_b])
            result.append(next_val)
            groups[label_a] |= groups[label_b]
            for bx in groups[label_b]:
                labels[bx] = labels[ai]
            del groups[label_b]
        else:
            result.append(result[-1])

    result.reverse()
    for v in result[1:]:
        print(v)

if __name__ == '__main__':
    main()
# Original solution
N, M = list(map(int, input().split()))
ab = [tuple([int(x)-1 for x in input().split()]) for _ in range(M)]


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

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab[1:]):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.number[px] * uf.number[py]
            uf.union(px, py)
        ans.append(p)

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


main()

# Optimized solution
import sys

N, M = list(map(int, input().split()))
ab = [tuple([int(x)-1 for x in sys.stdin.readline().split()]) for _ in range(M)]


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

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab[1:]):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.number[px] * uf.number[py]
            uf.union(px, py)
        ans.append(p)

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


main()
# Original solution
import sys
from itertools import combinations

# https://ikatakos.com/pot/programming_algorithm/data_structure/union_find_tree
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.n = n
        self.max_inconvenience = n * (n - 1) // 2

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def inconvenience(self):
        res = self.max_inconvenience
        for i, j in combinations(list(range(self.n)), 2):
            if self.find(i, j):
                res -= 1
        return res

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def main():
    input = sys.stdin.buffer.readline
    n, m = list(map(int, input().split()))
    bridges = [tuple([int(x) - 1 for x in input().split()]) for _ in range(m)]
    ans = [0] * m
    ans[-1] = n * (n - 1) // 2
    uf = UnionFind(n)
    for i in range(m - 2, -1, -1):
        uf.union(*bridges[i + 1])
        ans[i] = uf.inconvenience()
    for i in range(m):
        print((ans[i]))


if __name__ == "__main__":
    main()


# Optimized solution
import sys
from itertools import combinations

# https://ikatakos.com/pot/programming_algorithm/data_structure/union_find_tree
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
        self.n = n
        self.inconvenience = n * (n - 1) // 2

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        self.inconvenience -= d1 * d2
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    input = sys.stdin.buffer.readline
    n, m = list(map(int, input().split()))
    bridges = [tuple([int(x) - 1 for x in input().split()]) for _ in range(m)]
    ans = [0] * m
    ans[-1] = n * (n - 1) // 2
    uf = UnionFind(n)
    for i in range(m - 2, -1, -1):
        uf.union(*bridges[i + 1])
        ans[i] = uf.inconvenience
    for i in range(m):
        print((ans[i]))


if __name__ == "__main__":
    main()