module mod_graph
  implicit none
  integer(8), parameter :: inf = 1000000000000000000_8

  type item
    integer :: id = 0                             !番号
    integer(8) :: wt = 0_8                        !距離の合計
 end type item

  type priorityqueue
    integer :: num = 0                            !要素数
    type(item), pointer :: heap(:) => null()      !配列へのポインタの大きさは無指定
  contains
    !final :: finalizei
 end type priorityqueue

  type edge                                       !辺のこと．ここから可変長配列の実装
     integer :: fm = 0, to = 0, cp = 0, rv = 0
     !from,to,cpはff法の辺の容量，rvは逆辺のリスト上のインデックスの情報
    integer(8) :: wt = 0_8                        !重み(距離とか)
 end type edge

  type arraylist                                   !メソッドの実装，辺に番号付け？
    integer :: num = 0
    type(edge), pointer :: arr(:) => null()
  contains
    procedure :: add => adde
    procedure :: bellman_ford => bellman_ford
    !final :: finalizee
 end type arraylist

  type graph                                       !メソッドの実装，辺と番号，使用状況
    type(arraylist), pointer :: egs(:) => null()   !隣接リスト
    logical, pointer :: used(:) => null()          !dfsで使う
  contains                                         !type文の中にcontain文を入れる
    procedure :: add => add                       !typeの外のサブルーチンへのポインタ
    procedure :: dijkstra => dijkstra
    procedure :: ford_fulkerson => ford_fulkerson
    !final :: finalize
 end type graph

  interface graph                          !interfaceは安全に関数を引数として渡す
    module procedure :: newg               !コンストラクタ
  end interface graph

contains

  function newi(id,wt) result(ret)   !idとwtをitem型のretに入れる
    integer, intent(in) :: id
    integer(8), intent(in) :: wt
    type(item) :: ret
    ret%id = id
    ret%wt = wt
  end function newi

  subroutine swapi(a,b)               !item型であるa,bを入れ替える
    type(item), intent(inout) :: a, b
    type(item) :: c
    c = a
    a = b
    b = c
  end subroutine swapi

  subroutine appendi(a)                         !aの配列長をnから2nにする.O(n)かかる
    type(item), pointer, intent(inout) :: a(:)
    integer :: n
    type(item), allocatable :: tmp(:)
    n = size(a)                                 !配列の要素の合計数
    allocate(tmp(n))
    tmp = a
    deallocate(a)
    allocate(a(2*n))
    a(1:n) = tmp
    deallocate(tmp)
  end subroutine appendi

  function lessi(a,b) result(ret)         !bのwtが大きければ真，そうでなければ偽
    type(item), intent(in) :: a, b
    logical :: ret
    ret = a%wt < b%wt
  end function lessi

  subroutine finalizei(pq)               !pqのリセット
    type(priorityqueue), intent(inout) :: pq
    if (associated(pq%heap)) deallocate(pq%heap)
    pq%num = 0
  end subroutine finalizei

  subroutine offer(pq,it)                !item型であるitをpqに追加する
    type(priorityqueue), intent(inout) :: pq
    type(item), intent(in) :: it
    integer :: i, j
    if (.not.associated(pq%heap)) allocate(pq%heap(1)) !参照先がなければ1番目参照
    if (pq%num == size(pq%heap)) call appendi(pq%heap) !配列長をnから2nに
    pq%num = pq%num+1
    pq%heap(pq%num) = it                 !新たな数値は最後尾に
    i = pq%num
    do while (i > 1)   !逆転がなくなるまで上にあげていく(小さいほうが上)
      j = i/2
      if (lessi(pq%heap(i),pq%heap(j))) call swapi(pq%heap(i),pq%heap(j))
      i = j
    end do
  end subroutine offer

  function poll(pq) result(ret)   !一番上のitem型を取り出す(pqから削除する)
    type(priorityqueue), intent(inout) :: pq
    type(item) :: ret
    integer :: n, i, j
    n = pq%num
    ret = pq%heap(1)
    pq%heap(1) = pq%heap(n)
    pq%num = pq%num-1
    i = 1
    do while (2*i < n)   !最後尾のものを一番上に上げたので，逆転がなくなるまで下ろす
      j = 2*i
      if (j+1 < n .and. lessi(pq%heap(j+1),pq%heap(j))) j = j+1
      if (lessi(pq%heap(j),pq%heap(i))) call swapi(pq%heap(j),pq%heap(i))
      i = j
    end do
  end function poll

  function newe(to,wt,fm,cp,rv) result(ret)   !新しいedgeの生成
    integer, intent(in) :: to
    integer(8), intent(in) :: wt
    integer, intent(in), optional :: fm, cp, rv
    !省略可能な因数の利用(fmはbf法，cp,rvはff法で使用)
    type(edge) :: ret
    if (present(fm)) ret%fm = fm
    ret%to = to
    ret%wt = wt
    if (present(cp) .and. present(rv)) then
      ret%cp = cp
      ret%rv = rv
    end if
  end function newe

  subroutine appende(a)                        !配列長をnから2nに
    type(edge), pointer, intent(inout) :: a(:)
    integer :: n
    type(edge), allocatable :: tmp(:)
    n = size(a)
    allocate(tmp(n))
    tmp = a
    deallocate(a)
    allocate(a(2*n))
    a(1:n) = tmp
    deallocate(tmp)
  end subroutine appende

  function lesse(a,b) result(ret)              !bのwtが大きければ真
    type(edge), intent(in) :: a, b
    logical :: ret
    ret = a%wt < b%wt
  end function lesse

  subroutine finalizee(list)                   !リセット
    type(arraylist), intent(inout) :: list
    if (associated(list%arr)) deallocate(list%arr)
    list%num = 0
  end subroutine finalizee

  subroutine adde(list,e)   !メソッドの処理を書くとき，引数はclass文で宣言.edgeをlistに追加
    class(arraylist), intent(inout) :: list
    type(edge), intent(in) :: e
    if (.not.associated(list%arr)) allocate(list%arr(1))
    if (list%num == size(list%arr)) call appende(list%arr)
    list%num = list%num+1
    list%arr(list%num) = e   !最後尾に追加
  end subroutine adde

  function newg(n) result(ret)   !n番目のgraph型の枠をつくる
    integer, intent(in) :: n
    type(graph) :: ret
    allocate(ret%egs(n))
  end function newg

  subroutine add(g,fm,to,wt,cp)   !graph型にデータを追加
    class(graph), intent(inout) :: g
    integer, intent(in) :: fm, to
    integer, intent(in), optional :: cp
    integer(8) :: wt
    if (present(cp)) then
      call adde(g%egs(fm),newe(to,wt,cp=cp,rv=g%egs(to)%num))
      call adde(g%egs(to),newe(fm,wt,cp=0,rv=g%egs(fm)%num-1))
    else
      call adde(g%egs(fm),newe(to,wt))
    end if
  end subroutine add

  subroutine finalize(g)      !リセット
    type(graph), intent(inout) :: g
    integer :: i
    if (associated(g%used)) deallocate(g%used)
    if (.not.associated(g%egs)) return
    do i = 1, size(g%egs)
      call finalizee(g%egs(i))
    end do
    deallocate(g%egs)
  end subroutine finalize

  function dijkstra(g,s) result(ret)   !ダイクストラ法ABC168D，sはstart
    class(graph), intent(in) :: g
    integer, intent(in) :: s
    integer(8) :: ret(size(g%egs))     !graph中のlistの数だけ配列をつくる．最短距離を格納
    type(priorityqueue) :: pq
    type(item) :: it
    type(edge) :: e
    integer :: i
    ret = inf
    ret(s) = 0_8
    call offer(pq,newi(s,ret(s)))   !pqにstartの番号とret(s)=0からなるitem型を追加
    do while (pq%num > 0)           !すべて吐き出す
      it = poll(pq)                 !一番上のものを取り出す．次に使う頂点
      if (it%wt > ret(it%id)) cycle
      do i = 1, g%egs(it%id)%num
        e = g%egs(it%id)%arr(i)     !取り出したitemのid番目のlistをeとする
        if (ret(e%to) > ret(it%id)+e%wt) then   !今いる場所からの方が近い
          ret(e%to) = ret(it%id)+e%wt   !最短経路の更新
          call offer(pq,newi(e%to,ret(e%to)))
        end if
      end do
    end do
    call finalizei(pq)
  end function dijkstra

  recursive subroutine dfs_bf(g,u)
    type(graph), intent(inout) :: g
    integer, intent(in) :: u
    integer :: i, v
    g%used(u) = .true.
    do i = 1, g%egs(u)%num
      v = g%egs(u)%arr(i)%to
      if (g%used(v)) cycle
      call dfs_bf(g,v)
    end do
  end subroutine dfs_bf

  function bellman_ford(es,s,t) result(ret)   !sはスタート，tはゴール
    class(arraylist), intent(in) :: es
    integer, intent(in) :: s, t
    integer(8) :: ret
    integer :: n, i, fm, to, step
    integer(8) :: wt
    logical :: updated
    integer(8), allocatable :: tmp(:)
    type(graph) :: gs, gt
    type(arraylist) :: reach
    n = 0
    do i = 1, es%num
      n = max(n,es%arr(i)%fm,es%arr(i)%to)
    end do
    gs = newg(n)
    gt = newg(n)
    allocate(gs%used(n),gt%used(n))
    gs%used = .false.
    gt%used = .false.
    do i = 1, es%num
      fm = es%arr(i)%fm
      to = es%arr(i)%to
      wt = es%arr(i)%wt
      call add(gs,fm,to,wt)
      call add(gt,to,fm,wt)
    end do
    call dfs_bf(gs,s)
    call dfs_bf(gt,t)
    n = 0
    do i = 1, es%num
      fm = es%arr(i)%fm
      to = es%arr(i)%to
      if (gs%used(fm) .and. gt%used(fm) .and. gs%used(to) .and. gt%used(to)) then
        call adde(reach,es%arr(i))
        n = max(n,fm,to)
      end if
    end do
    call finalize(gs)
    call finalize(gt)
    allocate(tmp(n))
    tmp = inf
    tmp(s) = 0_8
    step = 0
    updated = .true.
    ret = inf
    do while (updated)
      updated = .false.
      do i = 1, reach%num
        fm = reach%arr(i)%fm
        to = reach%arr(i)%to
        wt = reach%arr(i)%wt
        if (tmp(to) > tmp(fm)+wt) then
          tmp(to) = tmp(fm)+wt
          updated = .true.
        end if
      end do
      step = step+1
      if (step > n) then
        ret = -inf
        exit
      end if
    end do
    if (ret == inf) ret = tmp(t)
    deallocate(tmp)
    call finalizee(reach)
  end function bellman_ford

  recursive function dfs_ff(g,u,t,f) result(ret)
    class(graph), intent(inout) :: g
    integer, intent(in) :: u, t, f          !uはスタート,tはゴール？
    integer :: ret
    integer :: i, v, cp, rv
    ret = f
    if (u == t) return
    g%used(u) = .true.
    do i = 1, g%egs(u)%num
      v = g%egs(u)%arr(i)%to
      cp = g%egs(u)%arr(i)%cp
      if (g%used(v) .or. cp <= 0) cycle
      ret = dfs_ff(g,v,t,min(f,cp))
      rv = g%egs(u)%arr(i)%rv
      if (ret > 0) then
        g%egs(u)%arr(i)%cp = g%egs(u)%arr(i)%cp-ret
        g%egs(v)%arr(rv)%cp = g%egs(v)%arr(rv)%cp+ret
        return
      end if
    end do
    ret = 0
  end function dfs_ff

  function ford_fulkerson(g,s,t) result(ret)   !最大流，最小カットを求める
    class(graph), intent(inout) :: g
    integer, intent(in) :: s, t                !スタート，ゴール
    integer :: ret
    integer :: f
    ret = 0
    if (associated(g%used) .and. size(g%used) /= size(g%egs)) deallocate(g%used)
    if (.not.associated(g%used)) allocate(g%used(size(g%egs)))
    do
      g%used = .false.
      f = dfs_ff(g,s,t,1000000000)
      if (f == 0) then
        deallocate(g%used)
        return
      end if
      ret = ret+f
    end do
  end function ford_fulkerson

end module mod_graph

program ABC168_D
  use mod_graph
  integer::N,M,A,B
  integer,allocatable::ans(:)
  type(graph)::g
  read(*,*)N,M
  allocate(ans(N))
  ans=0
  g=graph(N)
  do i=1,M
     read(*,*)A,B
     call g%add(A,B,1_8)
     call g%add(B,A,1_8)
  end do
  ans=g%dijkstra(1)
  if(any(ans==inf)) then
     write(*,*)'No'
  else
     write(*,*)'Yes'
     do i=2,N
        do j=1,g%egs(i)%num
           k=g%egs(i)%arr(j)%to
           if(ans(k)==ans(i)-1_8) then
              write(*,*)k
              exit
           end if
        end do
     end do
  end if
end program ABC168_D

Measured memory_bytes: 28396