{-# LANGUAGE TupleSections #-}

import Control.Monad
import Data.Array
import qualified Data.ByteString.Char8 as C
import Data.Graph
import qualified Data.IntMap.Strict as M
import Data.List
import Data.Ord
import qualified Data.Set as S
import Data.Tree

main = sub =<< get

sub [n,m] = sol n m <$> replicateM m get >>= print

get = unfoldr (C.readInt . C.dropWhile (<'0')) <$> C.getLine 

sol n m es = S.size (s `S.difference` c)
  where
  g = buildG (1,n) $ concatMap (\[u,v] -> [(u,v),(v,u)]) es
  t = head $ dff g
  s = S.fromList $ dfs t
    where
    dfs t = f t ++ concatMap dfs (subForest t)
    f t = fmap ((rootLabel t,) . rootLabel) (subForest t)
  bs = filter (`S.notMember` s) $ fmap ((\[u,v] -> (u,v)) . sortBy (comparing (lvl!))) es
  lvl = array (1,n) . concat . zipWith (\i -> fmap (,i)) [1..] $ levels t
  r = M.fromList . map (\(p,c) -> (c,p)) $ S.toList s
  pth ps u v 
    | u==v      = ps
    | otherwise = pth ((v',v):ps) u v' where v' = r M.! v
  c = S.fromList $ concatMap (uncurry (pth [])) bs