import qualified Data.IntMap as IM
import qualified Data.Vector as V
main=print.solve.map(map read.words).lines=<<getContents
solve([n,m]:abs)=fst(f(-1)0 IM.empty)-1 where
  f s t v=(c+if p==q then 1 else 0,a)where
    p=IM.size v
    (c,a@(_,q))=foldr h(0,(IM.insert t p v,p))$g V.! t
    h i a@(c,(v,p))
      |i==s=a
      |IM.member i v=let q=v IM.! i in if q<p then(c,(IM.insert t q v,q))else(c,(v,p))
      |otherwise=let (c,(w,q))=f t i v in if q<p then(c,(IM.insert t q w,q))else(c,(w,p))
  g=V.accum(flip(:))(V.replicate n[])$concatMap(\[a,b]->[(a,b),(b,a)])$map(map pred)abs