
{-# LANGUAGE BangPatterns #-}

import Data.Array (Array, listArray, accumArray, (!))
import Data.List (sortOn, sortBy, unfoldr)
import Data.Char (isSpace)
import qualified Data.ByteString.Char8 as B


import Data.Array.ST (STUArray, runSTUArray)
import Data.Array.MArray
import Control.Monad.ST (ST, runST)
import Control.Monad (when)


type UnionFind s = (STUArray s Int Int, STUArray s Int Int)

inituf :: (Int,Int) -> ST s (UnionFind s)
inituf (s,t) = (,) <$> newListArray (s,t) [s..] <*> newArray (s,t) 1

find :: UnionFind s -> Int -> ST s Int
find uf@(par,_) x = do
  p <- readArray par x
  if p==x then return x
  else do
    p' <- find uf p
    writeArray par x p'
    return p'

same :: UnionFind s -> Int -> Int -> ST s Bool
same uf x y = (==) <$> find uf x <*> find uf y

union :: UnionFind s -> Int -> Int -> ST s Int
union uf@(par,siz) x y = do
  px <- find uf x
  py <- find uf y
  when (px/=py) $ do
    sx <- readArray siz px
    sy <- readArray siz py
    writeArray par py px
    writeArray siz px (sx+sy)
  return px

size :: UnionFind s -> Int -> ST s Int
size (par,siz) x = readArray par x >>= readArray siz


type T a = (a,a)
f :: [a] -> T a
f [x,y] = (x,y)

permu n 0 = 1
permu n k = n * permu (n-1) (k-1)

choice n k = permu n k `div` permu k k

solv n m xs
  = runST $ do
    uf <- inituf (1,n)
    go uf (reverse xs) (choice n 2)
  where
    go :: UnionFind s -> [T Int] -> Int -> ST s [Int]
    go uf [] _ = return []
    go uf ((a,b):xs) c = do
      ga <- find uf a
      gb <- find uf b
      if ga==gb then (c:) <$> go uf xs c
      else do
        sa <- size uf ga
        sb <- size uf gb
        union uf a b
        let c' = c - sa*sb
        (c:) <$> go uf xs c'

readT :: B.ByteString -> Maybe (T Int, B.ByteString)
readT bs = do
  (x,bs') <- B.readInt . B.dropWhile isSpace $ bs
  (y,bs'') <- B.readInt . B.dropWhile isSpace $ bs'
  return ((x,y),bs'')

main = do
  [n,m] <- map read . words <$> getLine :: IO [Int]
  xs <- take m . unfoldr readT <$> B.getContents :: IO [T Int]
  putStr . unlines . map show . reverse $ solv n m xs
