{-# LANGUAGE DeriveFunctor                                          #-}
{-# LANGUAGE BangPatterns, BinaryLiterals, CPP, DerivingStrategies  #-}
{-# LANGUAGE DerivingVia, FlexibleContexts, FlexibleInstances       #-}
{-# LANGUAGE GeneralizedNewtypeDeriving, KindSignatures, LambdaCase #-}
{-# LANGUAGE MagicHash, MultiParamTypeClasses, MultiWayIf           #-}
{-# LANGUAGE NumericUnderscores, OverloadedStrings, PatternSynonyms #-}
{-# LANGUAGE RankNTypes, RecordWildCards, ScopedTypeVariables       #-}
{-# LANGUAGE StandaloneDeriving, TupleSections, TypeApplications    #-}
{-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns  #-}
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
{- base -}
import           Control.Applicative
import qualified Control.Arrow                 as Arrow
import           Control.Monad
import           Control.Monad.ST
import           Data.Bits
import           Data.Bool
import           Data.Complex
import qualified Data.Char                     as Char
import qualified Data.Foldable                 as Foldable
import           Data.Function
import qualified Data.List                     as List
import           Data.Maybe
import           Data.Monoid
import           Data.Ratio
import           Data.Ord
import           Data.Semigroup
import qualified Data.Word                     as Word
import           Foreign                       hiding (void)
import           GHC.Exts
import           Unsafe.Coerce
{- array -}
import qualified Data.Array.IO                 as ArrIO
import qualified Data.Array.MArray             as ArrMA
import qualified Data.Array.ST                 as ArrST
import qualified Data.Array.Storable           as ArrStore
import qualified Data.Array.Unboxed            as ArrU
{- bytestring -}
import qualified Data.ByteString               as BS
import qualified Data.ByteString.Builder       as BSB
import qualified Data.ByteString.Builder.Extra as BSBE
import qualified Data.ByteString.Char8         as BSC8
import qualified Data.ByteString.Lazy          as BSL
import qualified Data.ByteString.Lazy.Builder  as BSLB
import qualified Data.ByteString.Lazy.Char8    as BSLC8
import qualified Data.ByteString.Unsafe        as BSU
{- containers -}
import qualified Data.Graph                    as Graph
import           Data.IntMap                   (IntMap)
import qualified Data.IntMap                   as IntMap
import           Data.IntSet                   (IntSet)
import qualified Data.IntSet                   as IntSet
import qualified Data.Sequence                 as Seq
import qualified Data.Tree                     as Tree
{- integer-gmp -}
import           GHC.Integer.GMP.Internals
{- vector -}
import qualified Data.Vector                   as V
import qualified Data.Vector.Generic           as VG
import qualified Data.Vector.Generic.Mutable   as VGM
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Primitive         as VP
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
main :: IO ()
main = do
  n <- parse1
  m <- parse1
  let il = [0,0,0,0] :: [Int]
  xs <- VU.thaw $ VU.fromList il
  VUM.unsafeWrite xs n 1
  forM_ [1..m] $ \_ -> do
    (p, q) <- parse2
    a <- VUM.unsafeRead xs p
    b <- VUM.unsafeRead xs q
    VUM.unsafeWrite xs p b
    VUM.unsafeWrite xs q a
  ys <-  VU.unsafeFreeze xs
  print $ fromJust $ VU.elemIndex 1 ys
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parseChar :: [Char] -> VU.Vector Char
parseChar = VU.fromList
parse1 :: IO Int
parse1 = readLn
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine
parse4 :: IO (Int, Int, Int, Int)
parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------