module Main where

import Control.Arrow
import Data.Array
import Data.Bool
import Data.Graph
import Data.List

main :: IO ()
main = interact (show . (bool (-1) . id <*> (100000 >=)) . (count [] 0 . pred <*> graph . graphFromEdges . series) . read)

graph :: Gr -> Graph
graph (g,_,_) = g

type Nd = Int
type Id = Int
type Gr = (Graph, Vertex -> (Nd,Id,[Id]), Id -> Maybe Vertex)

count :: [Vertex] -> Vertex -> Vertex -> Graph -> Int
count vs s e g
  | s == e    = 1
  | otherwise = case (g ! s) \\ vs of
      []  -> 100000
      xs  -> succ $ minimum $ map (\ x -> count (s:vs) x e g) xs

series :: Int -> [(Int,Int,[Int])]
series n = take n $ map (rmout n) $ zipWith mkEdge [1..] $ concat $ unfoldr phi [0]
  where
    phi xs = Just (ys, zs)
      where
        ys = map succ xs
        zs = xs ++ ys

mkEdge :: Int -> Int -> (Int,Int,[Int])
mkEdge k n = (n,k,[k+n,k-n])

rmout :: Int -> (Int,Int,[Int]) -> (Int,Int,[Int])
rmout n (nd,k,es) = (nd,k,filter (uncurry (&&) . ((0<) &&& (<=n))) es)