CodeEff/ECCO huggingface dataset:
# Original solution
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.ans = n*(n-1)//2

    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
        sx = self.size(x)
        sy = self.size(y)
        self.ans += sx*(sx-1)//2 + sy*(sy-1)//2
        self.ans -= (sx+sy)*(sx+sy-1)//2

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

######
N,M = list(map(int,input().split()))
uf = UnionFind(N)
ans = [uf.ans]
pp = [list(map(int,input().split())) for i in range(M)]
for i in range(M,1,-1):
  uf.union(pp[i-1][0]-1, pp[i-1][1]-1)
  ans.insert(0,uf.ans)
for i in ans:
  print(i)

# Optimized solution
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.ans = n*(n-1)//2

    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
        sx = self.size(x)
        sy = self.size(y)
        self.ans += sx*(sx-1)//2 + sy*(sy-1)//2
        self.ans -= (sx+sy)*(sx+sy-1)//2

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

######
N,M = list(map(int,input().split()))
uf = UnionFind(N)
ans = [uf.ans]
pp = [list(map(int,input().split())) for i in range(M)]
for i in range(M,1,-1):
  uf.union(pp[i-1][0]-1, pp[i-1][1]-1)
  ans.append(uf.ans)
print(('\n'.join(map(str, reversed(ans)))))
# Original solution
N,M = list(map(int,input().split()))
Bridge = [[int(x)-1 for x in input().split()] for _ in range(M)] 

Igr = [{i} for i in range(N)]
Inconv = [N*(N-1)//2] * (M+1)

for i in range(M):  
    A = Bridge[M-1-i][0] 
    B = Bridge[M-1-i][1]
    if B in Igr[A]:     
        Inconv[M-1-i] = Inconv[M-i]  
    else:
        Inconv[M-1-i] = Inconv[M-i]-(len(Igr[A])*len(Igr[B]))
        Ngr = Igr[A] | Igr[B]   
        for x in list(Ngr):   
            Igr[x] = Ngr
        
for i in range(1,M+1):
    print((Inconv[i]))


# Optimized solution
N,M = list(map(int,input().split()))
Bridge = [[int(x)-1 for x in input().split()] for _ in range(M)]

Parent = [-1] * N
Size = [1] * N

def Pr(x):
    if Parent[x] == -1:
        return x
    else:
        return Pr(Parent[x])

Igr = [{i} for i in range(N)]
Inconv = [N*(N-1)//2] * (M+1)

for i in range(M):
    A = Bridge[M-1-i][0]
    B = Bridge[M-1-i][1]
    if Pr(A) == Pr(B):
        Inconv[M-1-i] = Inconv[M-i]
    else:
        Inconv[M-1-i] = Inconv[M-i]-(Size[Pr(A)]*Size[Pr(B)])
        if Size[Pr(A)]<Size[Pr(B)]:
            P = B
            C = A
        else:
            P = A
            C = B
        Size[Pr(P)] = Size[Pr(P)] + Size[Pr(C)]
        Parent[Pr(C)] = Pr(P)

for i in range(1,M+1):
    print((Inconv[i]))
# Original solution
from queue import Queue


def disintegration_Bridge(index):
    ConnectMatrix[index[0]][index[1]] = '0'
    ConnectMatrix[index[1]][index[0]] = '0'


def Calculate_inconveniece(group):
    if len(group) == 1:
        return 0
    else:
        Mysum = 0
        group_count = len(group)
        for i in range(group_count):
            num_group1 = len(group[i])
            for j in range(i + 1, group_count):
                Mysum += num_group1 * len(group[j])
        return Mysum


n, m = list(map(int, input().split()))
a = [input().split() for i in range(m)]
a = [(int(i[0]), int(i[1])) for i in a]
ConnectMatrix = [['0' for i in range(n + 1)] for j in range(n + 1)]

for bridge in a:
    ConnectMatrix[bridge[1]][bridge[0]] = '1'
    ConnectMatrix[bridge[0]][bridge[1]] = '1'

for i in a:
    # 橋の崩落
    disintegration_Bridge(i)
    mydic = ['0' for i in range(n + 1)]
    root = [[i for i in range(n + 1) if ConnectMatrix[j][i] == '1'] for j in range(n + 1)]
    group = []

    q = Queue()
    counter = 0
    for index in range(1, n + 1):
        if mydic[index] == '1':
            continue
        q.put(index)
        mydic[index] = '1'
        group.append([index])
        while not q.empty():
            focus = q.get()
            for j in root[focus]:
                if type(j) == int:
                    if mydic[j] == '0':
                        mydic[j] = '1'
                        group[counter].append(j)
                        q.put(j)
                else:
                    for node in j:
                        if mydic[node] == '0':
                            mydic[node] = '1'
                            q.put(node)
                            group[counter].append(j)
        counter += 1
    # print(group)
    print((Calculate_inconveniece(group)))


# Optimized solution

def Calculate_inconveniece(group):
    if len(group) == 1:
        return 0
    else:
        Mysum = 0
        group_count = len(group)
        for i in range(group_count):
            num_group1 = len(group[i])
            for j in range(i + 1, group_count):
                Mysum += num_group1 * len(group[j])
        return Mysum


def Conect_island(index, group):
    right = index[0]
    left = index[1]
    right_index = [i for i in range(len(group)) if right in group[i]][0]
    left_index = [i for i in range(len(group)) if left in group[i]][0]
    if right_index == left_index:
        return group
    else:
        temp = group[right_index]
        group[left_index] += temp
        del(group[right_index])
        return group



n, m = list(map(int, input().split()))
a = [input().split() for i in range(m)]
a = [(int(i[0]), int(i[1])) for i in a]
group = [[i]for i in range(1, n+1)]
ans =[]
for idnex in range(1, len(a) + 1):
    # print(Calculate_inconveniece(group))
    ans.append(Calculate_inconveniece(group))
    x = a[-idnex]
    group = Conect_island(x, group)
    # print(x)

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

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

bridge = bridge[1:]
bridge = reversed(bridge)
result = []
groups = []

value = n * (n - 1) // 2
result.append(value)

def find_group(v):
    for i, a in enumerate(groups):
        if v in a:
            return i
    return -1

for b in bridge:
    if value <= 0:
        result.append(0)
        continue
    b1 = find_group(b[0])
    b2 = find_group(b[1])
    if b1 < 0 and b2 < 0:
        groups.append(b)
        value -= 1
    elif b1 == b2:
        pass
    elif b1 >= 0 and b2 >= 0:
        value -= (len(groups[b1]) * len(groups[b2]))
        if b1 < b2:
            groups[b1].extend(groups[b2])
            del groups[b2]
        else:
            groups[b2].extend(groups[b1])
            del groups[b1]
    elif b1 >= 0:
        value -= len(groups[b1])
        groups[b1].append(b[1])
    else:
        value -= len(groups[b2])
        groups[b2].append(b[0])
    result.append(max(value, 0))

result = reversed(result)
for r in result:
    print(r)


# Optimized solution
n, m = list(map(int, input().split()))
bridge = list()

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

bridge = bridge[1:]
bridge = reversed(bridge)
result = []


parent = [-1] * n
size = [1] * n
def root(v):
    p = parent[v]
    if p >= 0:
        return root(p)
    return v

value = n * (n - 1) // 2
result.append(value)

for b in bridge:
    if value <= 0:
        result.append(0)
        continue
    p0 = root(b[0])
    p1 = root(b[1])
    if p0 == p1:
        result.append(value)
        continue
    s0 = size[p0]
    s1 = size[p1]
    if p0 < p1:
        parent[p1] = p0
        size[p0] += size[p1]
    else:
        parent[p0] = p1
        size[p1] += size[p0]
    value -= s0 * s1
    result.append(max(value, 0))

result = reversed(result)
for r in result:
    print(r)
# Original solution
from copy import deepcopy as dc
N, Q = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(Q)][: : -1]
res = [N * (N - 1) // 2]
mod = 2305843009213693951
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 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]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      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)]

class Factorial:
  def __init__(self, n, mod):
    self.f=[1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i=[pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

uf = UnionFind(N)
f = Factorial(N * (N - 1) // 2, 2305843009213693951)
check = set()
for b in A:
  uf.Unite(b[0], b[1])
  check.add(b[0])
  check.add(b[1])
  tempch = dc(check)
  convenience = 0
  for i in tempch:
    inc = uf.root[i]
    if inc < -1:
      if -inc > N * (N - 1) // 2:
        convenience += 1
      else:
        convenience += f.combi(-inc, 2)
    else:
      check.discard(i)
  res.append(N * (N - 1) // 2 - convenience)
for i in range(Q - 1, -1, -1):
  print((res[i]))

# Optimized solution
N, Q = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(Q)]
res = [0] * (Q - 1) + [N * (N - 1) // 2]
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 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]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      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)]

uf = UnionFind(N)
convenience = [0] * (N + 1)
for i in range(Q - 1, 0, -1):
  res[i - 1] = res[i]
  if uf.Find_Root(A[i][0]) != uf.Find_Root(A[i][1]):
    res[i - 1] -= uf.Count(A[i][0]) * uf.Count(A[i][1])
    a, b = uf.Count(A[i][0]), uf.Count(A[i][1])
    uf.Unite(A[i][0], A[i][1])
  #print(uf.root, res, a, b)
for i in range(Q):
  print((res[i]))
# Original solution
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.sizes = [1] * (n+1)
        self.root = [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
            self.root[x] = -1
            self.sizes[y] += self.sizes[x]
        else:
            self.par[y] = x
            self.root[y] = -1
            self.sizes[x] += self.sizes[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return self.sizes[find(x)]
    

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

all_comb = n*(n-1)/2

a = UnionFind(n)

ans = [all_comb]
for pair in reversed(lst):
    if a.same_check(pair[0], pair[1]):
        pass
    else:
        a.union(pair[0], pair[1])
    count = 0
    for i in range(n+1):
        if a.root[i] == 1:
            size = a.sizes[i]
            count += size * (size-1) / 2
    ans.append(all_comb - count)
    
for i in reversed(ans[:-1]):
    print((int(i)))

# Optimized solution
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.sizes = [1] * (n+1)
        self.root = [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
            self.root[x] = -1
            self.sizes[y] += self.sizes[x]
        else:
            self.par[y] = x
            self.root[y] = -1
            self.sizes[x] += self.sizes[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return self.sizes[find(x)]
    

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

all_comb = n*(n-1)/2

a = UnionFind(n)

ans = [all_comb]
for pair in reversed(lst):
    if a.same_check(pair[0], pair[1]):
        ans.append(ans[-1])
        pass
    else:
        ans.append(ans[-1] - a.sizes[a.find(pair[0])]*a.sizes[a.find(pair[1])])
        a.union(pair[0], pair[1])
    
for i in reversed(ans[:-1]):
    print((int(i)))
# Original solution
import collections
def main():
	n, m = list(map(int, input().split()))
	bridge = [[0, 0]]*m
	for i in range(m):
		bridge[i] = list(map(int, input().split()))
	inconveniences = [0]*(m+1)
	inconveniences[m] = (n*(n-1))//2
	islands = collections.defaultdict(list)
	stack = []
	for i in range(m-1, -1, -1):
		if inconveniences[i+1] == 0:
			break

		does_route_exist = False
		for island in islands[bridge[i][0]]:
			if island == bridge[i][1]:
				does_route_exist = True
				break

		if does_route_exist:
			inconvenience[i] = inconveniences[i+1]
			continue

		islands[bridge[i][0]].append(bridge[i][1])
		islands[bridge[i][1]].append(bridge[i][0])
		stack.append(bridge[i][0])

		is_visited = [False]*(n+1)
		total = 0
		for s in stack:
			is_visited[s] = True
			island_pair = 0
			queue = collections.deque([s])
			while queue:
				for island in islands[queue.popleft()]:
					if is_visited[island]:
						continue
					queue.append(island)
					is_visited[island] = True
					island_pair += 1

			total += (island_pair*(island_pair+1))//2

		inconveniences[i] = inconveniences[m] - total

	for i in range(1, m+1):
		print((inconveniences[i]))

if __name__ == '__main__':
    main()

# Optimized solution
def main():
	n, m = list(map(int, input().split()))
	bridge = [[0, 0]]*m
	for i in range(m):
		bridge[i] = list(map(int, input().split()))
	inconveniences = [0]*(m+1)
	inconveniences[m] = (n*(n-1))//2
	union_find = [[i, 0, 1] for i in range(n+1)]

	for i in range(m-1, -1, -1):
		if inconveniences[i+1] == 0:
			break
		if same(union_find, bridge[i][0], bridge[i][1]):
			inconveniences[i] = inconveniences[i+1]
			continue
		rx = root(union_find, bridge[i][0])
		ry = root(union_find, bridge[i][1])
		inconveniences[i] = inconveniences[i+1] - union_find[rx][2]*union_find[ry][2]
		unite(union_find, bridge[i][0], bridge[i][1])

	for i in range(1, m+1):
		print((inconveniences[i]))

def root(union_find, val:int) -> int:
	if union_find[val][0] == val:
		return val
	return root(union_find, union_find[val][0])

def same(union_find, x:int, y:int) -> bool:
	rx = root(union_find, x)
	ry = root(union_find, y)
	return rx == ry

def unite(union_find, x:int, y:int):
	rx = root(union_find, x)
	ry = root(union_find, y)
	if rx == ry:
		return
	if union_find[rx][1] < union_find[ry][1]:
		union_find[rx][0] = ry
		union_find[ry][2] += union_find[rx][2]
	else:
		union_find[ry][0] = rx
		union_find[rx][2] += union_find[ry][2]
		if union_find[rx][1] == union_find[ry][1]:
			union_find[rx][1] += 1

if __name__ == '__main__':
    main()
# Original solution
import sys
input = sys.stdin.readline

from collections import deque

sys.setrecursionlimit(10000000)

N,M=list(map(int,input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
to = [[] for _ in range(N+1)]
def dfs(v, p):
    count=1
    for u in to[v]:
        if u == p or done[u] == 1: continue
        done[u] = 1
        #print(v,u)
        count += dfs(u, v)
    return count

ans=0
sum = N*(N-1)/2
ans_list=[]
ans_list.append(sum)
for i in reversed(list(range(1,M))):
    done = [0]*(N+1)
    done[AB[i][0]] = 1
    v1 = dfs(AB[i][0], -1)
    if done[AB[i][1]] == 1:
        v2 = 0
    else:
        done[AB[i][1]] = 1
        v2 = dfs(AB[i][1], -1)
    to[AB[i][0]].append(AB[i][1])
    to[AB[i][1]].append(AB[i][0])
    ans+=v1*v2
    ans_list.append(sum-ans)
    
for i in reversed(list(range(M))):
    print((int(ans_list[i])))

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


class UnionFind:
    def __init__(self, N):
        self.Parent = [-1]*(N+1)
    #Aの親を探す。このときParent[A]は親の値からグループサイズに変わる。探索の最適化
    def root(self, A):
        if self.Parent[A] < 0: return A
        self.Parent[A] = self.root(self.Parent[A])
        return self.Parent[A]
    #Aが属しているグループのサイズを求める
    def size(self, A):
        return -self.Parent[self.root(A)]
    
    def connect(self,A,B):
        A = self.root(A)
        B = self.root(B)
        if A == B: return False
        
        if self.size(A) < self.size(B): A,B = B,A
        self.Parent[A] += self.Parent[B]
        self.Parent[B] = A
        return True



N,M = list(map(int,input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
Uni = UnionFind(N)
ans = [-1]*(M)
ans[M-1] = N*(N-1)//2 
for i in reversed(list(range(1,M))):
    ans[i-1] = ans[i]
    if Uni.root(AB[i][0]) != Uni.root(AB[i][1]):
        ans[i-1] -= Uni.size(AB[i][0])*Uni.size(AB[i][1])
    Uni.connect(AB[i][0], AB[i][1])
for i in range(M):
    print((ans[i]))
# Original solution
def readln():
    return list(map(int, input().split()))


N, M = readln()
AB = [readln() for _ in range(M)]
A = [ab[0]-1 for ab in AB[::-1]]
B = [ab[1]-1 for ab in AB[::-1]]


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def concat(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True


ans = [N * (N - 1) // 2]
uni = UnionFind(N)
for a, b in zip(A, B):
    if uni.root(a) == uni.root(b):
        ans.append(ans[-1])
    else:
        ans.append(ans[-1] - uni.size(a) * uni.size(b))
        uni.concat(a, b)

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


# Optimized solution
def readln():
    import sys
    input = sys.stdin.readline
    return list(map(int, input().split()))


N, M = readln()
AB = [readln() for _ in range(M)]
A = [ab[0]-1 for ab in AB[::-1]]
B = [ab[1]-1 for ab in AB[::-1]]


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def concat(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True


ans = [N * (N - 1) // 2]
uni = UnionFind(N)
for a, b in zip(A, B):
    if uni.root(a) == uni.root(b):
        ans.append(ans[-1])
    else:
        ans.append(ans[-1] - uni.size(a) * uni.size(b))
        uni.concat(a, b)

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