CodeEff/ECCO huggingface dataset:
# Original solution
N,M=list(map(int, input().split()))
#島、橋
class UnionFind():
  # 作りたい要素数nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n+1)
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
  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):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合
    if (x == y):
      return 
      # 違う木に属していた場合rnkを見てくっつける方を決める
      #rnkが大きい方に結合
    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
      # rnkが同じ（深さに差がない場合）は1増やす
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す
  def Count(self, x):
    return -self.root[self.Find_Root(x)]

L=[]
for i in range(M):
  a,b=list(map(int, input().split()))
  L.append((a-1,b-1))
uni=UnionFind(N)
ans=[0]*M
L=reversed(L)
for i,t in enumerate(L):
  a,b=t
  ca=uni.Count(a)
  cb=uni.Count(b)
  if uni.isSameGroup(a,b):
    ans[-(i+1)]=0
  else:
    ans[-(i+1)]=uni.Count(a)*uni.Count(b)
  uni.Unite(a,b)
final=[0]*M
final[0]=ans[0]
#print(ans)
for i in range(1,M):
  final[i]=final[i-1]+ans[i]
for f in final:
  print(f)
   

# Optimized solution
N,M=list(map(int, input().split()))
B=[]
class UnionFind():
  # 作りたい要素数nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n+1)
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
  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):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合
    if (x == y):
      return 
      # 違う木に属していた場合rnkを見てくっつける方を決める
      #rnkが大きい方に結合
    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
      # rnkが同じ（深さに差がない場合）は1増やす
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
for i in range(M):
  a,b=list(map(int, input().split()))
  B.append((a-1,b-1))
  
B=B[::-1]
uni=UnionFind(N)
now=N*(N-1)//2
ans=[]
for t in B:
  ans.append(now)
  a,b=t
  if uni.isSameGroup(a,b):
    uni.Unite(a,b)
  else:
    A=uni.Count(a)
    B=uni.Count(b)
    now-=(A*B)
    uni.Unite(a,b)
    
for a in ans[::-1]:
  print(a)
# Original solution
N,M=list(map(int,input().split()))

path=[]
for i in range(M):
    a,b=list(map(int,input().split()))
    path.append([a-1,b-1])
    
class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
        self.member_num = [1 for _ in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        m1=self.member_num[s1]
        m2=self.member_num[s2]
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.member_num[s1]=m1+m2
                    return [m1,m2]
                else:
                    self.table[s1] = s2
                    self.member_num[s2]=m1+m2
                    return [m1,m2]
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] = -1
                self.table[s2] = s1
                self.member_num[s1] = m1+m2
                return [m1,m2]
        return [0,0]
    
uf=UnionFind(N)

path=path[::-1]
count = 0
ans = [N*(N-1)//2]
for i in range(M):
    a,b=path[i]
    m1,m2 = uf.union(a,b)
    count+=m1*m2
    ans.append(N*(N-1)//2 - count)

ans=ans[:-1]
ans=ans[::-1]

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

# Optimized solution

N,M=list(map(int,input().split()))

path=[]
for i in range(M):
    a,b=list(map(int,input().split()))
    path.append([a-1,b-1])
    
class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
        self.member_num = [1 for _ in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        m1=self.member_num[s1]
        m2=self.member_num[s2]
        if s1 != s2:#根が異なる場合
            if m1 != m2:#グラフの高さが異なる場合
                if m1 < m2:
                    self.table[s1] = s2
                    self.member_num[s2]=m1+m2
                    return [m1,m2]
                else:
                    self.table[s2] = s1
                    self.member_num[s1]=m1+m2
                    return [m1,m2]
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] = -1
                self.table[s2] = s1
                self.member_num[s1] = m1+m2
                return [m1,m2]
        return [0,0]
    
uf=UnionFind(N)

path=path[::-1]
count = 0
ans = [N*(N-1)//2]
for i in range(M):
    a,b=path[i]
    m1,m2 = uf.union(a,b)
    count+=m1*m2
    ans.append(N*(N-1)//2 - count)

ans=ans[:-1]
ans=ans[::-1]

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親なら自身の番号を、そうでないなら（元）親の番号を示す
def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]


ans=n*(n-1)//2
d=[n*(n-1)//2]
for i in range(1,m+1):
    a,b=ab[-i][0],ab[-i][1]
    a=r(a)
    b=r(b)
    a,b=min(a,b),max(a,b)
    if a!=b:
        ans-=root[a]*root[b]
        root[a]+=root[b]
        root[b]=a
    d.append(ans)

for i in range(m):
    print((d[-2-i]))


# Optimized solution
import sys
input=sys.stdin.readline #文字列入力はするな！！



n,m=list(map(int,input().split()))
ab=[[0,0] for i in range(m)]
for i in range(m):
    ab[i][0],ab[i][1]=list(map(int,input().split()))


sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親なら自身の番号を、そうでないなら（元）親の番号を示す
def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]


ans=n*(n-1)//2
d=[n*(n-1)//2]
for i in range(1,m+1):
    a,b=ab[-i][0],ab[-i][1]
    a=r(a)
    b=r(b)
    a,b=min(a,b),max(a,b)
    if a!=b:
        ans-=root[a]*root[b]
        root[a]+=root[b]
        root[b]=a
    d.append(ans)

for i in range(m):
    print((d[-2-i]))
# Original solution
N, M = list(map(int, input().split()))
L = [list(map(int, input().split())) for _ in range(M)]

X = [set([i]) for i in range(1,N+1)]

C = [0]
for a, b in L[::-1]:
    xa = [x for x in X if a in x][0]
    xb = [x for x in X if b in x][0]
    if(len(xa ^ xb)!=0):
        C.append(C[-1]+len(xa)*len(xb))
        X.remove(xa)
        X.remove(xb)
        X.append(xa | xb)
    else:
        C.append(C[-1])

for c in C[:-1][::-1]:
    print((N*(N-1)//2-c))

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

X = [set([i]) for i in range(1,N+1)]

par = list(range(N+1))
rank = [0] * (N+1)
size = [1] * (N+1)

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    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
    return

C = [0]
for a, b in L[::-1]:
    xa = find(a)
    xb = find(b)
    if xa == xb:
        C.append(C[-1])
    else:
        C.append(C[-1] + size[xa] * size[xb])
        unite(xa, xb)

for c in C[:-1][::-1]:
    print((N*(N-1)//2-c))
# Original solution
class uf_tree:
    def __init__(self, n):
        self._size = n
        self.sizes = [1] * n
        self.par = list(range(n))

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

    def unite(self, x, y):
        self._size -= 1
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]

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

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


def com(x):
    return x*(x-1)//2

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

ans = []
benri = 0

uf = uf_tree(n+1)

benri = 0

for a, b in AB[::-1]:
    ans += [ com(n) - benri ]    
    if uf.same(a, b):
        continue

    a_benri = com(uf.size(a) )
    b_benri = com(uf.size(b) )

    uf.unite(a, b)
    sum_benri = com( uf.size(a) )
    benri += sum_benri - a_benri - b_benri

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



# Optimized solution
import sys

input = sys.stdin.readline

class uf_tree:
    def __init__(self, n):
        self._size = n
        self.sizes = [1] * n
        self.par = list(range(n))

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

    def unite(self, x, y):
        self._size -= 1
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]

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

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


def com(x):
    return x*(x-1)//2

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

ans = []
benri = 0

uf = uf_tree(n+1)

for a, b in AB[::-1]:
    ans += [ com(n) - benri ]    
    if uf.same(a, b):
        continue

    a_benri = com(uf.size(a) )
    b_benri = com(uf.size(b) )

    uf.unite(a, b)
    sum_benri = com( uf.size(a) )
    benri += sum_benri - a_benri - b_benri

print (*ans[::-1], sep="\n")
# Original solution
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
group = [i for i in range(n)]
islands = {i: [i] for i in range(n)}
ret = [0] * m + [n * (n - 1) // 2]
for i in range(m - 1, -1, -1):
    a, b = ab[i]
    ga, gb = group[a - 1], group[b - 1]
    if ga == gb:
        ret[i] = ret[i + 1]
    else:
        ret[i] = ret[i + 1] - len(islands[ga]) * len(islands[gb])
        islands[ga] += islands[gb]
        for j in islands[gb]:
            group[j] = ga
for i in range(1, m + 1):
    print((ret[i]))

# Optimized solution
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
group = [i for i in range(n)]
islands = {i: [i] for i in range(n)}
ret = [0] * m + [n * (n - 1) // 2]
for i in range(m - 1, -1, -1):
    a, b = ab[i]
    ga, gb = group[a - 1], group[b - 1]
    if ga == gb:
        ret[i] = ret[i + 1]
    else:
        la, lb = len(islands[ga]), len(islands[gb])
        ret[i] = ret[i + 1] - la * lb
        if la > lb:
            for j in islands[gb]:
                group[j] = ga
                islands[ga].append(j)
        else:
            for j in islands[ga]:
                group[j] = gb
                islands[gb].append(j)
for i in range(1, m + 1):
    print((ret[i]))
# Original solution
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
group = [i for i in range(n)]
islands = {i: [i] for i in range(n)}
ret = [0] * m + [n * (n - 1) // 2]
for i in range(m - 1, -1, -1):
    a, b = ab[i]
    ga, gb = group[a - 1], group[b - 1]
    if ga == gb:
        ret[i] = ret[i + 1]
    else:
        la, lb = len(islands[ga]), len(islands[gb])
        ret[i] = ret[i + 1] - la * lb
        if la > lb:
            for j in islands[gb]:
                group[j] = ga
                islands[ga].append(j)
        else:
            for j in islands[ga]:
                group[j] = gb
                islands[gb].append(j)
for i in range(1, m + 1):
    print((ret[i]))

# Optimized solution
import sys
sys.setrecursionlimit(100000)

n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
parent = [i for i in range(n)]
count = [1 for i in range(n)]

def root(i):
    if i == parent[i]:
        return i
    parent[i] = root(parent[i])
    return parent[i]

def merge(i, j):
    parent[j] = i
    count[i] += count[j]

ret = [0] * m + [n * (n - 1) // 2]
for i in range(m - 1, -1, -1):
    a, b = ab[i]
    ra, rb = root(a - 1), root(b - 1)
    if ra == rb:
        ret[i] = ret[i + 1]
    else:
        ret[i] = ret[i + 1] - count[ra] * count[rb]
        merge(ra, rb)

for i in range(1, m + 1):
    print((ret[i]))
# Original solution
def getN():
    return int(eval(input()))

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

from collections import Counter
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for i in range(n)]
        self.rank = [0] * (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.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.size[x] += self.size[y]
            self.size[y] = 0

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



n,m = getMN()

bridges = []

for i in range(m):
    a,b = getMN()
    bridges.append([a,b])

bridges.reverse()

uf = UnionFind(n)
answers = []
for query in bridges:
    x,y = query
    if not uf.same_check(x-1,y-1):
        uf.union(x-1,y-1)
    ans = 0
    for si in uf.size:
        ans += si * (n-si)
    answers.append(ans//2)

for fa in answers[:-1][::-1]:
    print(fa)
print((n*(n-1)//2))

# Optimized solution
def getN():
    return int(eval(input()))

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

from collections import Counter
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for i in range(n)]
        self.rank = [0] * (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.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.size[x] += self.size[y]
            self.size[y] = 0

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



n,m = getMN()

bridges = []

for i in range(m):
    a,b = getMN()
    bridges.append([a,b])

bridges.reverse()

uf = UnionFind(n)
ans = n*(n-1)//2
answers = [ans]
for query in bridges:
    x,y = query
    if not uf.same_check(x-1,y-1):
        #print(uf.size,x,y)
        ans -= uf.size[uf.find(x-1)]*uf.size[uf.find(y-1)]
        #print(uf.find(x-1))
        uf.union(x-1,y-1)

    answers.append(ans)

for fa in answers[:-1][::-1]:
    print(fa)
# Original solution
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))
SIZE = [0] + [1] * N  # 1-indexed


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


def unite(x, y):
    m = min(find(x), find(y))
    SIZE[m] = SIZE[find(x)] + SIZE[find(y)]
    UF[find(x)] = m
    UF[find(y)] = m


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


def scan_uf():
    for i in range(len(UF)):
        find(i)


ans = [N * (N - 1) // 2]
for a, b in AB[::-1]:
    if not is_same(a, b):
        ans += [ans[-1] - SIZE[find(a)] * SIZE[find(b)]]
        unite(a, b)
    else:
        ans += [ans[-1]]
print(*ans[-2::-1], sep='\n')


# Optimized solution
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))
SIZE = [0] + [1] * N  # 1-indexed


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


def unite(x, y):
    X, Y = find(x), find(y)
    SX,SY=SIZE[X],SIZE[Y]
    m = min(X,Y)
    SIZE[m] = SX + SY
    SIZE[X+Y-m]=0
    UF[X+Y-m] = m


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


def scan_uf():
    for i in range(len(UF)):
        find(i)


ans = [N * (N - 1) // 2]
for a, b in AB[::-1]:
    if not is_same(a, b):
        ans += [ans[-1] - SIZE[find(a)] * SIZE[find(b)]]
        unite(a, b)
    else:
        ans += [ans[-1]]
print(*ans[-2::-1], sep='\n')
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

P=list(range(N+1))
C=[1 for _ in range(N+1)]
C[0] = 0

def root(x):
    if P[x]==x: return x
    P[x] = root(P[x])
    return P[x]

def unite(a,b):
    ra = root(a)
    rb = root(b)
    C[ra] += C[rb]
    C[rb] = 0
    P[rb] = ra

def same(a,b):
    return root(a) == root(b)

def count(x):
    return C[root(x)]

ans=[0]*(M+1)
ans[M] = N * (N-1)

for i in range(M-1,-1,-1):
    a,b = B[i]
    if same(a,b):
        ans[i] = ans[i+1]
        continue
    ans[i] = ans[i+1] - count(a) * count(b)
    unite(a,b)

for i in range(1,M+1):
    print((ans[i] - ans[0]))

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

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

P=list(range(N+1))
C=[1 for _ in range(N+1)]
C[0] = 0

def root(x):
    t = x
    stack = []
    while P[t] != t:
        stack.append(t)
        t = P[t]
    for c in stack: P[c] = t
    return t

def unite(a,b):
    ra = root(a)
    rb = root(b)
    C[ra] += C[rb]
    C[rb] = 0
    P[rb] = ra

def same(a,b):
    return root(a) == root(b)

def count(x):
    return C[root(x)]

ans=[0]*(M+1)
ans[M] = N * (N-1)

for i in range(M-1,-1,-1):
    a,b = B[i]
    if same(a,b):
        ans[i] = ans[i+1]
        continue
    ans[i] = ans[i+1] - count(a) * count(b)
    unite(a,b)

for i in range(1,M+1):
    print((ans[i] - ans[0]))
# Original solution
N, M = list(map(int, input().split()))
A, B = [], []
g = {}
for i in range(1, N+1):
    g[i] = []
for _ in range(M):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)
    g[a].append(b)
    g[b].append(a)


def dfs(graph, start):
    visited = []
    stack = []
    stack.append(start)
    result = []
    while len(stack) > 0:
        next = stack.pop()
        if next in visited:
            continue
        result.append(next)
        visited.append(next)
        for nei in graph[next]:
            stack.append(nei)
    return result


def wfs(graph, start):
    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 graph[next_city]:
            queue.append(nei)
    return result


for i in range(M):
    ans = 0
    g[A[i]].remove(B[i])
    g[B[i]].remove(A[i])
    for j in range(1, N+1):
        # print(wfs(g, j))
        for k in range(j, N+1):
            if k not in wfs(g, j):
                ans += 1
    print(ans)


# Optimized solution
class UnionFind():
    # 初期化
    # 全てのノードの親は -1 とする
    def __init__(self, n):
        self.par = [-1] * n

    # xがどのグループに属しているか調べる
    def root(self, x):
        # xが親のとき
        if self.par[x] < 0:
            return x
        # xの親がさらに親をもつとき、それをxの親とする
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    # 自分のいるグループの頂点数を調べる
    def size(self, x):
        return -self.par[self.root(x)]

    # xとyをくっつける
    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        # すでにくっついていたらくっつけない
        if x == y:
            return

        # 大きい方(x)に小さい方(y)をくっつける
        if self.size(x) < self.size(y):
            x, y = y, x

        # xのサイズを更新
        self.par[x] += self.par[y]
        # yの親をxに変更
        self.par[y] = x

        return


N, M = list(map(int, input().split()))
A, B = [], []
for _ in range(M):
    a, b = list(map(int, input().split()))
    # インデックスをずらす
    A.append(a-1)
    B.append(b-1)

uni = UnionFind(N)

ans = [N * (N-1) // 2]
for i in range(M-1, 0, -1):
    ans.append(ans[-1])
    # 繋がっていないグループがつながったとき
    if uni.root(A[i]) != uni.root(B[i]):
        ans[-1] -= uni.size(A[i]) * uni.size(B[i])
        uni.connect(A[i], B[i])

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