import sys

sys.setrecursionlimit(100000)

F = sys.stdin

N, M = list(map(int, F.readline().strip("\n").split()))

Edge = [[] for _ in range(N)]

for _ in range(M):

    A, B = list(map(int, F.readline().strip("\n").split()))

    Edge[A-1].append(B-1)

    Edge[B-1].append(A-1)



Color = [0] * N





def dfs(v, c):

    Color[v] = c

    for next in Edge[v]:

        if Color[next] == c: return False

        if Color[next] == 0:

            if not dfs(next, -c): return False

    return True



Bipartite = dfs(0, 1)

if Bipartite:

    black = Color.count(1)

    print((black * (N-black) - M))

else:

    print((N * (N - 1)//2 - M))
import sys

from collections import deque



def solve():

    input = sys.stdin.readline

    N, M = list(map(int, input().split()))

    Edge = [[] for _ in range(N)]

    for _ in range(M):

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

        Edge[a-1].append(b-1)

        Edge[b-1].append(a-1)

    Col = [-1] * N

    q = deque()

    q.append((0, 0))

    bipartite = True

    while q:

        nnode, ncol = q.pop()

        if Col[nnode] == -1:

            Col[nnode] = ncol

            for e in Edge[nnode]: q.append((e, ncol ^ 1))

        else:

            if Col[nnode] != ncol:

                bipartite = False

                break

    

    if bipartite:

        zero, one = 0, 0

        for i, n in enumerate(Col):

            if n == 0: zero += 1

            else: one += 1

        print((zero * one - M))

    else:

        print((N * (N - 1) // 2 - M))

    return 0



if __name__ == "__main__":

    solve()
import sys

sys.setrecursionlimit(100000)
F = sys.stdin
N, M = list(map(int, F.readline().strip("\n").split()))
Edge = [[] for _ in range(N)]
for _ in range(M):
    A, B = list(map(int, F.readline().strip("\n").split()))
    Edge[A - 1].append(B - 1)
    Edge[B - 1].append(A - 1)
Color = [0] * N


def dfs(v, c):
    Color[v] = c
    for next in Edge[v]:
        if Color[next] == c:
            return False
        if Color[next] == 0:
            if not dfs(next, -c):
                return False
    return True


Bipartite = dfs(0, 1)
if Bipartite:
    black = Color.count(1)
    print((black * (N - black) - M))
else:
    print((N * (N - 1) // 2 - M))

import sys
from collections import deque


def solve():
    input = sys.stdin.readline
    N, M = list(map(int, input().split()))
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        a, b = list(map(int, input().split()))
        Edge[a - 1].append(b - 1)
        Edge[b - 1].append(a - 1)
    Col = [-1] * N
    q = deque()
    q.append((0, 0))
    bipartite = True
    while q:
        nnode, ncol = q.pop()
        if Col[nnode] == -1:
            Col[nnode] = ncol
            for e in Edge[nnode]:
                q.append((e, ncol ^ 1))
        else:
            if Col[nnode] != ncol:
                bipartite = False
                break
    if bipartite:
        zero, one = 0, 0
        for i, n in enumerate(Col):
            if n == 0:
                zero += 1
            else:
                one += 1
        print((zero * one - M))
    else:
        print((N * (N - 1) // 2 - M))
    return 0


if __name__ == "__main__":
    solve()

- -sys.setrecursionlimit(100000) -F = sys.stdin -N, M = list(map(int, F.readline().strip("\n").split())) -Edge = [[] for _ in range(N)] -for _ in range(M): -    A, B = list(map(int, F.readline().strip("\n").split())) -    Edge[A - 1].append(B - 1) -    Edge[B - 1].append(A - 1) -Color = [0] * N +from collections import deque -def dfs(v, c): -    Color[v] = c -    for next in Edge[v]: -        if Color[next] == c: -            return False -        if Color[next] == 0: -            if not dfs(next, -c): -                return False -    return True +def solve(): +    input = sys.stdin.readline +    N, M = list(map(int, input().split())) +    Edge = [[] for _ in range(N)] +    for _ in range(M): +        a, b = list(map(int, input().split())) +        Edge[a - 1].append(b - 1) +        Edge[b - 1].append(a - 1) +    Col = [-1] * N +    q = deque() +    q.append((0, 0)) +    bipartite = True +    while q: +        nnode, ncol = q.pop() +        if Col[nnode] == -1: +            Col[nnode] = ncol +            for e in Edge[nnode]: +                q.append((e, ncol ^ 1)) +        else: +            if Col[nnode] != ncol: +                bipartite = False +                break +    if bipartite: +        zero, one = 0, 0 +        for i, n in enumerate(Col): +            if n == 0: +                zero += 1 +            else: +                one += 1 +        print((zero * one - M)) +    else: +        print((N * (N - 1) // 2 - M)) +    return 0 -Bipartite = dfs(0, 1) -if Bipartite: -    black = Color.count(1) -    print((black * (N - black) - M)) -else: -    print((N * (N - 1) // 2 - M)) +if __name__ == "__main__": +    solve()