CodeEff/ECCO huggingface dataset:
# Original solution
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            while self.parent[x] >= 0:
                if self.parent[self.parent[x]] >= 0:
                    self.parent[x] = self.parent[self.parent[x]]
                x = self.parent[x]
#        self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return x

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


n,m=[int(i) for i in input().split()]

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

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

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

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





# Optimized solution
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            while self.parent[x] >= 0 and self.parent[self.parent[x]] >= 0:
                self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
#        self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return (x if self.parent[x] < 0 else self.parent[x])

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


n,m=[int(i) for i in input().split()]

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

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

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

for i in range(m):
    print((ans[m-i-1]))
# Original solution
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            while self.parent[x] >= 0 and self.parent[self.parent[x]] >= 0:
                self.parent[x] = self.parent[self.parent[x]]
                x = self.parent[x]
#        self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return (x if self.parent[x] < 0 else self.parent[x])

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


n,m=[int(i) for i in input().split()]

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

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

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

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





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

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        elif self.parent[self.parent[x]] < 0:
            return self.parent[x]
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


n,m=[int(i) for i in input().split()]

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

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

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

for i in range(m):
    print((ans[m-i-1]))
# Original solution
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        elif self.parent[self.parent[x]] < 0:
            return self.parent[x]
        else:
            self.parent[self.parent[x]] = self.parent[x] = self.root(self.parent[self.parent[x]]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


n,m=[int(i) for i in input().split()]

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

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

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

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





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

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        px=self.parent[x]
        if px < 0:
            return x
        ppx=self.parent[px]
        if ppx < 0:
            return px
        self.parent[px] = self.parent[x] = self.root(ppx) #xをxの根に直接つなぐ
        return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


n,m=[int(i) for i in input().split()]

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

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

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

for i in range(m):
    print((ans[m-i-1]))
# Original solution
n,m=list(map(int,input().split()))
list_p=[]
for i in range(0,m):
    a,b=list(map(int,input().split()))
    list_p.append([a,b])
list_p.reverse()
group=[]
count=[]
group.append(list_p[0])
count.append(0)
for i in range(1,m):
    number=0
    index=0
    ifa=0
    ifb=0
    for j in group:
        number=number+len(j)*(len(j)-1)//2
        if list_p[i][0] in j:
            ifa=1
            placea=index
        if list_p[i][1] in j:
            ifb=1
            placeb=index
        index=index+1
    count.append(number)
    if ifa==0 and ifb==0:
        group.append(list_p[i])
    elif ifa==1 and ifb==0:
        group[placea].append(list_p[i][1])
    elif ifa==0 and ifb==1:
        group[placeb].append(list_p[i][0])
    elif ifa==1 and ifb==1:
        if placea==placeb:
            pass
        else:
            group[placea].extend(group[placeb])
            group.pop(placeb)
x=n*(n-1)//2
count.reverse()
for i in count:
    print((x-i))


    


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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.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[y]
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.size[x]=self.size[x]+self.size[y]

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

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

n,m=list(map(int,input().split()))
a_list=[]
b_list=[]
for i in range(m):
    a,b=list(map(int,input().split()))
    a_list.append(a)
    b_list.append(b)
ans=[n*(n-1)//2]
U=UnionFind(n)
for i in range(m-1,0,-1):
    if U.same_check(a_list[i],b_list[i]):
        ans.append(ans[-1])
    else:
        ans.append(ans[-1]-U.Size(a_list[i])*U.Size(b_list[i]))
        U.union(a_list[i],b_list[i])
for i in range(m-1,-1,-1):
    print((ans[i]))
# Original solution
class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = [int(x) for x in input().split()]
b = []
for i in range(m):
  b.append(tuple(int(x) - 1 for x in input().split()))
r = []
t = n*(n-1)//2
ds = Unionfind(n)
for i in range(m):
  q, p = b[-i-1]
  r.insert(0, t)
  qq, pp = ds.find(p), ds.find(q)
  if pp != qq:
    t -= ds.size[pp] * ds.size[qq]
  ds.union(p, q)
for x in r:
  print(x)

# Optimized solution
class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = list(map(int, input().split()))
bridge = [tuple(map(int, input().split())) for _ in range(m)]
bridge.reverse()
uf = Unionfind(n)
cur = n * (n-1) // 2
ans = [cur]
for a, b in bridge:
    ap = uf.find(a-1)
    bp = uf.find(b-1)
    if ap != bp:
        cur -= uf.size[ap] * uf.size[bp]
    uf.union(a-1, b-1)
    ans.append(cur)
for a in reversed(ans[0:m]):
    print(a)
# Original solution
class DisjointSet():
    def __init__(self, n):
        self._p = [x for x in range(n)]
        self._size = [-1 for x in range(n)]
    
    def find(self, p):
        while p != self._p[p]:
            p = self._p[p]
        return p

    def union(self, p, q):
        pp, qq = self.find(p), self.find(q)
        if pp != qq:
            if self._size[pp] > self._size[qq]:
                self._p[qq] = pp
                self._size[pp] += self._size[qq]
            else:
                self._p[pp] = qq
                self._size[qq] += self._size[pp]
    
    def size(self, p):
        return self._size[self.find(p)]


n, m = [int(x) for x in input().split()]
b =  [tuple([int(x) - 1 for x in input().split()]) for _ in range(m)]
b.reverse()
r = []
t = n*(n-1)//2
ds = DisjointSet(n)
for q, p in b:
  r.append(t)
  qq, pp = ds.find(p), ds.find(q)
  if pp != qq:
    t -= ds.size(pp) * ds.size(qq)
  ds.union(p, q)
for x in reversed(r):
  print(x)

# Optimized solution
class DisjointSet():
    def __init__(self, n):
        self._p = [x for x in range(n)]
        self._size = [-1 for x in range(n)]
        self._rank = [0 for x in range(n)]
    
    def find(self, p):
        while p != self._p[p]:
            p = self._p[p]
        return p

    def union(self, p, q):
        pp, qq = self.find(p), self.find(q)
        if pp != qq:
            if self._rank[pp] > self._rank[qq]:
                self._p[qq] = pp
                self._rank[pp] += 1
                self._size[pp] += self._size[qq]
            else:
                self._p[pp] = qq
                self._rank[qq] += 1
                self._size[qq] += self._size[pp]
    
    def size(self, p):
        return self._size[self.find(p)]


n, m = [int(x) for x in input().split()]
b =  [tuple([int(x) - 1 for x in input().split()]) for _ in range(m)]
b.reverse()
r = []
t = n*(n-1)//2
ds = DisjointSet(n)
for q, p in b:
  r.append(t)
  qq, pp = ds.find(p), ds.find(q)
  if pp != qq:
    t -= ds.size(pp) * ds.size(qq)
  ds.union(p, q)
for x in reversed(r):
  print(x)
# Original solution
import sys
readline = sys.stdin.readline
N, M = map(int, input().split())
ab = [tuple(map(lambda x: int(x) - 1, readline().split())) for _ in range(M)]
class UnionFind:
    def __init__(self, size):
        self.rank = [-1] * size
        self.number = [1] * size
    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x
    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]
uf = UnionFind(N)
p = N * (N - 1) // 2
ans = [p]
for x, y in ab[1:][::-1]:
    px = uf.find(x)
    py = uf.find(y)
    if px != py:
        p -= uf.number[px] * uf.number[py]
        uf.union(px, py)
    ans.append(p)
print(*ans[::-1], sep="\n")


# Optimized solution
import sys
readline = sys.stdin.readline
N, M = map(int, input().split())
ab = [tuple(map(int, readline().split())) for _ in range(M)]
class UnionFind:
    def __init__(self, size):
        self.rank = [-1] * (size + 1)
        self.number = [1] * (size + 1)
    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x
    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]
uf = UnionFind(N)
p = N * (N - 1) // 2
ans = [p]
for x, y in ab[1:][::-1]:
    px = uf.find(x)
    py = uf.find(y)
    if px != py:
        p -= uf.number[px] * uf.number[py]
        uf.union(px, py)
    ans.append(p)
print(*ans[::-1], sep="\n")
# Original solution
n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
nodes = [[i, [i], 1] for i in range(n + 1)]
res = [n * (n - 1) // 2]
for a, b in reversed(ls):
    x = nodes[a][0]
    y = nodes[b][0]
    if x == y:
        res.append(res[-1])
    else:
        if x > y:
            x, y = y, x
        res.append(res[-1] - nodes[x][2] * nodes[y][2])
        nodes[x][1] += nodes[y][1]
        nodes[x][2] += nodes[y][2]
        for z in nodes[x][1]:
            nodes[z][0] = x
print(*reversed(res[:-1]), sep='\n')


# Optimized solution
n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]

parents = list(range(n + 1))
ranks = [0 for _ in range(n + 1)]


def find(x):
    if parents[x] == x:
        return x
    parents[x] = find(parents[x])
    return parents[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if ranks[x] < ranks[y]:
        parents[x] = y
    else:
        parents[y] = x
        if ranks[x] == ranks[y]:
            ranks[x] += 1


res = [n * (n - 1) // 2]
nums = [1 for _ in range(n + 1)]
for a, b in reversed(ls):
    aa = find(a)
    bb = find(b)
    if aa == bb:
        res.append(res[-1])
    else:
        res.append(res[-1] - nums[aa] * nums[bb])
        nums[aa] = nums[bb] = nums[aa] + nums[bb]
        unite(aa, bb)
print(*reversed(res[:-1]), sep='\n')
# Original solution
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        self.link(self.find_set(u), self.find_set(v))

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def link(self, u, v):
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


uf = UnionFind(n)

sm = n * (n - 1) // 2
ans = [sm]
for a, b in ab[-1:0:-1]:
    a -= 1
    b -= 1
    if not uf.same(a, b):
        sm -= uf.get_size(a) * uf.get_size(b)
        uf.unite(a, b)
    ans.append(sm)

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


# Optimized solution
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


uf = UnionFind(n)

sm = n * (n - 1) // 2
ans = [sm]
for a, b in ab[-1:0:-1]:
    a -= 1
    b -= 1
    if not uf.same(a, b):
        sm -= uf.get_size(a) * uf.get_size(b)
        uf.unite(a, b)
    ans.append(sm)

print(*ans[::-1], sep="\n")
# 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()))
    A[i] -= 1
    B[i] -= 1

parent = [-1]*N
depth = [0] * N

def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d

P = [1]*N
S = (N*(N-1))//2

ans = [0] * M
ans[M-1] = S

#print(A)
#print(B)

for i in range(M-1):
#    print(parent)
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
#    print(A[j],B[j],bA,bB)
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S

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


# 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()))
    A[i] -= 1
    B[i] -= 1

parent = [-1]*N

def boss(n):
    if parent[n] < 0:
        return n
    else:
        b = boss(parent[n])
        parent[n] = b
        return b

P = [1]*N
S = (N*(N-1))//2

ans = [0] * M
ans[M-1] = S

for i in range(M-1):
    j = M-1-i
    bA = boss(A[j])
    bB = boss(B[j])
    if bA != bB:
        if P[bA] < P[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] += P[bB]
    ans[j-1] = S

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