{-# LANGUAGE TupleSections #-}

import           Control.Monad       (replicateM, unless, when)
import           Control.Monad.ST    (ST, runST)
import           Control.Monad.State (StateT (runStateT), get, lift, put)
import           Data.Foldable       (for_)
import           Data.List           (mapAccumL)
import           Data.Tuple          (swap)
import           Data.Vector         (Vector, (!), (//))
import qualified Data.Vector         as V (enumFromTo, thaw)
import           Data.Vector.Mutable (STVector)
import qualified Data.Vector.Mutable as MV (read, write)

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  bridges <- replicateM m $ do
    [a, b] <- map read . words <$> getLine
    pure (a, b)
  for_ (solve n bridges) print

type Island = Int
type Bridge = (Island, Island)
type Inconvenience = Int

-- http://magnus.therning.org/posts/2015-06-09-000-mapaccum-in-monad.html
mapAccumM :: (Monad m, Traversable t) => (a -> b -> m (a, c)) -> a -> t b -> m (a, t c)
mapAccumM f a l = swap <$> runStateT (mapM go l) a
  where
    go i = do
      s <- get
      (s', r) <- lift $ f s i
      put s'
      return r

solve :: Int -> [Bridge] -> [Inconvenience]
-- solve n = reverse . snd . runST . mapAccumM f (maxInconvenience, toUnionFind n) . reverse
solve n bridges =
  reverse $ snd $ runST $ do
    uf <- toUnionFind n

    let
      f inconvenience (i1, i2) = do
          (s1, contain1) <- find i1 uf
          (s2, contain2) <- find i2 uf

          let
            bothContained = contain1 == contain2

            inconvenience' = inconvenience - (if bothContained then 0 else s1 * s2)

          unless bothContained $ union i1 i2 uf

          pure (inconvenience', inconvenience)

    mapAccumM f maxInconvenience $ reverse bridges
  where
    -- f ::
    --   (Inconvenience, UnionFind s Island) ->
    --   Bridge ->
    --   ST s ((Inconvenience, UnionFind s Island), Inconvenience)
    -- f (inconvenience, islandGroups) (i1, i2) = do
    --     (s1, contain1) <- find i1 islandGroups
    --     (s2, contain2) <- find i2 islandGroups

    --     let
    --       bothContained = contain1 == contain2

    --       inconvenience' = inconvenience - (if bothContained then 0 else s1 * s2)

    --     unless bothContained $ union i1 i2 islandGroups

    --     pure ((inconvenience', islandGroups), inconvenience)

    maxInconvenience :: Inconvenience
    maxInconvenience = n * (n - 1) `div` 2

type Size = Int
type UnionFind s a = STVector s (Size, a)
type UnionFind' a = Vector (Size, a)

toUnionFind :: Int -> ST s (UnionFind s Int)
toUnionFind n = V.thaw $ (1,) <$> V.enumFromTo 0 n

find :: Int -> UnionFind s Int -> ST s (Size, Int)
find i uf = do
  (s, i') <- MV.read uf i

  if i' == i
    then pure (s, i)
    else do
      (s', i'') <- find i' uf
      MV.write uf i' (s', i'')
      pure (s', i'')

union :: Int -> Int -> UnionFind s Int -> ST s ()
union i1 i2 uf = do
  (s1, representative1) <- find i1 uf
  (s2, representative2) <- find i2 uf

  when (representative1 /= representative2) $ do
    MV.write uf representative1 (s1, representative2)
    MV.write uf representative2 (s1 + s2, representative2)

-- size :: Int -> UnionFind' Int -> Int

{-
type UnionFind a = [[a]]

toUnionFind :: [a] -> UnionFind a
toUnionFind = map pure

find :: Eq a => a -> UnionFind a -> [a]
find x xss = fromJust $ L.find (x `elem`) xss

union :: Eq a => a -> a -> UnionFind a -> UnionFind a
union x1 x2 xss =
  let
    (contain1, notContain1) = partition (x1 `elem`) xss
    (contain2, notContain2) = partition (x2 `elem`) xss
    containNeither = notContain1 `intersect` notContain2
  in
    (head contain1 ++ head contain2) : containNeither

-- size :: Eq a => a -> [[a]] -> Int
-- size = (length .) . find
-}


Measured memory_bytes: 77180