CodeEff/ECCO huggingface dataset:
# Original solution
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict

N,M = inpl()
edge = defaultdict(lambda: [])
for _ in range(M):
    a, b = inpl()
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

Qu = [0] 
ctr = 1
color = [0 for _ in range(N)]
color[0] = -1
while ctr < N:
    st = Qu.pop()
    for i in edge[st]:
        if color[st] == -color[i]:
            Qu.append(i)
            continue
        if color[i] == 0:
            color[i] = -color[st]
            Qu.append(i)
            ctr += 1
sumc = sum(color)
ans =(N**2-sumc**2)//4-M
for i in range(N):
    for j in edge[i]:
        if color[i] == color[j]:
            ans = N*(N-1)//2-M
            break
    else:
        continue
    break
print(ans)

# Optimized solution
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict

N,M = inpl()
edge = defaultdict(lambda: [])
for _ in range(M):
    a, b = inpl()
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

Qu = [0] 
ctr = 1
color = [0 for _ in range(N)]
color[0] = -1
while ctr < N:
    st = Qu.pop()
    for i in edge[st]:
        if color[st] == -color[i]:
            continue
        if color[i] == 0:
            color[i] = -color[st]
            Qu.append(i)
            ctr += 1
sumc = sum(color)
ans =(N**2-sumc**2)//4-M
for i in range(N):
    for j in edge[i]:
        if color[i] == color[j]:
            ans = N*(N-1)//2-M
            break
    else:
        continue
    break
print(ans)
# Original solution
#https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c
from collections import deque
N,M=list(map(int,input().split()))
G=[[] for i in range(N)]
for i in range(M):
	a,b = list(map(int,input().split()))
	G[a-1].append(b-1)
	G[b-1].append(a-1)
visit=[False]*N
color=[-1]*N
que=deque()

def nibu():
	que.append(0)
	color[0]=True

	while que:
		p=que.pop()
		visit[p]=True
		for q in G[p]:
			if visit[q] and color[q]==color[p]:
				return False
			elif not visit[q]:
				que.append(q)
				color[q]=(color[p]+1)%2
	return True

if nibu():
	B=color.count(0)
	W=color.count(1)
	ans=B*W-M
else:
	ans = (N*(N-1))//2 -M
print(ans)

# Optimized solution
#https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c
from collections import deque
N,M=list(map(int,input().split()))
G=[[] for i in range(N)]
for i in range(M):
	a,b = list(map(int,input().split()))
	G[a-1].append(b-1)
	G[b-1].append(a-1)
visit=[False]*N
color=[-1]*N
que=deque()

def nibu():
	que.append(0)
	color[0]=1

	while que:
		p=que.pop()
		visit[p]=True
		for q in G[p]:
			if visit[q] and color[q]==color[p]:
				return False
			elif not visit[q]:
				que.append(q)
				color[q]=(color[p]+1)%2
	return True

if nibu():
	B=color.count(0)
	W=color.count(1)
	ans=B*W-M
else:
	ans = (N*(N-1))//2 -M
print(ans)
# Original solution
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, (input().split())))
dic = defaultdict(list)
seen = [False] * (n+1)

for _ in range(m):
    a, b = list(map(int, input().split()))
    dic[a].append(b)
    dic[b].append(a)


def dfs(v, todo,  depth):
    if depth == 3:
        if v not in dic[root]:
            global count
            count += 1
            dic[root].append(v)
            dic[v].append(root)
        return

    for new_v in todo:
        if new_v == root:
            continue
        new_todo = []
        new_todo += dic[new_v]
        new_todo.remove(v)
        dfs(new_v, new_todo, depth+1)


count = 0
for i in range(1, n+1):
    root = i
    todo = dic[i]
    dfs(i, todo, 0)

print(count)


# Optimized solution
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = list(map(int, (input().split())))
dic = defaultdict(list)
seen = [-1] * (n+1)

for _ in range(m):
    a, b = list(map(int, input().split()))
    dic[a].append(b)
    dic[b].append(a)


def dfs(v, todo, color):
    if seen[v] == color:  # 同じ色で戻ってくる = 偶サイクル
        return
    elif seen[v] == 1-color:  # 異なる色で戻ってくる = 奇サイクル
        global odd_cycle
        odd_cycle = True
        return

    seen[v] = color
    for new_v in todo:
        new_todo = dic[new_v]
        dfs(new_v, new_todo, 1-color)


odd_cycle = False
dfs(1, dic[1], 0)
if odd_cycle:
    ans = 0.5 * n * (n-1) - m
else:
    black = seen.count(0)
    white = seen.count(1)
    ans = black * white - m

print((int(ans)))
# Original solution
N, M = list(map(int, input().split()))
edges = [[] for _ in range(N)]

for _ in range(M):
    fr, to = list(map(int, input().split()))
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

def isBipartite():
    sign = [-1] * N
    st = [(0, 0)]
    while st:
        now, p = st.pop()
        sign[now] = p

        for to in edges[now]:
            if sign[to] == -1:
                st.append((to, (p + 1) % 2))
                continue
            if sign[to] != (p + 1) % 2:
                return -1

    return sum(sign)

s = isBipartite()

if s == -1:
    print((N * (N - 1) // 2 - M))
else:
    print((s * (N - s) - M))


# Optimized solution
N, M = list(map(int, input().split()))
edges = [[] for _ in range(N)]

for _ in range(M):
    fr, to = list(map(int, input().split()))
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

def isBipartite():
    sign = [-1] * N
    sign[0] = 0
    st = [0]
    while st:
        now = st.pop()
        p = sign[now]

        for to in edges[now]:
            if sign[to] == -1:
                st.append(to)
                sign[to] = (p + 1) % 2
                continue
            if sign[to] != (p + 1) % 2:
                return -1

    return sum(sign)

s = isBipartite()

if s == -1:
    print((N * (N - 1) // 2 - M))
else:
    print((s * (N - s) - M))
# Original solution
import sys
sys.setrecursionlimit(100000)

N,M=[int(a) for a in input().split()]
AB=[[int(a) for a in input().split()] for _ in range(M)]
edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

visited = [False]*N
WH = [None]*N

def dfs(curr, is_white):
    if visited[curr]:
        return WH[curr]^is_white
    WH[curr] = is_white
    visited[curr] = True
    ans = False
    for node in edges[curr]:
        ans |= dfs(node, not is_white)
    return ans

if dfs(0, True):
    print(((N*(N-1))//2 - M))
else:
    nw = sum(WH)
    print((nw*(N-nw)-sum([WH[a-1]^WH[b-1] for a, b in AB])))


# Optimized solution
import sys
sys.setrecursionlimit(100000)

N,M=[int(a) for a in input().split()]
AB=[[int(a) for a in input().split()] for _ in range(M)]
edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

colors = [0]*N
def dfs(curr, c):
    colors[curr] = c
    for node in edges[curr]:
        if colors[node] == colors[curr]:
            return False
        if colors[node]== 0 and not dfs(node, -c):
            return False
    return True

if not dfs(0, 1):
    print(((N*(N-1))//2 - M))
else:
    WH = [c==1 for c in colors]
    nw = sum(WH)
    print((nw*(N-nw)-sum([WH[a-1]^WH[b-1] for a, b in AB])))
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=list(map(int,input().split()))
    E=[[] for _ in range(n)]
    for i in range(m):
        u,v=list(map(int,input().split()))
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    # bipartite check
    col=[-1]*n
    col[0]=0
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv in E[v]:
            if(col[v]==col[nv]): # 二部グラフではない
                print((n*(n-1)//2-m))
                return
            elif(col[nv]!=-1 and col[nv]^col[v]): continue
            col[nv]=1-col[v]
            Q.append(nv)

    depth=[-1]*n
    depth[0]=0
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv in E[v]:
            if(depth[nv]!=-1): continue
            depth[nv]=depth[v]+1
            Q.append(nv)

    odd=sum(1 for i in range(n) if(depth[i]&1))
    even=n-odd
    ans=odd*even-m
    print(ans)
resolve()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=list(map(int,input().split()))
    E=[[] for _ in range(n)]
    for i in range(m):
        u,v=list(map(int,input().split()))
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    # bipartite check
    col=[-1]*n
    col[0]=0
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv in E[v]:
            if(col[v]==col[nv]): # 二部グラフではない -> 全部繋げられる
                print((n*(n-1)//2-m))
                return
            elif(col[nv]!=-1 and col[nv]^col[v]): continue
            col[nv]=1-col[v]
            Q.append(nv)

    # 二部グラフ -> 偶数と奇数とが繋げられる
    even=col.count(0)
    odd=col.count(1)
    print((even*odd-m))
resolve()
# Original solution
def bipartite():
    color = {v: None for v in V}
    stack = [(V[0], 0)]
    parts = {0: set([]), 1: set([])}
    while stack:
        v, c = stack.pop()
        color[v] = c
        parts[c].add(v)
        for u in E[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    return (parts[0], parts[1])
            
N, M = list(map(int, input().split()))
V = list(range(1, N+1))
E = {v: [] for v in V}
for _ in range(M):
    a, b = list(map(int, input().split()))
    E[a].append(b)
    E[b].append(a)
p1, p2 = bipartite()
if p1 is None:
    print((N * (N-1) // 2 - M))
else:
    print((len(p1) * len(p2) - M))

# Optimized solution
def bipartite():
    color = {v: None for v in V}
    stack = [(V[0], 0)]
    parts = {0: [], 1:[]}
    while stack:
        v, c = stack.pop()
        if color[v] is not None: # consistent
            continue
        color[v] = c
        parts[c].append(v)
        for u in E[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    return (parts[0], parts[1])
            
N, M = list(map(int, input().split()))
V = list(range(1, N+1))
E = {v: [] for v in V}
for _ in range(M):
    a, b = list(map(int, input().split()))
    E[a].append(b)
    E[b].append(a)
p1, p2 = bipartite()
if p1 is None:
    print((N * (N-1) // 2 - M))
else:
    print((len(p1) * len(p2) - M))
# Original solution
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
    
n, m = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

ok = False
tag = [-1] * n


def dfs(i=0, c=0):
    global ok, tag
    if tag[i] != -1:
        if tag[i] != c:
            ok = True
        return
    tag[i] = c
    for j in e[i]:
        dfs(j, (c + 1) % 2)


dfs()

if ok:
    print((n * (n - 1) // 2 - m))
else:
    s = sum(tag)
    print((s * (n - s) - m))


# Optimized solution
import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, m = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

ok = False
tag = [-1] * n


def dfs(i=0, c=0, r=-1):
    global ok, tag
    if tag[i] != -1:
        if tag[i] != c:
            ok = True
        return
    tag[i] = c
    for j in e[i]:
        if j == r:
            continue
        dfs(j, (c + 1) % 2, i)


dfs()

if ok:
    print((n * (n - 1) // 2 - m))
else:
    s = sum(tag)
    print((s * (n - s) - m))
# Original solution
import sys
sys.setrecursionlimit(10 ** 7)

N, M = list(map(int, input().split()))
AB = [[int(x) for x in input().split()] for _ in range(M)]
G = [[] for _ in range(N+1)]
for a,b in AB:  
  G[a].append(b)
  G[b].append(a)
color = [None]*(N+1)  
# 二部グラフ判定
def dfs(v, c):
  color[v] = c
  for e in G[v]:
    if color[e] == None:
      color[e] = 1 - color[v]      
      dfs(e, c^1) # c^1 == xor (0+1==True)
dfs(1, 0)      
bl = all(color[a] != color[b] for a, b in AB)      
# ans
if bl:
  # 二部グラフ
  x = sum(color[1:])
  y = N-x
  print((x*y-M))
else:
  # 完全グラフ
  print((N*(N-1)//2-M))

# Optimized solution
import sys
sys.setrecursionlimit(10 ** 7)

N, M = list(map(int, input().split()))
AB = [[int(x) for x in input().split()] for _ in range(M)]
G = [[] for _ in range(N+1)]
for a,b in AB:  
  G[a].append(b)
  G[b].append(a)
color = [None]*(N+1)  
color[1] = 0
q = [1]
# 二部グラフ判定
while q:
  x = q.pop()
  for y in G[x]:
    if color[y] is None:
      color[y] = 1 - color[x]
      q.append(y)
bl = all(color[a] != color[b] for a, b in AB)      
# ans
if bl:
  # 二部グラフ
  x = sum(color[1:])
  y = N-x
  print((x*y-M))
else:
  # 完全グラフ
  print((N*(N-1)//2-M))
# Original solution
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    a,b=MAP()
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)

visited=[False]*N
team=['']*N

def rec(u):
    if visited[u]:
        return True
    visited[u]=True
    for v in nodes[u]:
        if team[u]==team[v]:
            return False
        if team[u]=='a':
            team[v]='b'
        elif team[u]=='b':
            team[v]='a'
        if not rec(v):
            return False
    return True

# 1からnまでの等差数列の和
def get_sum(n):
    return (1+n)*n//2

team[0]='a'
if rec(0):
    C=Counter(team)
    ans=C['a']*C['b']-M
else:
    ans=get_sum(N-1)-M
print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
nodes = tuple([] for i in range(N))
for i in range(M):
    a, b = MAP()
    a -= 1
    b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

# 二部グラフ判定
color = [-1] * N
def rec(u, prev, c):
    if color[u] == -1:
        color[u] = c
    else:
        if color[u] == c:
            return True
        else:
            return False
    for v in nodes[u]:
        if v != prev:
            if not rec(v, u, 1-c):
                return False
    return True

if rec(0, -1, 0):
    a = sum(color)
    b = N - a
    ans = a*b - M
else:
    ans = N*(N-1) // 2 - M
print(ans)
# Original solution
n, m = list(map(int, input().split()))
g = [[] for i in range(n)]

for i in range(m):
    a, b = list(map(int, input().split()))
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

visited = [False] * n
def dfs(i, src, depth=0):
    global ans
    if depth==3:
        if not i in g[src]:
            g[src].append(i)
            g[i].append(src)
            ans+=1
    else:
        for t in g[i]:
            if visited[t]:
                continue
            else:
                visited[t] = True
                dfs(t, src, depth+1)
                visited[t] = False
    return

ans = 0
for i in range(n):
    visited[i] = True
    dfs(i, i, 0)
    visited[i] = False
print(ans)



# Optimized solution
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
g = [[] for i in range(n)]

for i in range(m):
    a, b = list(map(int, input().split()))
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

# 2部グラフかどうかを判定する
# 色の初期化、0:未着色
colors = [0]*n
def dfs(v, color):
    """
    parm v: node
    param color: 1 or -1
    """
    colors[v] = color
    for to in g[v]:
        if colors[to] == color:
            return False
        
        if colors[to] == 0:
            if not dfs(to, -color):
                return False
    return True

def is_bipartite():
    return dfs(0, 1)

if is_bipartite():
    # すべての対抗で辺が張れる
    print((colors.count(-1)*colors.count(1) - m))
else:
    # すべての対抗の辺が張れる
    print(((n*(n-1))//2 - m))
# Original solution
import sys
sys.setrecursionlimit(10 ** 7)

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

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

for a, b in AB:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

colors = [None] * N
# 二部グラフかどうかのチェック
colors[0] = 0
que = [0]
while que:
    x = que.pop()
    for y in graph[x]:
        if colors[y] == None:
            colors[y] = 1 - colors[x]
            que.append(y)

is_bg = all(colors[a-1] != colors[b-1] for a, b in AB)

if is_bg:
    # 二部完全グラフ
    x = sum(colors)
    y = N - x
    answer = x*y - M
else:
    # 完全グラフ
    answer = N*(N-1)//2 - M

print(answer)



# Optimized solution
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N, M = rl()
graph = [[] for _ in range(N+1)] # 0は使わない、直接行ける頂点
for _ in range(M):
    a, b = rl()
    graph[a].append(b)
    graph[b].append(a)

# 二部グラフのチェック、各頂点に0か1の色を塗る、1の頂点に0の色
color = [None] * (N+1) # 0は使わない
color[1] = 0
stack = [1]
bool = True
while stack:
    node = stack.pop()
    for n in graph[node]:
        if color[n] == None:
            color[n] = 1 - color[node]
            stack.append(n)
        elif color[n] == color[node]:
            bool = False
        else:
            continue

if bool:
    # 二部グラフ
    print(((color.count(1) * color.count(0)) - M))
else:
    print((N*(N-1)//2 - M))
#29
# Original solution
import sys
sys.setrecursionlimit(100000)

N,M = list(map(int,input().split()))
adj_list = { i: [] for i in range(1, N+1) }

for i in range(M):
  a,b = list(map(int, input().split()))
  adj_list[a].append(b)
  adj_list[b].append(a)

visited = [False]*(N+1)
colors = [None] * (N)
is_bipartite = True

## improved dfs ###
def dfs(node, c):
  colors[node-1] = c
  visited[node] = True
  for nei in adj_list[node]:
    if colors[nei-1] == c:
      return False
    if not visited[nei] and not dfs(nei, 1-c):
      return False

  return True

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

# Optimized solution
import sys
sys.setrecursionlimit(100000)

N,M = list(map(int,input().split()))
adj = [ [] for _ in range(N) ]
for _ in range(M):
  u,v = list(map(int,input().split()))
  u -= 1
  v -= 1
  adj[u].append(v)
  adj[v].append(u)

color = [None] * N
def dfs(n, c):
  color[n] = c
  for nei in adj[n]:
    if color[nei] is not None:
      if color[nei] == c: 
        return False
    elif not dfs(nei, 1-c):
      return False
    # else:
    #   dfs(nei, 1-c)

  return True

if dfs(0,1):
  print((color.count(1)*color.count(0) - M))
else:
  print((N*(N-1)//2 - M))
# Original solution
from collections import deque
n,m=list(map(int,input().split()))
e=[[] for _ in range(n+1)]
d=[-1]*(n+1)
for i in range(m):
  a,b=list(map(int,input().split()))
  e[a]+=[b]
  e[b]+=[a]
q=deque([(1,0)])
d[1]=0
a,b=0,0
while q:
  now,par=q.popleft()
  for to in e[now]:
    if to==par:continue
    if d[to]==-1:
      d[to]=(d[now]+1)%2
      a+=1
      q.append((to,now))
    elif d[to]!=d[now]%2:b+=1
    else:
      print((n*(n-1)//2-m))
      exit()
p=sum(d)+1
print((p*(n-p)-a-b//2))

# Optimized solution
from collections import deque
n,m=list(map(int,input().split()))
e=[[] for _ in range(n+1)]
d=[-1]*(n+1)
for i in range(m):
  a,b=list(map(int,input().split()))
  e[a]+=[b]
  e[b]+=[a]
q=deque([(1,0)])
d[1]=0
while q:
  now,par=q.popleft()
  for to in e[now]:
    if to==par:continue
    if d[to]==-1:
      d[to]=(d[now]+1)%2
      q.append((to,now))
    elif d[to]==d[now]%2:
      print((n*(n-1)//2-m))
      exit()
p=sum(d)+1
print((p*(n-p)-m))
# Original solution
import sys

sys.setrecursionlimit(1000000)


def dfs(g: {}, v: int, path_list: [], added: {}):
    path_list.append(v)
    for next_v in g[v]:
        # # next_v が探索済だったらスルー
        if next_v in path_list:
            continue
        # 距離３なら追加可能か確認して次へ
        if len(path_list) == 3:
            if path_list[0] not in g[next_v]:
                dic_a = added.setdefault(path_list[0], set())
                dic_a.add(next_v)
                dic_b = added.setdefault(next_v, set())
                dic_b.add(path_list[0])
        # 距離1なら複製して次へ
        elif len(path_list) == 1:
            copied = [v]
            dfs(g, next_v, copied, added)
        # 距離2なら複製して次へ
        elif len(path_list) == 2:
            copied = path_list.copy()
            dfs(g, next_v, copied, added)


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

    g = {}
    for i in range(m):
        a, b = list(map(int, input().split()))
        dic_a = g.setdefault(a-1, set())
        dic_a.add(b-1)
        dic_b = g.setdefault(b-1, set())
        dic_b.add(a-1)
    count = 0
    while True:
        added = {}
        for i in range(n):
            dfs(g, i, [], added)
        added_cnt = 0
        for _set in list(added.values()):
            added_cnt += len(_set)
        if added_cnt == 0:
            break
        count += added_cnt
        for k, v in list(added.items()):
            dic_a = g.setdefault(k, set())
            for v_item in v:
                dic_a.add(v_item)
    print((int(count/2)))



main()


# Optimized solution
import sys

sys.setrecursionlimit(100000000)


def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for next_v in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v]:
                return False
            continue
        seen[next_v] = 1-current_color
        # 再帰的に探索
        if not dfs(g, next_v, seen, 1 - current_color):
            return False
    return True


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

    g = {}
    for i in range(m):
        a, b = list(map(int, input().split()))
        dic_a = g.setdefault(a-1, [])
        dic_a.append(b-1)
        dic_b = g.setdefault(b-1, [])
        dic_b.append(a-1)
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True
    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, 0, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        white = len([x for x in seen if x == 0])
        black = n - white

        print((black*white - m))
    else:
        print((int((n-1)*n / 2) - m))

main()