module UF
	implicit none
	private
	type Union_Find
		integer, allocatable :: par(:), rank(:), counter(:)
	end type Union_Find
	public Union_Find, make_Union_Find, unite, root,  same
	
	contains
	
	subroutine make_Union_Find(UFty, N)
		integer, intent(in)           :: N
		type(Union_Find), intent(out) :: UFty
		allocate(UFty%par(1:N), UFty%rank(1:N), UFty%counter(1:N))
		call format_Union_Find(UFty, N)
	end subroutine make_Union_Find
	
	subroutine format_Union_Find(UFty, N)
		integer, intent(in)             :: N
		type(Union_Find), intent(inout) :: UFty
		integer :: i
		do i = 1, N
			UFty%par(i) = i
		end do
		UFty%rank    = 0
		UFty%counter = 1
	end subroutine format_Union_Find
	
	subroutine unite(UFty, x, y)
		integer, value                  :: x, y
		type(Union_Find), intent(inout) :: UFty
		x = root(UFty, x)
		y = root(UFty, y)
		if(x == y) return
		if(UFty%rank(x) < UFty%rank(y)) then
			UFty%par(x)     = y
			UFty%counter(y) = UFty%counter(y) + UFty%counter(x)	
		else
			UFty%par(y)     = x
			UFty%counter(x) = UFty%counter(x) + UFty%counter(y)	
			if(UFty%rank(x) == UFty%rank(y)) UFty%rank(x) = UFty%rank(x) + 1
		end if
	end subroutine unite
	
	recursive function root(UFty, x) result(root_ans)
		integer, intent(in)             :: x
		type(Union_Find), intent(inout) :: UFty
		integer :: root_ans
		if(UFty%par(x) == x) then
			root_ans = x
			return
		else
			UFty%par(x) = root(UFty, UFty%par(x))
			root_ans    = UFty%par(x)
			return
		end if
	end function root
	
	logical function same(UFty, x, y)
		integer, intent(in) :: x, y
		type(Union_Find), intent(inout) :: UFty
		if(root(UFty, x) == root(UFty, y)) then
			same = .TRUE.
		else
			same = .FALSE. 
		end if
	end function same
end module UF

program main
	use UF
	implicit none
	integer :: N, M, i
	integer, allocatable :: A(:), B(:)
	integer(8), allocatable :: ans(:)
	type(Union_Find) :: Island
	read(*, *) N, M
	allocate(A(1:M), B(1:M), ans(1:M))
	do i = 1, M
		read(*, *) A(i), B(i)
	end do
	
	
	call make_Union_Find(Island, N)
	
	ans(M) = (N*(N-1)) / 2
	do i = M, 2, -1
		if(same(Island, A(i), B(i))) then
			ans(i-1) = ans(i)
		else
			ans(i-1) = ans(i) - Island%counter(root(Island, A(i)))*Island%counter(root(Island, B(i)))
		end if
		call unite(Island, A(i), B(i))
	end do
	do i = 1, M
		write(*, *) ans(i)
	end do
end program main