module m_deque ! 双端キュー. リングバッファ実装. itemtypeを変更して使え
  implicit none

  private
  public :: itemtype, dequetype
  integer, parameter :: MINSIZE = 2

  type itemtype
    integer :: x(3)
  end type itemtype

  type dequetype
    integer :: n = 0, st = 1, memsize = 0
    type(itemtype), allocatable :: ary(:)
  contains
    procedure :: push_left, push_right, pop_left, pop_right, slice, dump
  end type dequetype

  contains

  subroutine resize_up(dq)
    ! 初めの要素追加または n == memsize で呼ばれる
    type(dequetype), intent(inout) :: dq
    type(itemtype), allocatable :: tmp(:)
    if (dq%memsize == 0) then
      dq%memsize = MINSIZE
      allocate (dq%ary(dq%memsize))
      dq%n = 0
      dq%st = max(1, dq%memsize / 8)
    else
      if (dq%n /= dq%memsize) stop 2
      allocate (tmp(dq%n))
      tmp(:) = slice(dq, 1, dq%n)
      dq%memsize = dq%memsize * 2
      deallocate (dq%ary)
      allocate (dq%ary(dq%memsize))
      dq%st = max(1, dq%memsize / 8)
      dq%ary(dq%st:dq%st + dq%n - 1) = tmp(:)
      deallocate (tmp)
    end if
  end subroutine resize_up

  subroutine may_resize_down(dq)
    ! 必要なら小さい配列に移し替える
    type(dequetype), intent(inout) :: dq
    type(itemtype), allocatable :: tmp(:)
    if (dq%memsize <= MINSIZE) return
    if (mod(dq%memsize, 2) /= 0) stop 1
    if (dq%n * 4 > dq%memsize) return

    allocate (tmp(dq%n))
    tmp(:) = slice(dq, 1, dq%n)
    dq%memsize = dq%memsize / 2
    deallocate (dq%ary)
    allocate (dq%ary(dq%memsize))
    dq%st = max(1, dq%memsize / 8)
    dq%ary(dq%st:dq%st + dq%n - 1) = tmp(:)
    deallocate (tmp)
  end subroutine may_resize_down

  subroutine push_left(dq, x)
    class(dequetype), intent(inout) :: dq
    type(itemtype), intent(in) :: x

    if (dq%n == dq%memsize) call resize_up(dq)
    dq%n = dq%n + 1
    dq%st = imod(dq%st - 1, dq%memsize)
    dq%ary(dq%st) = x
  end subroutine push_left

  subroutine push_right(dq, x)
    class(dequetype), intent(inout) :: dq
    type(itemtype), intent(in) :: x
    integer :: idx

    if (dq%n == dq%memsize) call resize_up(dq)
    dq%n = dq%n + 1
    idx = dq%st + dq%n - 1
    idx = imod(idx, dq%memsize)
    dq%ary(idx) = x
  end subroutine push_right

  type(itemtype) function pop_left(dq)
    class(dequetype), intent(inout) :: dq
    if (dq%n == 0) stop 1
    pop_left = dq%ary(dq%st)
    dq%n = dq%n - 1
    dq%st = imod(dq%st + 1, dq%memsize)
    call may_resize_down(dq)
  end function pop_left

  type(itemtype) function pop_right(dq)
    class(dequetype), intent(inout) :: dq
    if (dq%n == 0) stop 1
    pop_right = dq%ary(imod(dq%st + dq%n - 1, dq%memsize))
    dq%n = dq%n - 1
    call may_resize_down(dq)
  end function pop_right

  function slice(dq, istart, iend)
    ! 実データの [istart:iend] の範囲を切り出す
    class(dequetype), intent(in) :: dq
    type(itemtype), allocatable :: slice(:)
    integer, intent(in) :: istart, iend  ! 実データ内のインデックス
    integer :: dstart, dend
    if (istart < 1) stop 1
    if (iend < istart) stop 1
    if (iend > dq%n) stop 1

    dstart = imod(istart + dq%st - 1, dq%memsize)
    dend = imod(dstart + (iend - istart), dq%memsize)

    allocate (slice(iend - istart + 1))
    if (dend < dstart) then
      slice(1:dq%memsize - dstart + 1) = dq%ary(dstart:dq%memsize)
      slice(dq%memsize - dstart + 2:iend - istart + 1) = dq%ary(1:dend)
    else
      slice(:) = dq%ary(dstart:dend)
    end if
  end function slice

  subroutine dump(dq)
    class(dequetype), intent(in) :: dq
    print *, "Data count:               ", dq%n
    print *, "Physical starting index:  ", dq%st
    print *, "Physical memory allocated:", dq%memsize
    print *, slice(dq, 1, dq%n)
  end subroutine dump

  pure integer function imod(idx, ms)
    ! メモリサイズ ms でインデックスを丸める
    ! [1 - ms <= idx <= ms + ms] を仮定
    integer, intent(in) :: idx, ms
    imod = idx
    if (imod > ms) then
      imod = imod - ms
    else if (imod < 1) then
      imod = imod + ms
    end if
  end function imod
end module m_deque

program main
  use m_deque, only: dequetype, itemtype
  implicit none
  integer :: n, m, u, v, i, j, k, k2, d, s, t, res, x
  logical, allocatable :: queued(:, :)
  type(dequetype), allocatable :: dest(:)
  type(dequetype) :: q
  type(itemtype) :: tri, tri2(1)

  read *, n, m
  allocate (dest(n), queued(0:2, n))
  do i = 1, m
    read *, u, v
    call dest(u) % push_right(itemtype((/v, 0, 0/)))
  end do
  read *, s, t
  queued(:, :) = .false.
  call q % push_right(itemtype((/s, 0, 0/)))
  queued(0, s) = .true.
  res = -1
  do while (q % n > 0)
    tri = q % pop_left()
    i = tri % x(1)
    k = tri % x(2)
    d = tri % x(3)
    if (i == t .and. k == 0) then
      res = d / 3
      exit
    end if
    k2 = modulo((k + 1), 3)
    do x = 1, dest(i) % n
      tri2 = dest(i) % slice(x, x)
      j = tri2(1) % x(1)
      if (queued(k2, j)) cycle
      call q % push_right(itemtype((/j, k2, d + 1/)))
      queued(k2, j) = .true.
    end do
  end do
  print "(i0)", res
end program main
