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 qualified Data.IntMap as IMap
import Data.Sequence (ViewL(..),ViewR(..),(><),(<|),(|>),Seq)

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

setadj :: [[Int]] -> IMap.IntMap (Set.Set Int) -> IMap.IntMap (Set.Set Int)
setadj [] adj = adj
setadj (x:xs) adj = setadj xs (IMap.insert a add adj) 
                            where a = x!!0
                                  b = x!!1
                                  add = Set.union (Set.singleton b) cs
                                  cs = if IMap.member a adj == True
                                       then (IMap.!) adj a
                                       else Set.empty

--nsetadj :: [[Int]] -> IMap.IntMap (Set.Set Int) -> IMap.IntMap (Set.Set Int)
--nsetadj xs adj = setadj (xs ++ (map reverse xs)) adj

nsetadj :: [[Int]] -> IMap.IntMap (Set.Set Int) -> IMap.IntMap (Set.Set Int)
nsetadj [] adj = adj
nsetadj (x:xs) adj = nsetadj xs (IMap.insert b adda (IMap.insert a addb adj)) 
                                 where a = x!!0
                                       b = x!!1
                                       adda = Set.union (Set.singleton a) csa
                                       addb = Set.union (Set.singleton b) csb
                                       csa = if IMap.member b adj == True
                                             then (IMap.!) adj b
                                             else Set.empty                                       
                                       csb = if IMap.member a adj == True
                                             then (IMap.!) adj a
                                             else Set.empty


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 (nsetadj (ab \\ [ab!!(k-1)]) IMap.empty) chk | k <-[1..m]]
    --print $ length $ filter (==False) [connectchk q n (delete adjs) 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 -> IMap.IntMap (Set.Set Int) -> Set.Set Int -> Bool
connectchk q n adjs chk = foldr (&&) True [ (bsearch q n g adjs chk) /= [] | g <- [2..n] ]
         
adjset :: Int -> Int -> IMap.IntMap (Set.Set Int) -> Set.Set Int -> [Int]
adjset x n adjs chk  = Set.toList (Set.difference (f adjs x) chk)
                        where f adj a = if IMap.member a adj == True
                                        then (IMap.!) adj a
                                        else Set.empty

bsearch :: Sq.Seq [Int] -> Int -> Int -> (IMap.IntMap (Set.Set 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

    


Measured memory_bytes: 1404