{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bits                   (shiftR)
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char                   (isSpace)
import           Data.STRef
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  pys <- V.unfoldrN m parseInt2 <$> B.getContents
  putStr $ solve n m pys

solve :: Int -> Int -> V.Vector (Int, Int) -> String
solve _ m pys = unlines . map (tail . show) $ V.toList ids
  where
    ids = runST $ do
      v <- VM.new m :: ST s (VM.STVector s Int)
      cr <- newSTRef 1 :: ST s (STRef s Int)
      VM.write v (get3 (pyis V.! 0)) (encodeId (get1 (pyis V.! 0)) 1)
      forM_ [1 .. m - 1] $ \i -> do
        if get1 (pyis V.! i) /= get1 (pyis V.! (i - 1))
          then writeSTRef cr 1
          else modifySTRef cr (+ 1)
        c <- readSTRef cr
        VM.write v (get3 (pyis V.! i)) (encodeId (get1 (pyis V.! i)) c)
      V.freeze v
    pyis = sort' . V.zip pys $ V.enumFromN 0 m :: V.Vector ((Int, Int), Int)

get1 :: ((a, a), a) -> a
get1 = fst . fst

-- get2 :: ((a, a), a) -> a
-- get2 = snd . fst

get3 :: ((a, a), a) -> a
get3 = snd

encodeId :: Int -> Int -> Int
encodeId p r = 1000000000000 + p * 1000000 + r

sort' :: (Ord a, V.Unbox a) => V.Vector a -> V.Vector a
sort' = V.modify (\v -> quicksort v 0 (VM.length v))

-- https://github.com/as-capabl/haskell-qsort-pfm/blob/master/src/UV.hs
quicksort :: (Ord a, V.Unbox a) => VM.STVector s a -> Int -> Int -> ST s ()
quicksort work iStart iEnd
    | iEnd - iStart <= 1 = return ()
    | otherwise = do
        pivot <- VM.unsafeRead work (((iEnd - iStart) `shiftR` 1) + iStart)
        med <- divide pivot iStart (iEnd - 1)
        quicksort work iStart med
        quicksort work med iEnd
  where
    divide pivot iS' iE'
        | iS' > iE' = return iS'
        | otherwise = do
            lower <- shrinkLower pivot iS' iE'
            higher <- shrinkHigher pivot lower iE'
            if lower >= higher
              then do
                return lower
              else do
                swapWork lower higher
                divide pivot (lower + 1) (higher - 1)

    shrinkLower pivot iS' iE'
        | iS' > iE' = return iS'
        | otherwise = do
            x <- VM.unsafeRead work iS'
            if x >= pivot
              then
                return iS'
              else
                shrinkLower pivot (iS' + 1) iE'

    shrinkHigher pivot iS' iE'
        | iS' > iE' = return iE'
        | otherwise = do
            x <- VM.unsafeRead work iE'
            if x <= pivot
              then
                return iE'
              else
                shrinkHigher pivot iS' (iE' - 1)

    swapWork i j = VM.unsafeSwap work i j

type Parser a = B.ByteString -> Maybe (a, B.ByteString)

parseInt2 :: Parser (Int, Int)
parseInt2 = runStateT $
  (,) <$> StateT (B.readInt . B.dropWhile isSpace)
  <*> StateT (B.readInt . B.unsafeTail)
