{-# LANGUAGE BangPatterns #-}
import Control.Arrow (second)
import Control.Monad
import Control.Monad.Fix
import Data.Foldable (foldl')
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.ByteString.Char8 as B
import Data.ByteString.Internal (accursedUnutterablePerformIO)

uread :: VUM.Unbox a => Int -> VUM.IOVector a -> a
uread i v = accursedUnutterablePerformIO $ VUM.unsafeRead v i

uwrite :: VUM.Unbox a => Int -> a -> VUM.IOVector a -> VUM.IOVector a
uwrite i a v = accursedUnutterablePerformIO $ VUM.unsafeWrite v i a >> return v

uswap :: VUM.Unbox a => Int -> Int -> VUM.IOVector a -> VUM.IOVector a
uswap i j v = accursedUnutterablePerformIO $ VUM.unsafeSwap v i j >> return v

ufreeze :: VUM.Unbox a => VUM.IOVector a -> VU.Vector a
ufreeze v = accursedUnutterablePerformIO $ VU.unsafeFreeze v

uthaw :: VUM.Unbox a => VU.Vector a -> VUM.IOVector a
uthaw v = accursedUnutterablePerformIO $ VU.unsafeThaw v

newtype UnionFind = UnionFind (VUM.IOVector Int, VUM.IOVector Int)

findUF :: Int -> UnionFind -> (Int, UnionFind)
findUF k uf = (\(a, b, _) -> (a, b)) $ fix
  ( \f (k, uf, path) -> case ureadElem k uf of
    n | n == k -> (n, foldl' (\acc p -> uwriteElem p n acc) uf path, [])
    n          -> f (n, uf, n : path)
  )
  (k, uf, [k])

sizeUF :: UnionFind -> Int -> Int
sizeUF (UnionFind (_, sizes)) i = uread i sizes

ureadElem :: Int -> UnionFind -> Int
ureadElem i (UnionFind (elem, _)) = uread i elem

uwriteElem :: Int -> Int -> UnionFind -> UnionFind
uwriteElem i a (UnionFind (elem, sizes)) = UnionFind (uwrite i a elem, sizes)

uwriteSize :: Int -> Int -> UnionFind -> UnionFind
uwriteSize i a (UnionFind (elem, sizes)) = UnionFind (elem, uwrite i a sizes)

unionUF :: UnionFind -> Int -> Int -> (UnionFind, Int)
unionUF uf i j =
  let
    (pi, uf1) = findUF i uf
    (pj, uf2) = findUF j uf1
    si        = sizeUF uf2 pi
    sj        = sizeUF uf2 pj
    sij       = si + sj
  in
    if pi == pj
    then
      (uf2, 0)
    else
      if si < sj
      then
        (uwriteSize pi 0 $ uwriteSize pj sij $ uwriteElem pi pj uf2, si * sj)
      else
        (uwriteSize pj 0 $ uwriteSize pi sij $ uwriteElem pj pi uf2, si * sj)

comb2 k = k * (k - 1) `div` 2

solve :: Int -> Int -> VU.Vector (Int, Int) -> VU.Vector Int
solve n m abs = ufreeze $ (\(_, _, acc) -> acc) $ VU.foldr'
  go
  (group, 0, accursedUnutterablePerformIO $ VUM.replicate m 0)
  abs
 where
  go (a, b) (uf, k, acc) =
    let (uf', d) = unionUF uf a b
        prev     = if k == 0 then 0 else uread (k - 1) acc
    in  (uf', k + 1, uwrite k (prev + d) acc)

  nC2 = comb2 n

  group :: UnionFind
  group = UnionFind
    (uthaw $ VU.enumFromN 0 n, accursedUnutterablePerformIO $ VUM.replicate n 1)

main = do
  let readInt = fmap (second B.tail) . B.readInt

  nm  <- VU.unfoldrN 2 readInt <$> B.getLine
  abs <- VU.replicateM
    (nm VU.! 1)
    (   (\vec -> (vec VU.! 0 - 1, vec VU.! 1 - 1))
    .   VU.unfoldrN 2 readInt
    <$> B.getLine
    )

  let solutions = solve (nm VU.! 0) (nm VU.! 1) abs
  let nC2       = comb2 $ nm VU.! 0

  mapM_ (print . (nC2 -) . (solutions VU.!)) [nm VU.! 1 - 2, nm VU.! 1 - 3 .. 0]
  print nC2


Measured memory_bytes: 32380