CodeEff/ECCO huggingface dataset:
# Original solution
N,M = [int(x) for x in input().split()]
map = [[0 for j in range(N+1)] for i in range(N+1)]
li_e = []

def dfs(v,li_gr,flg):
    if(not flg[v]):
        flg[v] = True
        li_gr.append(v)
        for u,exist in enumerate(map[v]):
            if(exist == 1 and not flg[u]):
                dfs(u,li_gr,flg)

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

for i in range(M):
    flg = [False]*(N+1)
    li_gr = []
    A = li_e[i][0]
    B = li_e[i][1]
    map[A][B] = 0
    map[B][A] = 0
    for j in range(1,N+1):
        if(not flg[j]):
            li_gr.append([])
            dfs(j,li_gr[-1],flg)
    ans = 0
    grps = len(li_gr)
    for p in range(grps):
        for q in range(p+1,grps):
            ans += len(li_gr[p])*len(li_gr[q])
    print(ans)


# Optimized solution
import sys
#sys.setrecursionlimit(1000000)

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

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

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

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

N,M = [int(x) for x in input().split()]
A = [0]*M
B = [0]*M
ans = [0]*M
for i in range(M):
    A[i],B[i] = [int(x) for x in input().split()]
ans[M-1] = int(N*(N-1)/2)
uni = UnionFind(N)
for i in range(M-1,0,-1):
    ans[i-1]=ans[i]
    if(not uni.same(A[i]-1,B[i]-1)):
        ans[i-1]-=uni.size(A[i]-1)*uni.size(B[i]-1)
        uni.unite(A[i]-1,B[i]-1)
for i in ans:
    print(i)
# Original solution
class UnionFind:
    def __init__(self, n):
        self.data=[-1 for i in range(n)]

    def root(self,x):
        if self.data[x]<0:
            return x
        else:
            self.data[x]=self.root(self.data[x])
            return self.data[x]
    def uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.data[y]<self.data[x]:
            x,y=y,x
        self.data[x]+= self.data[y]
        self.data[y] = x

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

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

n,m=map(int,input().split())
data=[]
for i in range(m):
    a,b=map(int,input().split())
    data.append((a,b))

data=data[::-1]
tmp=0
for i in range(n):
    tmp+=i
ans=[tmp]
uf=UnionFind(n)
for i in range(m):
    a,b=data[i]
    if not uf.same(a-1,b-1):
        x,y=uf.size(a-1),uf.size(b-1)
        uf.uni(a-1,b-1)
        ans.append(ans[-1]-x*y)
    else:
        ans.append(ans[-1])
print(*ans[:-1][::-1],sep='\n')


# Optimized solution
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

class UnionFind:
    def __init__(self, n):
        self.data=[-1 for i in range(n)]
 
    def root(self,x):
        if self.data[x]<0:
            return x
        else:
            self.data[x]=self.root(self.data[x])
            return self.data[x]
    def uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.data[y]<self.data[x]:
            x,y=y,x
        self.data[x]+= self.data[y]
        self.data[y] = x
 
    def same(self,x,y):
        return self.root(x)==self.root(y)
 
    def size(self,x):
        return -self.data[self.root(x)]
 
n,m=map(int,input().split())
data=[]
for i in range(m):
    a,b=map(int,input().split())
    data.append((a,b))
 
data=data[::-1]
tmp=0
for i in range(n):
    tmp+=i
ans=[tmp]
uf=UnionFind(n)
for i in range(m):
    a,b=data[i]
    if not uf.same(a-1,b-1):
        x,y=uf.size(a-1),uf.size(b-1)
        uf.uni(a-1,b-1)
        ans.append(ans[-1]-x*y)
    else:
        ans.append(ans[-1])
print(*ans[:-1][::-1],sep='\n')
# Original solution
N,M=map(int,input().split())

#Union-Find

par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]
root=set()

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            if b in root:
                root.remove(b)
            root.add(a)
            siz[a]+=siz[b]
        else:
            par[a]=b
            if a in root:
                root.remove(a)
            root.add(b)
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
            
def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)
p=N*(N-1)//2
edge=[]
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    edge.append([a,b])
ans=[p]
for i in reversed(range(1,M)):
    res=0
    union(edge[i][0],edge[i][1])
    for x in root:
        s=size(x)
        res+=s*(s-1)//2
    ans.append(max(p-res,0))
print(*ans[::-1],sep='\n')


# Optimized solution
N,M=map(int,input().split())

#Union-Find

par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]
root=set()

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            if b in root:
                root.remove(b)
            root.add(a)
            siz[a]+=siz[b]
        else:
            par[a]=b
            if a in root:
                root.remove(a)
            root.add(b)
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)
    
edge=[]
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    edge.append([a,b])
p=N*(N-1)//2
res=[p]
for i in reversed(range(1,M)):
    if(not same(edge[i][0],edge[i][1])):
        p=p-size(edge[i][0])*size(edge[i][1])
        union(edge[i][0],edge[i][1])
    res.append(p)
print(*res[::-1],sep='\n')
# Original solution
# 逆順に見ていく
# M本の橋が全て崩落した状態=全ての島が行き来できない=不便さ:N*(N-1)//2
# 橋ができたら、UnionFindで一つに島グループとしてつなぐ
# 新たにできた橋が、今まで別の島グループだったときは
# 二つの島グループの間の組み合わせの数だけ不便さが減る
# 島グループ1の数 * 島グループ2の数だけ不便さが減る
# 新たにできた島グループが同じ島グループだったときは何も変わらない

import sys
readline=sys.stdin.readline

# 0-indexed
class UnionFind:
  N=0
  parent=None
  size=None
  def __init__(self,N):
    self.N=N
    self.parent=[i for i in range(self.N)]
    self.size=[1]*self.N
    
  def root(self,x):
    while x!=self.parent[x]:
      self.parent[x]=self.parent[self.parent[x]]
      x=self.parent[x]
    return 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.size[x]>self.size[y]:
      # 大きい方にくっつける
      self.parent[y]=x
      self.size[x]+=self.size[y]
    else:
      self.parent[x]=y
      self.size[y]+=self.size[x]
      
  def get_group_size(self,x):
    return self.size[self.root(x)]
  
  def get_roots(self):
    r=set()
    for i in range(self.N):
      r.add(root(i))
    return r
  
  def show_parent(self):
    print((self.parent))
    
  def show_size(self):
    print((self.size))
    
N,M=list(map(int,readline().split()))
UF=UnionFind(N)
ans=[N*(N-1)//2]
decay=[None]*M
for i in range(M):
  a,b=list(map(int,readline().split()))
  decay[M-1-i]=[a-1,b-1]
  
# decayは逆順になっている
for i in range(M):
  a,b=decay[i]
  if UF.same(a,b):
    ans+=[ans[-1]]
  else:
    asize=UF.get_group_size(a)
    bsize=UF.get_group_size(b)
    ans+=[ans[-1]-asize*bsize]
    UF.unite(a,b)
    
for i in range(len(ans)-2,-1,-1):
  print((ans[i]))


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

class UnionFind:
  N=0
  parent=None
  size=None
  def __init__(self,N):
    self.N=N
    self.parent=[i for i in range(self.N)]
    self.size=[1]*self.N
    
  def root(self,x):
    while x!=self.parent[x]:
      self.parent[x]=self.parent[self.parent[x]]
      x=self.parent[x]
    return 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.size[x]>self.size[y]:
      # 大きい方にくっつける
      self.parent[y]=x
      self.size[x]+=self.size[y]
    else:
      self.parent[x]=y
      self.size[y]+=self.size[x]
      
  def get_group_size(self,x):
    return self.size[self.root(x)]
  
  def get_roots(self):
    r=set()
    for i in range(self.N):
      r.add(self.root(i))
    return r
  
  def show_parent(self):
    print(self.parent)
    
  def show_size(self):
    print(self.size)
    
N,M = map(int,readline().split())
bridges = [tuple(map(int,readline().split())) for i in range(M)]

# 順に崩落していく = 最後に崩落するものから順に建設されていくと考える
# 最初の不便さは(N * (N - 1)) // 2
# 新たにa,bの間に橋が繋がると、[aが属していた島々 * bが属していた島々]だけ不便さが減る
UF = UnionFind(N)
ans = [0] * M
num = (N * (N - 1)) // 2

for i in range(len(bridges) - 1, -1, -1):
  ans[i] = num
  a,b = bridges[i]
  a,b = a - 1,b - 1
  if not UF.same(a,b):
    num -= UF.get_group_size(a) * UF.get_group_size(b)
  UF.unite(a,b)

print(*ans, sep = "\n")
# Original solution
import sys
sys.setrecursionlimit(65536)

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

uf=[i for i in range(N+1)]
nc=[1 for i in range(N+1)]

def find(i):
	if uf[i] == i:
		return i
	else:
		uf[i] = find(uf[i])
		return uf[i]

def union(i, j):
	gi, gj = find(i), find(j)
	if gi != gj:
		uf[gi] = gj
		diff = nc[gj] * nc[gi]
		nc[gj] += nc[gi]
		return diff
	return 0

su = N*(N-1)//2
ans = [-1]*M

for i in range(M-1, -1, -1):
	ans[i] = su
	x,y = bridge[i]
	su -= union(x, y)

for p in ans:
	print(p)


# Optimized solution
import sys
sys.setrecursionlimit(65536)

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

uf=[i for i in range(N+1)]
nc=[1 for i in range(N+1)]

def find(i):
	if uf[i] == i:
		return i
	else:
		uf[i] = find(uf[i])
		return uf[i]

def union(i, j):
	gi, gj = find(i), find(j)
	if gi != gj:
		uf[gi] = gj
		diff = nc[gj] * nc[gi]
		nc[gj] += nc[gi]
		return diff
	return 0

su = N*(N-1)//2
ans = [-1]*M

for i in range(M-1, -1, -1):
	ans[i] = su
	x,y = bridge[i]
	su -= union(x, y)

print(("\n".join(map(str, ans))))
# Original solution
n,m = list(map(int,input().split()))
a = [0]*m
b = [0]*m
for i in range(m):
  a[i], b[i] = list(map(int,input().split()))

d = [0]*(n+1)
for i in range(1,n+1):
  d[i] = i
  
s = [0] + [1]*n

g=[ [0] ]*(n+1)
for i in range(1,n+1):
  g[i] = [i]
g[0] = []
#print(g)
#quit()

c = n*(n-1)//2
ans = []
ans.append(c)

for i in range(1,m)[::-1]:
  x = d[a[i]]
  y = d[b[i]]
  x,y = max(x,y),min(x,y)
  if x == y:
    ans.append(c)
    continue
  c -= s[x]*s[y]
  #print(c, "x")
  ans.append(c)
  s[x] += s[y]
  #s[y] = 0
  for i in g[y]:
    d[i] = x
  g[x] += g[y]
  #g[y] = []
for t in ans[::-1]:
  print(t)
  

# Optimized solution
n,m = list(map(int,input().split()))
a = [0]*m
b = [0]*m
for i in range(m):
  a[i], b[i] = list(map(int,input().split()))

d = [0]*(n+1)
for i in range(1,n+1):
  d[i] = i
  

g=[ [0] ]*(n+1)
for i in range(1,n+1):
  g[i] = [i]
g[0] = []
#print(g)
#quit()

c = n*(n-1)//2
ans = []
ans.append(c)

for i in range(1,m)[::-1]:
  x = d[a[i]]
  y = d[b[i]]
  x,y = max(x,y),min(x,y)
  if x == y:
    ans.append(c)
    continue
  c -= len(g[x])*len(g[y])
  ans.append(c)
  for i in g[y]:
    d[i] = x
  g[x] += g[y]
for t in ans[::-1]:
  print(t)
# Original solution
import queue
n, m = list(map(int, input().split()))
bridges = [list(map(int, input().split())) for _ in range(m)]

nodes = [[] for _ in range(n)] # いける島のリスト
ans = n*(n-1)//2
ans_list = []
q = queue.Queue()
for i in range(m):
    ans_list.append(ans)
    # 順番に橋をかけていく
    a, b = bridges[-(i+1)]
    if not a in nodes[b-1]:
        nodes[b-1].append(a)
        nodes[a-1].append(b)
        ans -= 1
    q.put((a,b))
    q.put((b,a))
    while not q.empty():
        # print(nodes)
        a,b = list(map(int, q.get()))
        for j in nodes[a-1]:
            if not j in nodes[b-1] and j != b:
                nodes[b-1].append(j)
                nodes[j-1].append(b)
                ans -= 1
                q.put((j,b))
        for j in nodes[b-1]:
            if not j in nodes[a-1] and j != a:
                nodes[a-1].append(j)
                nodes[j-1].append(a)
                ans -= 1
                q.put((j,a))
# print(nodes)
for i in range(m):
    print((ans_list[-i-1]))


# Optimized solution
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を見てくっつける方を決める
        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)]

n, m = list(map(int, input().split()))
bridges = [list(map(int, input().split())) for _ in range(m)]
nodes = [[] for _ in range(n)] # いける島のリスト
ans = n*(n-1)//2
ans_list = []
u = UnionFind(n)
for i in range(m):
    ans_list.append(ans)
    # 順番に橋をかけていく
    a, b = bridges[-(i+1)]
    if u.isSameGroup(a, b):
        continue
    else:
        ans -= u.Count(a)*u.Count(b)
        u.Unite(a, b)

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

par = [int(x) for x in range(N+1)]  # 所属グループ
gn = [1 for _ in range(N+1)]


def group(i):
    if par[i] == i:
        return i
    else:
        return group(par[i])


def group_num(i):               # order(NlogN)?
    counter = 0
    for j in range(N+1):
        if group(j) == i:
            counter += 1
    return counter


ans = [int(N*(N-1)/2)]

for i, b in enumerate(bridge[::-1]):  # O(M)
    g0 = group(b[0])
    g1 = group(b[1])
    # print(i)
    if g0 > g1:
        ans.append(int(ans[-1] - gn[g0]*gn[g1]))
        par[g0] = g1
        gn[g1] += gn[g0]
        gn[g0] = 0
        par[g0] = g1
    elif g0 < g1:
        ans.append(int(ans[-1] - gn[g0]*gn[g1]))
        par[g1] = g0
        gn[g0] += gn[g1]
        gn[g1] = 0
    else:
        ans.append(ans[-1])

# print(par)
# print([group(x) for x in par])
for x in ans[::-1][1:]:
    print(x)


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

par = [int(x) for x in range(N+1)]  # 所属グループ
gn = [1 for _ in range(N+1)]        # 各グループサイズ


def group(i):
    if par[i] == i:
        return i
    else:
        par[i] = group(par[i])
        return par[i]


ans = [int(N*(N-1)/2)]

for i, b in enumerate(bridge[::-1]):  # O(M)
    g0 = group(b[0])
    g1 = group(b[1])
    if g0 > g1:
        ans.append(int(ans[-1] - gn[g0]*gn[g1]))
        par[g0] = g1
        gn[g1] += gn[g0]
        gn[g0] = 0
    elif g0 < g1:
        ans.append(int(ans[-1] - gn[g0]*gn[g1]))
        par[g1] = g0
        gn[g0] += gn[g1]
        gn[g1] = 0
    else:
        ans.append(ans[-1])

for x in ans[::-1][1:]:
    print(x)
# Original solution
n,m = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i 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)
s = n*(n-1)//2
ans = [0]*m
for i in range(m-1,-1,-1):
  if uf.find(ab[i][0]-1) != uf.find(ab[i][1]-1):
    s -= uf.size(ab[i][0]-1)*uf.size(ab[i][1]-1)
  uf.union(ab[i][0]-1,ab[i][1]-1)
  ans[i-1] = s
ans[m-1] = n*(n-1)//2
for i in ans:
  print(i)

# 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

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


n,m = list(map(int,input().split()))
uf = UnionFind(n)
q = []
for i in range(m):
    a,b = list(map(int,input().split()))
    q.append([a-1,b-1])
ans = n*(n-1)//2
l = []
for i in range(m-1,-1,-1):
    a,b = q[i]
    l.append(ans)
    if not uf.same(a,b):
        ans -= uf.size(a)*uf.size(b)
    uf.union(a,b)
for i in l[::-1]:
    print(i)
# Original solution

n,m=map(int,input().split())
A=[]
par=[-1]*n
def find(x):
  if par[x]<0:
    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 False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True
def same(x,y):
  return find(x)==find(y)
def size(x):
  return -par[find(x)]
for i in range(m):
  a,b=map(int,input().split())
  A.append([a,b])
A=A[::-1]
ans=n*(n-1)//2
Ans=[ans]
for i in range(m):
  a,b=A[i]
  if not same(a-1,b-1):
    ans-=(size(a-1)*size(b-1))
  Ans.append(ans)
  unite(a-1,b-1)
Ans=Ans[::-1][1:]
print(*Ans,sep="\n")


# Optimized solution
import sys
input=lambda: sys.stdin.readline().rstrip()
n,m=list(map(int,input().split()))
par=[-1]*n
def find(x):
  if par[x]<0:
    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 False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True

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

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

AB=[]
for i in range(m):
  AB.append(tuple(int(i)-1 for i in input().split()))
Ans=[n*(n-1)//2]
for i in range(m)[::-1]:
  a,b=AB[i]
  if same(a,b):
    Ans.append(Ans[-1])
  else:
    Ans.append(Ans[-1]-size(a)*size(b))
    unite(a,b)
Ans=Ans[::-1][1:]
for a in Ans:
  print(a)
# 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)
 
  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()))
ab=[list(map(int,input().split())) for i in range(m)]

ans=[]
ans.append(n*(n-1)//2)
uf=UnionFind(n)
for a,b in ab[::-1]:
  if not uf.same(a-1,b-1):
    sizea=uf.size(a-1)
    sizeb=uf.size(b-1)
    ans.append(ans[-1]-sizea*sizeb)
  else:
    ans.append(ans[-1])
  uf.union(a-1,b-1)

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


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

n,m = list(map(int, input().split()))
ab = []
uf = UnionFind(n+1)
for i in range(m):
    a,b = list(map(int, input().split()))
    ab.append((a,b))

ans = []
huben = n*(n-1)//2
for a,b in ab[::-1]:
    ans.append(huben)
    if not uf.same(a,b):
        huben -= uf.size(a)*uf.size(b)
        uf.union(a,b)
    
for aa in ans[::-1]:
    print(aa)