import Control.Monad
import Control.Applicative
import Data.List
import qualified Data.Map as Map
import Data.Array
import qualified Data.ByteString.Char8 as BC
import Data.Maybe
import qualified Data.Set as Set
import qualified Data.Sequence as Sq
import Data.Sequence (ViewL(..),ViewR(..),(><),(<|),(|>),Seq)

bsreadInt :: BC.ByteString -> Int
bsreadInt = fst . fromJust . BC.readInt

setadj :: Int -> [[Int]] -> [[Int]]
setadj n sn = setadj_ startset sn
              where startset = replicate n []

setadj_ :: [[Int]] -> [[Int]] -> [[Int]]
setadj_ an [] = an
setadj_ an (s:sn) = setadj_ bn sn
                    where sa = head s
                          sb = last s
                          bn = (take sa an) ++ [sb : (an!!sa)] ++ drop (sa+1) an

--無向隣接リスト作成
nsetadj :: Int -> [[Int]] -> [[Int]]
nsetadj n sn = setadj_ startset snx
              where startset = replicate (n+1) []
                    snx = sn ++ (map reverse sn)
                    
main = do
    [n,m] <- map bsreadInt . BC.words <$> BC.getLine --n頂点，m本の辺
    ab <- map ((map bsreadInt . BC.words)) <$> replicateM m BC.getLine -- a-->b :path のリスト
    let q = Sq.singleton [1]
    let chk = Set.singleton 1
    print $ length $ filter (==False) [connectchk q n (listArray (1,n) (drop 1 (nsetadj n (ab \\ [ab!!(k-1)] )))) chk | k <- [1..m]]
    --print $ length $ filter (==False) [connectchk q n (Set.union (Set.fromList (ab \\ [ab!!(k-1)] ) ) (Set.fromList (map reverse (ab \\ [ab!!(k-1)] )) )) chk | k <- [1..m]]

connectchk :: Sq.Seq [Int] -> Int -> (Array Int [Int]) -> Set.Set Int -> Bool
connectchk q n adjs chk = foldr (&&) True [ (bsearch q n g adjs chk) /= [] | g <- [2..n] ]
         
adjset :: Int -> Int  -> (Array Int [Int]) -> Set.Set Int -> [Int]
adjset x n adjs chk  = (adjs!x) \\ Set.toList chk

bsearch :: Sq.Seq [Int] -> Int -> Int -> (Array Int [Int]) -> Set.Set Int -> [Int]
bsearch q n g adjs chk = if Sq.length q == 0
                         then []
                         else if head (sqleft q) == g
                              then reverse $ sqleft q
                              else bsearch q2 n g adjs chk2
                                where qa = sqleft q
                                      q2 = (Sq.drop 1 q) >< (Sq.fromList add)
                                      add = [x : qa | x <- adjset (head qa) n adjs chk]
                                      chk2 = Set.union chk (Set.fromList (adjset (head qa) n adjs chk))
                                      
sqleft :: Seq a -> a
sqleft q = sqleft_(Sq.viewl q)
sqleft_ :: ViewL a -> a
sqleft_ (x :< xs) = x
sqright :: Seq a -> a
sqright q = sqright_(Sq.viewr q)
sqright_ :: ViewR a -> a
sqright_ (xs :> x) = x

    
