-- 132 e
import qualified Data.IntMap as IM
import qualified Data.IntSet as IS
import Data.Maybe

func :: Int -> [Int] -> ([(Int,Int)],[Int])
func num array =
    _inner num array []
    where
        _inner 0 _array _result = (_result,_array)
        _inner _num (i1:i2:rest) _result = 
            _inner (_num - 1) rest ((i1,i2):_result)

makemap :: [(Int,Int)] -> IM.IntMap IS.IntSet
makemap array_ =
    foldr func IM.empty array_
    where
        func :: (Int,Int) -> IM.IntMap IS.IntSet -> IM.IntMap IS.IntSet
        func (u,v) = IM.insertWith IS.union u (IS.singleton v)

solve2 :: Int -> IM.IntMap IS.IntSet -> IS.IntSet -> IS.IntSet -> Int -> Int
solve2 g dic already nexts level =
    if IS.member g nexts 
        then 
            level
        else
            let next2 = IS.unions $ catMaybes $ map (dic IM.!?) $ IS.elems nexts in
            let next3 = IS.difference next2 already in
            let next_already = IS.union already nexts in
            if (IS.null next2) 
                then 
                    -1
                else
                    solve2 g dic next_already next3 (1+level)

solve :: [Int] -> Int
solve (n:m:rest)  = 
    (solve2 t dic ss ss 0)
    where
        (uvs,[s,t]) = func m rest
        test = [(u1,v3)| (u1,v1)<-uvs,(u2,v2)<-uvs,(u3,v3)<-uvs,v1 == u2 && v2 == u3 && u1 /= v3]
        dic = makemap [(u1,v3)| (u1,v1)<-uvs,(u2,v2)<-uvs,(u3,v3)<-uvs,v1 == u2 && v2 == u3 && u1 /= v3]
        ss = IS.singleton s
    
main = interact $ show.solve.map read.words
