CodeEff/ECCO huggingface dataset:
# 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.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()


# 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
    print(("\n".join(map(str, ans))))


if __name__ == "__main__":
    main()
# Original solution
n,m = list(map(int, input().split()))

bridges = []
for i in range(m):
    bridges.append([int(x) for x in input().split()])
'''
g = list(range(n+1))
ng = [1 for _ in range(n+1)]
gl = [[i] for i in range(n+1)]
ans = []
unconf = n*(n-1)//2
ans.append(unconf)


for x in reversed(bridges):
    a,b = x
    if g[a] != g[b]:
        tmp = ng[g[a]] * ng[g[b]]
        ng[g[a]] = ng[g[a]]+ng[g[b]]
        gl[g[a]] = gl[g[a]] + gl[g[b]]
        for y in gl[g[b]]:
            g[y] = g[a]
        unconf -= tmp
        ans.append(unconf)
    else:
        ans.append(unconf)


ans.reverse()
ans.pop(0)
for x in ans:
    print(x)
'''
def root(par, ifpar, a):
    while ifpar[a] != 1:
       a = par[a]
    return a 

def unite(cnt, par, ifpar, npar, ra, rb):
    if cnt % 2 == 0:
        npar[ra] = npar[ra] + npar[rb]
        par[rb] = ra
        ifpar[rb] = 0
    else:
        npar[rb] = npar[rb] + npar[ra]
        par[ra] = rb
        ifpar[ra] = 0

par = list(range(n+1))
ifpar = [1 for _ in range(n+1)]
npar = [1 for _ in range(n+1)]

ans = []
unconf = n*(n-1)//2
ans.append(unconf)
cnt = 0

for x in reversed(bridges):
    a,b = x
    ra = root(par, ifpar, a)
    rb = root(par, ifpar, b)
    if ra != rb:
        tmp = npar[ra] * npar[rb]
        unite(cnt, par, ifpar, npar, ra, rb)
        unconf -= tmp
    ans.append(unconf)
    cnt += 1

ans.reverse()
ans.pop(0)
for x in ans:
    print(x)



















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

bridges = []
for i in range(m):
    bridges.append([int(x) for x in input().split()])
'''
g = list(range(n+1))
ng = [1 for _ in range(n+1)]
gl = [[i] for i in range(n+1)]
ans = []
unconf = n*(n-1)//2
ans.append(unconf)


for x in reversed(bridges):
    a,b = x
    if g[a] != g[b]:
        tmp = ng[g[a]] * ng[g[b]]
        ng[g[a]] = ng[g[a]]+ng[g[b]]
        gl[g[a]] = gl[g[a]] + gl[g[b]]
        for y in gl[g[b]]:
            g[y] = g[a]
        unconf -= tmp
        ans.append(unconf)
    else:
        ans.append(unconf)


ans.reverse()
ans.pop(0)
for x in ans:
    print(x)
'''
def root(par, ifpar, a):
    while ifpar[a] != 1:
       a = par[a]
    return a 

def unite(cnt, par, ifpar, npar, depth, ra, rb):
    if depth[ra] >= depth[rb]:
        npar[ra] = npar[ra] + npar[rb]
        par[rb] = ra
        ifpar[rb] = 0
        if depth[ra] == depth[rb]:
            depth[ra] += 1
    else:
        npar[rb] = npar[rb] + npar[ra]
        par[ra] = rb
        ifpar[ra] = 0

par = list(range(n+1))
ifpar = [1 for _ in range(n+1)]
npar = [1 for _ in range(n+1)]
depth = [1 for _ in range(n+1)]

ans = []
unconf = n*(n-1)//2
ans.append(unconf)
cnt = 0

for x in reversed(bridges):
    a,b = x
    ra = root(par, ifpar, a)
    rb = root(par, ifpar, b)
    if ra != rb:
        tmp = npar[ra] * npar[rb]
        unite(cnt, par, ifpar, npar, depth, ra, rb)
        unconf -= tmp
    ans.append(unconf)
    cnt += 1

ans.reverse()
ans.pop(0)
for x in ans:
    print(x)
# Original solution
import math
from collections import defaultdict
from collections import deque


class UnionFindTree:
    '''
    Union Find Tree
    '''

    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


_ncr = {}


def ncr(n, r):
    if n < r:
        return 0
    k = "{}:{}".format(n, r)
    if k not in _ncr:
        _ncr[k] = math.factorial(n) // (math.factorial(n - r) *
                                        math.factorial(r))
    return _ncr[k]


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

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = ncr(N, 2)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += ncr(nx, 2) + ncr(ny, 2)
        total -= ncr(n, 2)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

# Optimized solution
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


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

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)
# Original solution
import sys
sys.setrecursionlimit(100000)
N,M=list(map(int,input().split()))
AB=[list(map(int,input().split())) for _ in range(M)]
AB.reverse()
par=list(range(1,N+1))
size=[1]*N

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

def spar(n):
  if par[n-1]==n:
    return n
  else:
    return spar(par[n-1])

for i in range(0,M-1):
  A,B=AB[i]
  pa,pb=spar(par[A-1]),spar(par[B-1])
  if pa==pb:
    ans[i+1]=ans[i]
  else:
    ans[i+1]=ans[i]-size[pa-1]*size[pb-1]
    sa,sb=size[pa-1],size[pb-1]
    size[pa-1]+=sb
    size[pb-1]+=sa
  par[pa-1]=pa
  par[pb-1]=pa
  
for i in reversed(ans):
  print(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)]
AB.reverse()
par=list(range(1,N+1))
size=[1]*N

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

def spar(n):
  if par[n-1]==n:
    return n
  else:
    par[n-1]=spar(par[n-1])
    return par[n-1]

for i in range(0,M-1):
  A,B=AB[i]
  pa,pb=spar(par[A-1]),spar(par[B-1])
  if pa==pb:
    ans[i+1]=ans[i]
  else:
    ans[i+1]=ans[i]-size[pa-1]*size[pb-1]
    sa,sb=size[pa-1],size[pb-1]
    size[pa-1]+=sb
    size[pb-1]+=sa
  par[pa-1]=pa
  par[pb-1]=pa
  
for i in reversed(ans):
  print(i)
# Original solution
from itertools import combinations

n,m = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ 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 roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
 
ans = [n*(n-1)//2]
island = Unionfind(n)
for a,b in reversed(AB[1:]):
    island.union(a-1,b-1)
    num = [island.size(r) for r in island.roots()]
    cnt = 0
    for v,w in combinations(num,2):
      cnt += v*w
    ans.append(cnt)
        
for a in reversed(ans):
    print(a)
    
    
    

# Optimized solution
n,m = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ 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)
 
ans = [n*(n-1)//2]
island = Unionfind(n)
for a,b in reversed(AB[1:]):
  if island.same(a-1,b-1):
    cnt = ans[-1]
  else:
    cnt = ans[-1]-island.size(a-1)*island.size(b-1)
    island.union(a-1,b-1)
  ans.append(cnt)
        
for a in reversed(ans):
    print(a)
# Original solution
sn,bn=list(map(int,input().split(" ")))
fubensa=[int(sn*(sn-1)/2)]
if bn>1:
    br=[]
    for _ in range(bn):
        br.append(list(map(int, input().split(" "))))
    br=br[::-1]
    sg=[0 for n in range(sn+1)]
    sg[br[0][0]]=1
    sg[br[0][1]]=1
    gn=1
    fubensa.append(fubensa[0]-1)
    sgc=[0,2]

    for bri in range(1,bn-1):
        si1=br[bri][0]
        si2=br[bri][1]
        sg1=sg[si1]
        sg2=sg[si2]
        if sg1+sg2==0:
            gn+=1
            sg[si1],sg[si2]=gn,gn
            sgc.append(2)
            fubensa.append(fubensa[bri]-1)
        elif sg1==0:
            fubensa.append(fubensa[bri] - sgc[sg2])
            sg[si1]=sg2
            sgc[sg2]+=1
        elif sg2==0:
            fubensa.append(fubensa[bri] - sgc[sg1])
            sg[si2]=sg1
            sgc[sg1] += 1
        elif sg1!=sg2:
            fubensa.append(fubensa[bri] - sgc[sg1]*sgc[sg2])
            if sgc[sg1]<sgc[sg2]:
                sg1,sg2=sg2,sg1
            sgc[sg1]+=sgc[sg2]
            sg=[sg1 if x==sg2 else x for x in sg]
        else:
            fubensa.append(fubensa[bri])
for x in fubensa[::-1]:
    print(x)

# Optimized solution
sn,bn=map(int,input().split(" "))
fu=[int(sn*(sn-1)/2)]
gr_si=[n for n in range(sn+1)]
siL_gr=[[n] for n in range(sn+1)]
siL_br=[]
for _ in range(bn):
    siL_br.append(list(map(int, input().split(" "))))
siL_br=siL_br[::-1]

for bri in range(bn-1):
    si1,si2=siL_br[bri]
    gr1 = gr_si[si1]
    gr2 = gr_si[si2]
    if gr1==gr2:
        fu.append(fu[bri])
    else:
        lengr1 = len(siL_gr[gr1])
        lengr2 = len(siL_gr[gr2])
        if lengr1<lengr2:
            gr1,gr2=gr2,gr1
        fu.append(fu[bri]-lengr1*lengr2)
        for si in siL_gr[gr2]:
            gr_si[si]=gr1
        siL_gr[gr1]+=siL_gr[gr2]
        siL_gr[gr2]=[]

print(*fu[::-1],sep="\n")
# Original solution
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)]

n,m=list(map(int,input().split()))
ab=[list(map(int,input().split())) for _ in range(m)]
uf=UnionFind(n)
ans=[0]*m
ans.append((n*(n-1))//2)
for i in range(m-1,-1,-1):
    if uf.isSameGroup(ab[i][0],ab[i][1]):
        ans[i]=ans[i+1]
    else:
        ans[i]=ans[i+1]-uf.Count(ab[i][0])*uf.Count(ab[i][1])
        uf.Unite(ab[i][0],ab[i][1])
for i in range(1,m+1):
    print((ans[i]))


# Optimized solution
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)]

n,m=list(map(int,input().split()))
ab=[list(map(int,input().split())) for _ in range(m)]
uf=UnionFind(n)
ans=[0]*m
ans.append((n*(n-1))//2)
for i in range(m-1,-1,-1):
    a,b=ab[i][0],ab[i][1]
    if uf.isSameGroup(a,b):
        ans[i]=ans[i+1]
    else:
        ans[i]=ans[i+1]-uf.Count(a)*uf.Count(b)
        uf.Unite(a,b)
for i in range(1,m+1):
    print((ans[i]))
# Original solution
import sys

class UnionFind():
    def __init__(self, num):
        self.par = [-1]*num
        self.size = [1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.size[rx] += self.size[ry] 
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.size[ry] += self.size[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.size[rx] += self.size[ry]
        return

def inpl(): return list(map(int, input().split()))
input = sys.stdin.readline

N, M = inpl()
Edge = [list([int(x) - 1 for x in input().split()]) for _ in range(M)]

UF = UnionFind(N)
ic = N*(N-1)//2
Ans = []
for i, (a, b) in enumerate(Edge[::-1]):
    Ans.append(ic)
    ra = UF.find(a)
    rb = UF.find(b)
    if ra != rb:
        ic -= UF.size[ra]*UF.size[rb]
        UF.union(a, b)
for a in Ans[::-1]:
    print(a)


# Optimized solution
import sys

class UnionFind():
    def __init__(self, num):
        self.par = [-1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        prx = self.par[rx]
        pry = self.par[ry]
        if rx != ry:
            if prx <= pry:
                self.par[ry] = rx 
                self.par[rx] += pry
            else:
                self.par[rx] = ry
                self.par[ry] += prx
        return

def inpl(): return list(map(int, input().split()))
input = sys.stdin.readline

N, M = inpl()
Edge = [list([int(x) - 1 for x in input().split()]) for _ in range(M)]

UF = UnionFind(N)
ic = N*(N-1)//2
Ans = []
for i, (a, b) in enumerate(Edge[::-1]):
    Ans.append(ic)
    ra = UF.find(a)
    rb = UF.find(b)
    if ra != rb:
        ic -= UF.par[ra]*UF.par[rb]
        UF.union(a, b)
for a in Ans[::-1]:
    print(a)
# Original solution
from collections import deque

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        else:
            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
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def tree_size(self, x):
        return self.size[self.find(x)]
    


N, M = list(map(int, input().split()))
bridge = [[int(_) for _ in input().split()] for _ in range(M)]
uf = UnionFind(N+1)
anslist = deque()
ans = N*(N-1)//2
anslist.append(ans)


for i in range(M-1):
    island1 = bridge[M-i-1][0]
    island2 = bridge[M-i-1][1]
    if uf.find(island1) != uf.find(island2):
        ans -= uf.tree_size(island1) * uf.tree_size(island2)
    
    anslist.append(ans)
    uf.unite(bridge[M-i-1][0], bridge[M-i-1][1])

for _ in range(M):
    print((anslist.pop()))

# Optimized solution
from collections import deque
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        else:
            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
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def tree_size(self, x):
        return self.size[self.find(x)]
    


N, M = list(map(int, input().split()))
bridge = [[int(_) for _ in input().split()] for _ in range(M)]
uf = UnionFind(N+1)
anslist = deque()
ans = N*(N-1)//2
anslist.append(ans)


for i in range(M-1):
    island1 = bridge[M-i-1][0]
    island2 = bridge[M-i-1][1]
    if uf.find(island1) != uf.find(island2):
        ans -= uf.tree_size(island1) * uf.tree_size(island2)
    
    anslist.append(ans)
    uf.unite(bridge[M-i-1][0], bridge[M-i-1][1])

for _ in range(M):
    print((anslist.pop()))
# Original solution
tmp=input().split(" ")
n = int(tmp[0])
m = int(tmp[1])

node_groups = [ i for i in range(n)]
group_nodes = [ [i] for i in range(n)]

edges = []
for i in range(m):
    tmp=input().split(" ")
    edges.append([int(tmp[0])-1, int(tmp[1])-1])

hubensa_list = [0] * (m + 1)
hubensa_list[m] = n*(n-1)//2

for i in range(m-1, 0, -1):
    edge = edges[i]
    # print("edge: ", edge)
    # print("node_groups: ", node_groups)
    node_1 = edge[0]
    node_2 = edge[1]

    node_1_group = node_groups[node_1]
    node_2_group = node_groups[node_2]

    if node_1_group == node_2_group:
        hubensa_list[i] = hubensa_list[i+1]
        continue

    group_of_node_1 = group_nodes[node_1_group]
    group_of_node_2 = group_nodes[node_2_group]
    len_1 = len(group_of_node_1)
    len_2 = len(group_of_node_2)
    group_nodes[node_2_group] = None

    group_of_node_1.extend(group_of_node_2)

    for j in group_of_node_2:
        # print("group_update: ",j, node_1_group)
        node_groups[j] = node_1_group
    
    # 不便さをだす
    hubensa_list[i] = hubensa_list[i+1] - (len_1 * len_2)

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

# Optimized solution
import sys

sys.setrecursionlimit(100000)

tmp=input().split(" ")
n = int(tmp[0])
m = int(tmp[1])

node_groups = [ i for i in range(n)]
group_sizes = [ 1 for _ in range(n)]

edges = []
for i in range(m):
    tmp=input().split(" ")
    edges.append([int(tmp[0])-1, int(tmp[1])-1])

hubensa_list = [0] * (m + 1)
hubensa_list[m] = n*(n-1)//2

def root(i):
    if node_groups[i] == i:
        #print(i, "is root.")
        return i
    else:
        #_1 = node_groups[i]
        node_groups[i] = root(node_groups[i])
        #_2 = node_groups[i]
        #print ("root: ", _1, _2)
        return node_groups[i]

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

def size(i):
    return group_sizes[root(i)]

def unite(a, b):
    a = root(a)
    b = root(b)

    if a == b:
        return
    
    group_sizes[a] += size(b)
    node_groups[b] = a


for i in range(m-1, -1, -1):
    edge = edges[i]
    # print("edge: ",edge)
    #print("node_groups: ", node_groups)
    node_1 = edge[0]
    node_2 = edge[1]

    root_1 = root(node_1)
    root_2 = root(node_2)
    if root_1 == root_2:
        hubensa_list[i] = hubensa_list[i+1]
        continue

    # 不便さをだす
    hubensa_list[i] = hubensa_list[i+1] - (size(root_1) * size(root_2))

    unite(root_1, root_2)

#print("node_groups: ", node_groups)


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