from collections import deque



n, m = list(map(int, input().split()))



e = [set() for _ in range(n)]

for _ in range(m):

    a, b = list(map(int, input().split()))

    a -= 1

    b -= 1

    e[a].add(b)

    e[b].add(a)



dq = deque()

dq.append(0)



p = [None] * n

p[0] = 0



is_bipartite = True

while dq:

    v = dq.popleft()

    for u in e[v]:

        if p[u] is None:

            p[u] = 1 ^ p[v]

            dq.append(u)

        elif p[u] == p[v]:

            is_bipartite = False

            break

        else:

            # p[u] == p[v] ^ 1

            pass



if is_bipartite:

    # 同じ色の頂点には辺を張らない

    sp = sum(p)

    print((sp * (n - sp) - m))

else:

    # 全ての頂点間に辺を張る

    print((n * (n - 1) // 2 - m))

from collections import deque



n, m = list(map(int, input().split()))



g = [set() for _ in range(n)]

for _ in range(m):

    a, b = (int(x) - 1 for x in input().split())

    g[a].add(b)

    g[b].add(a)



par = [-1] * n





def is_bipartite():

    dq = deque()

    dq.append(0)

    par[0] = 0



    while dq:

        v = dq.popleft()

        for u in g[v]:

            if par[u] != -1:

                if par[u] == (par[v] ^ 1):

                    continue

                else:

                    return False

            else:

                par[u] = (par[v] ^ 1)

                dq.append(u)

    return True





if is_bipartite():

    # print('bipartite', par)

    evens = par.count(0)

    odds = n - evens

    print((odds * evens - m))

else:

    # print('not bipartite', par)

    print((n * (n - 1) // 2 - m))



# 全ての奇数路にパスが張れる

# 1 : 既に張られている

# 3 : 張れる

# >= 5 : 途中に長さ3のパスを張ると長さが2減るので、奇数のまま2ずつ減らして3になる



# 二部グラフでない場合、奇サイクルが存在するので、

# 偶数路だったパスには、奇サイクルを挟んだ奇数路がある

# すべての頂点間にパスが張れる

from collections import deque

n, m = list(map(int, input().split()))
e = [set() for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    e[a].add(b)
    e[b].add(a)
dq = deque()
dq.append(0)
p = [None] * n
p[0] = 0
is_bipartite = True
while dq:
    v = dq.popleft()
    for u in e[v]:
        if p[u] is None:
            p[u] = 1 ^ p[v]
            dq.append(u)
        elif p[u] == p[v]:
            is_bipartite = False
            break
        else:
            # p[u] == p[v] ^ 1
            pass
if is_bipartite:
    # 同じ色の頂点には辺を張らない
    sp = sum(p)
    print((sp * (n - sp) - m))
else:
    # 全ての頂点間に辺を張る
    print((n * (n - 1) // 2 - m))

from collections import deque

n, m = list(map(int, input().split()))
g = [set() for _ in range(n)]
for _ in range(m):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add(b)
    g[b].add(a)
par = [-1] * n


def is_bipartite():
    dq = deque()
    dq.append(0)
    par[0] = 0
    while dq:
        v = dq.popleft()
        for u in g[v]:
            if par[u] != -1:
                if par[u] == (par[v] ^ 1):
                    continue
                else:
                    return False
            else:
                par[u] = par[v] ^ 1
                dq.append(u)
    return True


if is_bipartite():
    # print('bipartite', par)
    evens = par.count(0)
    odds = n - evens
    print((odds * evens - m))
else:
    # print('not bipartite', par)
    print((n * (n - 1) // 2 - m))
# 全ての奇数路にパスが張れる
# 1 : 既に張られている
# 3 : 張れる
# >= 5 : 途中に長さ3のパスを張ると長さが2減るので、奇数のまま2ずつ減らして3になる
# 二部グラフでない場合、奇サイクルが存在するので、
# 偶数路だったパスには、奇サイクルを挟んだ奇数路がある
# すべての頂点間にパスが張れる

-e = [set() for _ in range(n)] +g = [set() for _ in range(n)] -    a, b = list(map(int, input().split())) -    a -= 1 -    b -= 1 -    e[a].add(b) -    e[b].add(a) -dq = deque() -dq.append(0) -p = [None] * n -p[0] = 0 -is_bipartite = True -while dq: -    v = dq.popleft() -    for u in e[v]: -        if p[u] is None: -            p[u] = 1 ^ p[v] -            dq.append(u) -        elif p[u] == p[v]: -            is_bipartite = False -            break -        else: -            # p[u] == p[v] ^ 1 -            pass -if is_bipartite: -    # 同じ色の頂点には辺を張らない -    sp = sum(p) -    print((sp * (n - sp) - m)) +    a, b = (int(x) - 1 for x in input().split()) +    g[a].add(b) +    g[b].add(a) +par = [-1] * n + + +def is_bipartite(): +    dq = deque() +    dq.append(0) +    par[0] = 0 +    while dq: +        v = dq.popleft() +        for u in g[v]: +            if par[u] != -1: +                if par[u] == (par[v] ^ 1): +                    continue +                else: +                    return False +            else: +                par[u] = par[v] ^ 1 +                dq.append(u) +    return True + + +if is_bipartite(): +    # print('bipartite', par) +    evens = par.count(0) +    odds = n - evens +    print((odds * evens - m)) -    # 全ての頂点間に辺を張る +    # print('not bipartite', par) +# 全ての奇数路にパスが張れる +# 1 : 既に張られている +# 3 : 張れる +# >= 5 : 途中に長さ3のパスを張ると長さが2減るので、奇数のまま2ずつ減らして3になる +# 二部グラフでない場合、奇サイクルが存在するので、 +# 偶数路だったパスには、奇サイクルを挟んだ奇数路がある +# すべての頂点間にパスが張れる