CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = list(map(int, input().split()))
AB = [list([int(x)-1 for x in input().split()]) for _ in range(M)][::-1]
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 [-x for i, x in enumerate(self.parents) if x < 0]

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

uf = UnionFind(N)
ans = []
for a, b in AB:
    roots = uf.roots()
    ans.append(sum([i*(N-i) for i in roots]))
    uf.union(a, b)
for a in ans[::-1]:
    print((a//2))

# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = list(map(int, input().split()))
AB = [list([int(x)-1 for x in input().split()]) for _ in range(M)][::-1]
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 [-x for i, x in enumerate(self.parents) if x < 0]

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

uf = UnionFind(N)
ans = []
cnt = N*(N-1)//2
for a, b in AB:
    ans.append(cnt)
    if uf.same(a, b):
        continue
    cnt -= uf.size(a)*uf.size(b)
    uf.union(a, b)
for a in ans[::-1]:
    print(a)
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = list(map(int, input().split()))
AB = [list([int(x)-1 for x in input().split()]) for _ in range(M)][::-1]
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 [-x for i, x in enumerate(self.parents) if x < 0]

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

uf = UnionFind(N)
ans = []
cnt = N*(N-1)//2
for a, b in AB:
    ans.append(cnt)
    if uf.same(a, b):
        continue
    cnt -= uf.size(a)*uf.size(b)
    uf.union(a, b)
for a in ans[::-1]:
    print(a)

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N, M = mapint()

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()}

uf = UnionFind(N)
AB = [list(mapint()) for _ in range(M)][::-1]
ans = [0]*M
ans[0] = N*(N-1)//2
groups = N*(N-1)//2
for i in range(M-1):
    a, b = AB[i]
    if not uf.same(a-1, b-1):
        a_size = uf.size(a-1)
        b_size = uf.size(b-1)
        uf.union(a-1, b-1)
        groups -= a_size*b_size
    ans[i+1] = groups
for a in ans[::-1]:
    print(a)
# Original solution
n, m = [int(i) for i in input().split() ]
br = list([])
for i in range(m):
    x = [int(i) for i in input().split() ]
    br.append(x)

inc = int((n*(n-1))/2)
can = [set([i]) for i in range(n+1)]
ans = list([inc])
for b in br[:0:-1] :
    tmp = 0
    #new0 = (can[b[1]]|{b[1]}) - can[b[0]]
    #new1 = (can[b[0]]|{b[0]}) - can[b[1]]
    new0 = can[b[1]] - can[b[0]]
    new1 = can[b[0]] - can[b[1]]
    tmp += (len(new0) + len(new1))

    can[b[0]] = can[b[0]] | new0
    for x in new0-{b[1]}:
        #tmp += len(can[b[0]]-can[x])
        #can[x] = can[x]|can[b[0]]
        z = can[b[0]]-can[x]
        tmp += len(z)
        can[x] |= z

    can[b[1]] = can[b[1]] | new1
    for x in new1-{b[0]}:
        #tmp += len(can[b[1]]-can[x])
        #can[x] = can[x]|can[b[1]]
        z = can[b[1]]-can[x]
        tmp += len(z)
        can[x] |= z
    inc -= int(tmp/2)

    ans.append(inc)
    if inc == 0:
        break
while len(ans) < m:
    ans.append(0)

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

# Optimized solution
n, m = [int(i) for i in input().split() ]
br = list([])
for i in range(m):
    x = [int(i) for i in input().split() ]
    br.append(x)
inc = int((n*(n-1))/2)
can = [set([i]) for i in range(n+1)]
ans = list([inc])
for b in br[:0:-1] :
    if b[1] not in can[b[0]]:
        inc -= len(can[b[0]]) * len(can[b[1]])
        z = can[b[0]]|can[b[1]]
        for x in z:
            can[x] = z
    ans.append(inc)
    if inc == 0:
        break
while len(ans) < m:
    ans.append(0)
for i in ans[::-1]:
    print(i)
# Original solution
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.find(self.par[x])

    def sizeCheck(self, x):
        x = self.find(x)
        return self.size[x]

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

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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                
n, m = map(int, input().split())
bridge = []
for i in range(m):
  bridge.append(list(map(int, input().split())))
ans = [int(n * (n - 1) / 2)]

uf = UnionFind(n)
index = m - 1
while index > 0:
  li = bridge[index]
  if uf.sameCheck(li[0], li[1]):
    ans = [ans[0]] + ans
    index -= 1
  else:
    s0 = uf.sizeCheck(li[0])
    s1 = uf.sizeCheck(li[1])
    uf.union(li[0], li[1])
    ans = [ans[0] - s0 * s1] + ans
    index -= 1
print(*ans, sep = "\n")
  


# Optimized solution
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.find(self.par[x])

    def sizeCheck(self, x):
        x = self.find(x)
        return self.size[x]

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

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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

uf = UnionFind(n)
index = m - 1
while index > 0:
  li = bridge[index]
  if uf.sameCheck(li[0], li[1]):
    ans[index - 1] = ans[index]
    index -= 1
  else:
    s0 = uf.sizeCheck(li[0])
    s1 = uf.sizeCheck(li[1])
    uf.union(li[0], li[1])
    ans[index - 1] = ans[index] - s0 * s1
    index -= 1
print(*ans, sep = "\n")
# Original solution
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)

n,m = list(map(int,input().split()))
Bridge = [list(map(int,input().split())) for i in range(m)]

uf = UnionFind(n)

Inconvenience = [n*(n-1)//2]

for b in reversed(Bridge):
  if not uf.same(b[0]-1,b[1]-1):
    Inconvenience += [Inconvenience[-1]-uf.size(b[0]-1)*uf.size(b[1]-1)]
    uf.union(b[0]-1,b[1]-1)
  else:
    Inconvenience += [Inconvenience[-1]]
    
Inconvenience.pop()
for i in reversed(Inconvenience):
  print(i)

# Optimized solution
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.size[yroot] += self.size[xroot]
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
            self.size[xroot] += self.size[yroot]
        else:
            self.parents[yroot] = xroot
            self.size[xroot] += self.size[yroot]

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


import sys
input = sys.stdin.readline

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

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

for a, b in reversed(bridge):
    if uf.find(a - 1) != uf.find(b - 1):
        la = uf.len(a - 1)
        lb = uf.len(b - 1)
        uf.unite(a - 1, b - 1)
        lab = uf.len(a - 1)
        inc += la * (la - 1) // 2 + lb * (lb - 1) // 2 - lab * (lab - 1) // 2
    ans.append(inc)

print(('\n'.join(map(str, ans[:-1][::-1]))))
# Original solution
n, m = list(map(int, input().split()))

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

uni = [set([i]) for i in range(n)]

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

blis = [start]
for a, b in ab[::-1]:
  ap = a
  bp = b
  while isinstance(uni[ap], int):
    _ap = uni[ap]
    uni[ap] = _ap
    ap = _ap
  while isinstance(uni[bp], int):
    _bp = uni[bp]
    uni[bp] = _bp
    bp = _bp
  _ap = uni[ap]
  _bp = uni[bp]
  if _ap.intersection(_bp) == set():
    start -= len(_ap) * len(_bp)
  if ap != bp:
    uni[ap] = uni[ap].union(uni[bp])
    uni[bp] = ap
  blis.append(start)
for p in blis[::-1][1:]:
  print(p)


# Optimized solution
def comb(n):
    return n*(n+1)//2

class UnionFind:
  def __init__(self, N):
    self.parent = [i for i in range(N)]
    self.rank = [0] * N
    self.count = 0
    self.size = [1] * N
    self.connection = 0

  def root(self, a):
    if self.parent[a] == a:
      return a
    else:
      self.parent[a] = self.root(self.parent[a])
      return self.parent[a]

  def is_same(self, a, b):
    return self.root(a) == self.root(b)

  def unite(self, a, b):
    ra = self.root(a)
    rb = self.root(b)
    if ra == rb:
      return
    self.connection -= (comb(self.size[ra]) + comb(self.size[rb]))
    self.connection += comb(self.size[ra] + self.size[rb])
    if self.rank[ra] < self.rank[rb]:
      self.size[rb] += self.size[ra]
      self.parent[ra] = rb
    else:
      self.size[ra] += self.size[rb]
      self.parent[rb] = ra
      if self.rank[ra] == self.rank[rb]:
        self.rank[ra] += 1
    self.count += 1

n, m = list(map(int, input().split()))
uni = UnionFind(n)
remain = [comb(n-1)]
abl = []
for _ in range(m):
  a, b = list(map(int, input().split()))
  abl.append((a-1, b-1))
for a, b in abl[::-1]:
  uni.unite(a, b)
  remain.append(remain[0] - uni.connection)
for r in reversed(remain[:-1]):
  print(r)
# Original solution
#!/usr/bin/env python3
import sys

class UnionFind():
    def __init__(self, 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 main():
    N, M = map(int, input().split())
    A = [None] * M
    B = [None] * M
    for i in range(M):
        A[i], B[i] = map(int, input().split())

    ans = [0] * M
    ans[-1] = N * (N-1) // 2
    # 逆順に橋が出来ると不便さが変わるか調べる
    uf = UnionFind(N)
    for i in range(M-1):
        # aとbが連結か調べる
        a, b = A[M-1-i]-1, B[M-1-i]-1
        if uf.find(a) == uf.find(b):
            ans[M-i-2] = ans[M-i-1]
        else:
            ans[M-i-2] = ans[M-i-1] - abs(uf.parents[uf.find(a)]) * abs(uf.parents[uf.find(b)])
            uf.union(a, b) 

    [print(a) for a in ans]
    

if __name__ == '__main__':
    main()


# Optimized solution
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parents[x] == x:
            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:
            if self.size[x] < self.size[y]:
                x, y = y, x
            self.parents[y] = x
            self.size[x] += self.size[y]

N, M = map(int, input().split())
ab = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]
uf = UnionFind(N)

now = N*(N-1)//2
ans = [now]
for i in range(M-1):
    a = ab[M - i - 1][0]
    b = ab[M - i - 1][1]
    pa = uf.find(a)
    pb = uf.find(b)
    if pa != pb:
        now -= uf.size[pa] * uf.size[pb]
        uf.union(a, b)
    ans.append(now)
[print(a) for a in ans[::-1]]
# Original solution
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 group_count(self):
        temp = [(-self.parents[i])*(-self.parents[i]-1)//2 for i in range(len(self.parents)) if self.parents[i] < -1]
        a = sum(temp)
        if a == init:
            end = True
            return a
        else:
            return a
N,M = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
uf = UnionFind(N)
init = N*(N-1)//2
ans = []
temp = []
end = False
b = 0
for i in range(1, M+1):
    if b == init:
        ans.append(0)
    else:
        uf.union((AB[-i][0]-1), (AB[-i][1]-1))
        b = uf.group_count()
        ans.append(init-b)
for i in range(1, M):
    print((ans[-i-1]))
print(init)

# Optimized solution
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 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        a = self.parents[x]
        b = self.parents[y]
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return(a*b)
N,M = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
uf = UnionFind(N)
init = N*(N-1)//2
ans = []
temp = init
for i in range(1, M+1):
    temp -= uf.union((AB[-i][0]-1), (AB[-i][1]-1))
    ans.append(temp)
for i in range(1, M):
    print((ans[-i-1]))
print(init)
# Original solution
n,m=list(map(int,input().split()))
bridge=[[] for i in range(m)]
iland=[[i+1] for i in range(n)]
for i in range(m):
    bridge[i]=list(map(int,input().split()))
ans=[0 for i in range(m+1)]
ans[0]=int((n-1)*n/2)
k=1
for i in reversed(bridge):
    ans[k]=ans[k-1]
    for j in range(len(iland)):
        if i[0] in iland[j]:
            temp=j
            break
    for j in range(len(iland)):
        if i[1] in iland[j]:
            if temp!=j:
                ans[k]=ans[k-1]-len(iland[j])*len(iland[temp])
                iland[temp].extend(iland[j])
                del iland[j]
                break
    if ans[k]==0:
        ans[k:]=[0 for l in range(m-k)]
        break
    k+=1
for i in range(m):
    print((ans[m-1-i]))

# Optimized solution
n,m=list(map(int,input().split()))
bridge=[[] for i in range(m)]
leader=[i for i in range(n+1)]
member=[1 for i in range(n+1)]
for i in range(m):
    bridge[i]=list(map(int,input().split()))
ans=[0 for i in range(m+1)]
ans[0]=int((n-1)*n/2)
k=1
for i in reversed(bridge):
    le0=leader[i[0]]
    le1=leader[i[1]]
    while le0!=leader[le0]:
        le0=leader[le0]
        leader[i[0]]=le0
        
    while le1!=leader[le1]:
        le1=leader[le1]
        leader[i[1]]=le1
        
    if le0!=le1:
        ans[k]=ans[k-1]-member[le0]*member[le1]
        if member[le0]>=member[le1]:
            member[le0]+=member[le1]
            leader[le1]=le0
        else:
            member[le1]+=member[le0]
            leader[le0]=le1
    else:
        ans[k]=ans[k-1]
    if ans[k]==0:
        ans[k:]=[0 for l in range(m-k)]
        break
    k+=1
for i in range(m):
    print((ans[m-1-i]))
# Original solution
#16:50
n,m = list(map(int,input().split()))
a = []
for _ in range(m):
  x,y = list(map(int,input().split()))
  x -= 1
  y -= 1
  a.append([x,y])
a.reverse()
scr = n * (n-1) // 2
pre = [-1 for _ in range(n)]
cnt = [1 for _ in range(n)]
ans = []
for i in range(m):
  ans.append(scr)
  X,Y = a[i]
  while pre[X] != -1:
    X = pre[X]
  while pre[Y] != -1:
    Y = pre[Y]
  x,y = min(X,Y), max(X,Y)
  if x != y:
    scr -= cnt[x] * cnt[y]
    pre[y] = x
    cnt[x] = cnt[x] + cnt[y]
  #print(pre)
  #print(cnt)
ans.reverse()
for i in range(m):
  print((ans[i]))

# Optimized solution
#16:50
n,m = list(map(int,input().split()))
a = []
for _ in range(m):
  x,y = list(map(int,input().split()))
  x -= 1
  y -= 1
  a.append([x,y])
a.reverse()
scr = n * (n-1) // 2
pre = [-1 for _ in range(n)]
cnt = [1 for _ in range(n)]
ans = []
for i in range(m):
  ans.append(scr)
  X,Y = a[i]
  while pre[X] != -1:
    X = pre[X]
  while pre[Y] != -1:
    Y = pre[Y]
  x,y = min(X,Y), max(X,Y)
  if x != y:
    scr -= cnt[x] * cnt[y]
    pre[y] = x
    cnt[x] = cnt[x] + cnt[y]
  #print(pre)
  #print(cnt)
ans.reverse()
for z in ans:
  print(z)