{-# LANGUAGE BangPatterns, MagicHash #-}
import Control.Monad
import Control.Applicative
import Data.List
import Data.Maybe
import Data.Bits
import qualified Data.IntMap.Strict as M
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed ((!))
import Data.Tuple
import Data.Ord (Down(..))
import Data.Coerce
                                 
query :: Int -> [(Int,Int)] -> Int
query n =
  fromJust . findIndex M.null
  . iterate (\m -> snd $ M.split (snd (M.findMin m) - 1) m)
  . foldl' (\m (y,x) -> let (_,m') = M.split x m in M.insert x y m') M.empty
  . (coerce :: [(Down Int, Int)] -> [(Int, Int)])
  . sort . (coerce :: [(Int,Int)] -> [(Down Int, Int)])
     
main :: IO ()
main = do
  [n,m] <- map read . words <$> getLine
  bas <- replicateM m $ (\(x:y:_)->(y,x)) . map read . words  <$> getLine
  putStrLn $ show $ query n bas
