
import Data.Array.IO

parsePair :: IO (Int, Int)
parsePair = do
    [a,b] <- (fmap read . words) <$> getLine :: IO [Int]
    return (a,b)

main = do
    (n,m) <- parsePair
    arr <- newArray ((1,1), (n,n)) False :: IO (IOArray (Int,Int) Bool)
    bridges <- reverse <$> (sequence $ replicate m parsePair)
    res <- solve arr n bridges 0 []
    mapM_ print res


littleGauss :: Int -> Int
littleGauss n = (n^2+n) `div` 2

validIndices :: Int -> [(Int, Int)]
validIndices n = [(i,j) | i<-[1..n], j<-[1..n], i<j]

countTrues :: IOArray (Int,Int) Bool -> IO Int
countTrues arr = do
    ls <- getElems arr
    return $ length $ filter id ls



solve :: IOArray (Int,Int) Bool -> Int -> [(Int,Int)] -> Int -> [Int] -> IO [Int]
solve arr n []     _    ac = return ac
solve arr n (b:bs) prev ac = do
    let cur = (littleGauss (n-1) - prev)
    isAlreadyPossible <- readArray arr b
    if isAlreadyPossible
        then solve arr n bs prev (cur:ac)
        else do
            writeArray arr b True
            newCnt <- fill arr n
            solve arr n bs newCnt (cur:ac)

fill :: IOArray (Int,Int) Bool -> Int -> IO Int
fill arr n = do
    prevTrueCount <- countTrues arr
    fillOnce arr n (validIndices n)
    newTrueCount <- countTrues arr
    if prevTrueCount == newTrueCount
        then return prevTrueCount
        else fill arr n

fillOnce :: IOArray (Int,Int) Bool -> Int -> [(Int,Int)] -> IO ()
fillOnce arr n []     = return ()
fillOnce arr n (b:bs) = do
    directPath <- readArray arr b
    if directPath
        then fillOnce arr n bs
        else do
            ls <- sequence $ map (indirectPath arr b) [1..n]
            if or ls
                then do
                    writeArray arr b True
                    fillOnce arr n bs
                else fillOnce arr n bs

indirectPath :: IOArray (Int,Int) Bool -> (Int,Int) -> Int -> IO Bool
indirectPath arr (from, to) pass = do
    fstP <- readArray arr (min from pass, max from pass)
    sndP <- readArray arr (min pass to, max pass to)
    return $ fstP && sndP

