module Main where
import Data.Maybe
import Data.List(foldl', union)

main = interact $ printer . solver . parser
int = read :: String -> Int
count a bs = length $ filter (==a) bs
split n ls = map (take n) $ takeWhile (/=[]) $ iterate (drop n) ls

printer = unlines . (:[]) . show
parser input = (n, m, edges)
  where
    (n:m:abs) = map int $ words input
    edges = map (\[x,y]->(x,y)) $ split 2 abs


nextNode :: Int -> [(Int,Int)] -> [Int]
nextNode p edges = map (\(a,b)->if p==a then b else a) $ filter (\(a,b)->p==a||p==b) edges

neighbours :: Int -> [(Int,Int)] -> [(Int, [Int])]
neighbours n edges = [(p,nextNode p edges)|p<-[1..n]]

convergence (n1:n2:ns) = if n1==n2 then n1 else convergence (n2:ns)

solver :: (Int, Int, [(Int,Int)]) -> Int
solver (n, m, edges)
  = (\x -> m - x) $ count True $
    do target <- edges
       let edge2 = filter (/=target) edges
       let nei = neighbours n edge2
       let func xs = foldl' union xs $ map (\x -> fromJust $ lookup x nei) xs
       let g = convergence $ iterate func [fst target]
       return (elem (snd target) g)
      
