{-# 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

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 = makeTree n >>= calc >>= return . tail . res
            where
                calc uft = foldlM ff ([c], c, uft) . reverse $ map (map pred) 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 = return (prev : acc, prev, uft)
                            | otherwise = (next : acc, next, uft) <$ unionNodes a b uft
                            where
                                next = prev - sa * sb
                c = cmb2 n
                res (x, _, _) = x
                cmb2 x = product [1..x] `div` (product $ 2 : [1..(x - 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
findRoot v uft = readArray uft v >>= check 
    where
        check (root, s)
            | v == root = return v
            | otherwise = findRoot root uft >>= edit s
        edit s u = u <$ writeArray uft v (u, s)
            
unionNodes :: Int -> Int -> UFTree s -> ST s ()
unionNodes a b uft = mapM (\v -> findRoot v uft) [a, b] >>= check0
    where
        check0 [c, d]
            | c == d = return ()
            | otherwise = mapM (readArray uft) [c, d] >>= check1 c d
        check1 c d [(cv, cs), (dv, ds)]
            | cs < ds = writeArray uft c (dv, ds) >> writeArray uft d (dv, cs + ds)
            | otherwise = writeArray uft d (cv, cs) >> writeArray uft c (cv, cs + ds)

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

size :: Int -> UFTree s -> ST s Int 
size v uft = readArray uft v >>= check
    where
        check (root, s)
            | v == root = return s
            | otherwise = size root uft