let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let abs = Array.init m @@ fun _ ->
    Scanf.scanf "%d %d\n" @@ fun a b -> a - 1, b - 1 in
  let succ = Array.make n [] in
  Array.iter (fun (a, b) ->
    succ.(a) <- b :: succ.(a);
    succ.(b) <- a :: succ.(b)) abs;
  let colour = Array.make n None in
  let rec dfs c v =
    match colour.(v) with
    | None -> colour.(v) <- Some c; List.iter (dfs (not c)) succ.(v)
    | Some c' -> if c <> c' then raise Not_found in
  try
    dfs true 0;
    Printf.printf "%d\n" @@
      List.length (List.filter (( = ) (Some true)) (Array.to_list colour)) *
      List.length (List.filter (( = ) (Some false)) (Array.to_list colour)) - m
  with Not_found -> Printf.printf "%d\n" (n * (n - 1) / 2 - m)
