import std.algorithm;
import std.array;
import std.ascii;
import std.bigint;
import std.complex;
import std.container;
import std.conv;
import std.functional;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

auto readInts() {
  return array(map!(to!int)(readln().strip().split()));
}

auto readInt() {
  return readInts()[0];
}

auto readLongs() {
  return array(map!(to!long)(readln().strip().split()));
}

auto readLong() {
  return readLongs()[0];
}

void readlnTo(T...)(ref T t) {
  auto s = readln().split();
  assert(s.length == t.length);
  foreach (ref ti; t) {
    ti = s[0].to!(typeof(ti));
    s = s[1 .. $];
  }
}

class UnionFindTree {
public:
  this(size_t n) {
    parent = iota(n).array();
    rank = new size_t[](n);
  }

  size_t find(size_t n) {
    if (n == parent[n]) {
      return n;
    } else {
      parent[n] = find(parent[n]);
      return parent[n];
    }
  }

  void unite(size_t n, size_t m) {
    auto p1 = find(n);
    auto p2 = find(m);
    if (n == m) {
      return;
    }
    if (rank[p1] < rank[p2]) {
      swap(p1, p2);
    }
    if (rank[p1] == rank[p2]) {
      ++rank[p1];
    }
    parent[p2] = p1;
  }

private:
  size_t[] parent;
  size_t[] rank;
}

unittest {
  auto uft = new UnionFindTree(10);
  foreach (i; iota(10)) {
    assert(uft.find(i) == i);
  }
  foreach (i; iota(10).filter!(a => a % 3 == 0).drop(1)) {
    uft.unite(i, i - 3);
  }
  foreach (i; iota(10).filter!(a => a % 3 == 0)) {
    assert(uft.find(0) == uft.find(i));
  }
  foreach (i; iota(10).filter!(a => a % 3 != 0)) {
    assert(uft.find(0) != uft.find(i));
  }
}

//内部では1-based, 使うときは0-based
class BinaryIndexedTree(T, alias F = "a + b") if (is(typeof(binaryFun!F))) {
  alias f = binaryFun!F;
public:
  this(in size_t n, in T T0 = T.init) {
    t.length = n + 1;
    t[] = T0;
  }

  void add(in size_t idx, in T v)
  in {
    assert(idx < t.length - 1);
  }
  body {
    one_based_add(idx + 1, v);
  }

  T accumulate(size_t idx) {
    return one_based_accumulate(idx + 1);
  }

private:
  T[] t;

  //1-based
  void one_based_add(size_t idx, in ref T v) {
    if (idx >= t.length) {
      return;
    }
    t[idx] = f(t[idx], v);
    one_based_add(idx + (idx & (-idx)), v);
  }

  T one_based_accumulate(size_t idx) {
    if (idx == 0) {
      return t[0];
    } else {
      return f(one_based_accumulate(idx - (idx & (-idx))), t[idx]);
    }
  }
}

unittest {
  auto bit = new BinaryIndexedTree!(long)(10);
  foreach (i; iota(10)) {
    assert(bit.accumulate(i) == 0);
  }
  bit.add(5, 3);
  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 0);
  }
  foreach (i; iota(5, 10)) {
    assert(bit.accumulate(i) == 3);
  }

  bit.add(7, 2);

  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 0);
  }
  foreach (i; iota(5, 7)) {
    assert(bit.accumulate(i) == 3);
  }
  foreach (i; iota(7, 10)) {
    assert(bit.accumulate(i) == 5);
  }
}

unittest {
  auto bit = new BinaryIndexedTree!(long, "a*b")(10, 1);
  foreach (i; iota(10)) {
    assert(bit.accumulate(i) == 1);
  }
  bit.add(5, 3);
  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 1);
  }
  foreach (i; iota(5, 10)) {
    assert(bit.accumulate(i) == 3);
  }

  bit.add(7, 2);

  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 1);
  }
  foreach (i; iota(5, 7)) {
    assert(bit.accumulate(i) == 3);
  }
  foreach (i; iota(7, 10)) {
    assert(bit.accumulate(i) == 6);
  }
}

//最大流、O(|V||E|^2)
template Flow_Dinic() {
  class Edge {
  public:
    this(long to, long capacity) {
      this.to = to;
      this.capacity = capacity;
    }

    long to;
    long capacity;
    Edge reverse;
  }

  //gを残余グラフにする
  void residualise(ref Edge[][] g) {
    foreach (u; iota(g.length)) {
      foreach (e; g[u]) {
        if (e.capacity != 0) {
          e.reverse = new Edge(u, 0);
          e.reverse.reverse = e;
          g[e.to] ~= e.reverse;
        }
      }
    }
  }

  const long INF = long.max / 2;

  //gは残余グラフ
  //gは計算の結果書き換わる
  long solve(Edge[][] g, long s, long t) {
    long ret;
    while (true) {
      auto level = new long[](g.length);
      level[] = INF;
      auto q = DList!long(s);
      level[s] = 0;
      //level graph
      auto lg = new Edge[][](g.length, 0);
      while (!q.empty()) {
        auto u = q.front();
        q.removeFront();
        if (u == t) {
          break;
        }
        foreach (e; g[u]) {
          if (e.capacity > 0 && level[e.to] >= level[u] + 1) {
            level[e.to] = level[u] + 1;
            q.insertBack(e.to);
            lg[u] ~= e;
          }
        }
      }
      if (level[t] == INF) {
        break;
      }
      auto iter = new long[](g.length);
      long dfs(long u, long c_min) {
        if (u == t) {
          return c_min;
        }
        foreach (i; iota(iter[u], lg[u].length)) {
          iter[u] = i;
          long f = dfs(lg[u][i].to, min(c_min, lg[u][i].capacity));
          if (f > 0) {
            lg[u][i].capacity -= f;
            lg[u][i].reverse.capacity += f;
            return f;
          }
        }
        return 0;
      }

      while (true) {
        long f = dfs(s, INF);
        if (f == 0) {
          break;
        }
        ret += f;
      }
    }
    return ret;
  }
}

//Pは素数
struct ModInt(ulong P) if (P < int.max) {
  long num;
  this(long num) {
    this.num = num % P;
  }

  const auto inv() {
    return this ^^ (P - 2);
  }

  const bool opEquals()(auto ref const ModInt m) {
    return this.num == m.num;
  }

  const bool opEquals()(auto ref const long m) {
    return this.num == m;
  }

  const auto opBinary(string op)(ModInt r) {
    static if (op == "+") {
      return ModInt(this.num + r.num);
    } else static if (op == "-") {
      return ModInt(this.num + P - (r.num % P));
    } else static if (op == "*") {
      return ModInt(this.num * r.num);
    } else static if (op == "/") {
      return this * r.inv();
    } else static if (op == "^^") {
      return this ^^ r.num;
    }
  }

  const auto opBinary(string op)(long r) {
    static if (op == "^^") {
      if (r == 0) {
        return ModInt(1);
      }
      return (this * this) ^^ (r / 2) * (r % 2 == 1 ? this : ModInt(1));
    } else {
      return this.opBinary!(op)(ModInt!P(r));
    }
  }

  void opAssign(long r) {
    this.num = r % P;
  }

  void opOpAssign(string op, T)(T r) {
    this = this.opBinary!(op)(r);
  }

  string toString() {
    return this.num.to!string;
  }
}

//P(n)を最大n = N-1までメモ
class PMemo(T) {
  this(long N) {
    t = new T[](N);
    t[0] = 1;
    foreach (i; iota(1, N)) {
      t[i] = t[i - 1] * i;
    }
  }

  T p(long n) {
    return t[n];
  }

  T[] t;
}

//nCkを最大n = N-1までメモ
class CMemo(T) {
  this(long N) {
    p_memo = new PMemo!T(N);
  }

  T c(long n, long k) {
    return p_memo.p(n) / (p_memo.p(n - k) * p_memo.p(k));
  }

  PMemo!T p_memo;
}

// [l, r)を管理するセグツリー
class SegmentTree(T, alias F) if (is(typeof(binaryFun!F))) {
  alias f = binaryFun!F;
public:
  this(size_t l, size_t r, T t) {
    this.l = l;
    this.r = r;
    if (r == l + 1) {
      v = t;
    } else {
      auto m = (l + r) / 2;
      lc = new SegmentTree(l, m, t);
      rc = new SegmentTree(m, r, t);
      v = f(lc.v, rc.v);
    }
  }

  this(size_t n, T t) {
    this(0, n, t);
  }

  void update(size_t l, size_t r, T v) {
    if (this.r <= l || r <= this.l) {
      return;
    }
    if (l <= this.l && this.r <= r) {
      this.v = v;
    } else {
      lc.update(l, r, v);
      rc.update(l, r, v);
      this.v = f(lc.v, rc.v);
    }
  }

  void update(size_t idx, T v) {
    update(idx, idx + 1, v);
  }

  auto read(size_t l, size_t r) {
    assert(this.l <= l && r <= this.r);
    if (l == this.l && this.r == r) {
      return this.v;
    } else {
      if (r <= lc.r) {
        return lc.read(l, r);
      } else if (rc.l <= l) {
        return rc.read(l, r);
      } else {
        return f(lc.read(l, lc.r), rc.read(rc.l, r));
      }
    }
  }

private:
  size_t l, r;
  T v;
  SegmentTree lc, rc;
}

enum real eps = 1e-10;

enum long mod = 1_000_000_000 + 7;

void main() {
  long n, m;
  readlnTo(n, m);

  auto g = new long[][](n, 0);
  foreach (i; iota(m)) {
    long a, b;
    readlnTo(a, b);
    --a;
    --b;
    g[a] ~= b;
    g[b] ~= a;
  }
  auto color = new long[](n);
  bool coloring(long i, long c) {
    color[i] = c;
    foreach (v; g[i]) {
      if (color[v] != 0) {
        if (color[v] == c) {
          return false;
        }
      } else {
        if (!coloring(v, -c)) {
          return false;
        }
      }
    }
    return true;
  }

  if (coloring(0, 1)) {
    writeln(color.count!("a == 1") * color.count!("a == -1") - m);
  } else {
    writeln(n * (n - 1) / 2 - m);
  }
}


Measured memory_bytes: 13308