{-# LANGUAGE FlexibleContexts #-}
import Control.Monad.ST
import Data.Array.ST
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Foldable
import Debug.Trace

main :: IO ()
main = readLine >>= main'
    where
        main' [n, m] = readContents m >>= printRes . solve n m
        printRes = mapM_ print 

solve :: Int -> Int -> [[Int]] -> [Int]
solve n m bs = runST stActions
    where
        stActions = res <$> (makeTree n >>= calc)
            where
                calc uft = foldlM ff ([c], c, uft) . reverse . map (map pred) $ tail bs
                ff (acc, prev, uft) [a, b] = vals >>= check
                    where
                        vals = (,,) <$> isSame a b uft <*> size a uft <*> size b uft
                        check (f, sa, sb)
                            | f = getAssocs uft >>= traceShowM >> return (prev : acc, prev, uft)
                            | otherwise = getAssocs uft >>= traceShowM >> (next : acc, next, uft) <$ unionNodes a b uft
                            where
                                next = prev - sa * sb
                c = cmb2 n
                res (x, _, _) = x
                cmb2 x = (x * (x - 1)) `div` 2


readLine :: IO [Int]
readLine = unfoldr (fmap (second (maybe B.empty snd . B.uncons)) . B.readInt) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine


type UFTree s = STArray s Int (Int, Int)

makeTree :: Int -> ST s (UFTree s)
makeTree n = newListArray (0, n - 1) . zip [0..(n - 1)] $ repeat 1

findRoot :: Int -> UFTree s -> ST s (Int, Int)
findRoot v uft = readArray uft v >>= check
    where
        check res@(root, _)
            | v == root = return res
            | otherwise = findRoot root uft >>= edit
        edit res = res <$ writeArray uft v res
            
unionNodes :: Int -> Int -> UFTree s -> ST s ()
unionNodes a b uft = mapM (`findRoot` uft) [a, b] >>= check
    where
        check [(c, cs), (d, ds)]
            | c == d = return ()
            | cs < ds = writeArray uft c (d, cs + ds) >> writeArray uft d (d, ds + cs)
            | otherwise = writeArray uft d (c, cs + ds) >> writeArray uft c (c, cs + ds) 

isSame :: Int -> Int -> UFTree s -> ST s Bool
isSame a b uft = (== 1) . length . group <$> mapM (`findRoot` uft) [a, b]

size :: Int -> UFTree s -> ST s Int 
size v uft = snd <$> findRoot v uft