module mod_t_list
  implicit none
  type :: t_list
    integer :: vol
    integer, pointer :: arr(:)
  end type t_list
  private
  public :: t_list, init_list, push_back, pop_back
  public :: poll_back, get_at, size_of_list
contains
  subroutine init_list(list)
    implicit none
    type(t_list), intent(inout) :: list
    list%vol = 0
    nullify(list%arr)
    allocate(list%arr(1))
    return
  end subroutine init_list
  subroutine push_back(list,n)
    implicit none
    type(t_list), intent(inout) :: list
    integer, intent(in) :: n
    integer, allocatable :: tmp(:)
    if (size(list%arr).eq.list%vol) then
      allocate(tmp(list%vol))
      tmp = list%arr
      deallocate(list%arr)
      allocate(list%arr(2*list%vol))
      list%arr(1:list%vol) = tmp
      deallocate(tmp)
    end if
    list%vol = list%vol+1
    list%arr(list%vol) = n
    return
  end subroutine push_back
  function pop_back(list) result(n)
    implicit none
    type(t_list), intent(inout) :: list
    integer :: n
    n = list%arr(list%vol)
    list%vol = list%vol-1
    return
  end function pop_back
  subroutine poll_back(list)
    implicit none
    type(t_list), intent(inout) :: list
    list%vol = list%vol-1
    return
  end subroutine poll_back
  function get_at(list,i) result(n)
    implicit none
    type(t_list), intent(in) :: list
    integer, intent(in) :: i
    integer :: n
    n = list%arr(i)
    return
  end function get_at
  function size_of_list(list) result(s)
    implicit none
    type(t_list), intent(in) :: list
    integer :: s
    s = list%vol
    return
  end function size_of_list
end module mod_t_list
module mod_t_graph
  use mod_t_list
  implicit none
  integer, allocatable :: color(:)
  type :: t_graph
    type(t_list), pointer :: edges(:)
  end type t_graph
  private
  public :: t_graph, init_graph, add, is_bipartite
contains
  subroutine init_graph(graph,n)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer, intent(in) :: n
    integer :: i
    allocate(color(n))
    color = 0
    allocate(graph%edges(n))
    do i = 1, n
      call init_list(graph%edges(i))
    end do
    return
  end subroutine init_graph
  subroutine add(graph,i,pos)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer, intent(in) :: i, pos
    call push_back(graph%edges(i),pos)
    return
  end subroutine add
  recursive function is_bipartite(graph,v) result(w)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer :: v, i, e, w, s, t
    if (v.lt.0) then
      color(1) = 1
      w = is_bipartite(graph,1)
      return
    end if
    w = -1
    s = 0
    do i = 1, size_of_list(graph%edges(v))
      e = get_at(graph%edges(v),i)
      if (color(e).eq.color(v)) return
      if (color(e).eq.0) then
        color(e) = -color(v)
        t = is_bipartite(graph,e)
        if (t.lt.0) return
        s = s+t
        if (color(v).eq.1) s = s+1
      end if
    end do
    w = s
    return
  end function is_bipartite
end module mod_t_graph
program three_step
  use mod_t_graph
  implicit none
  type(t_graph) :: graph
  integer :: n, m, a, b, w, i
  read(*,*) n, m
  call init_graph(graph,n)
  do i = 1, m
    read(*,*) a, b
    call add(graph,a,b)
    call add(graph,b,a)
  end do
  w = is_bipartite(graph,-1)
  if (w.lt.0) then
    write(*,'(i0)') int(n,8)*int(n-1,8)/2_8-int(m,8)
  else
    write(*,'(i0)') int(w,8)*int(n-w,8)-int(m,8)
  end if
  stop
end program three_step