Problem:
 Score : 500 points    Problem Statement Rng has a connected undirected graph with N vertices.
Currently, there are M edges in the graph, and the i -th edge connects Vertices A_i and B_i .  Rng will add new edges to the graph by repeating the following operation:   Operation: Choose u and v  (u \neq v) such that Vertex v can be reached by traversing exactly three edges from Vertex u , and add an edge connecting Vertices u and v . It is not allowed to add an edge if there is already an edge connecting Vertices u and v .   Find the maximum possible number of edges that can be added.      Constraints  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq A_i,B_i \leq N  The graph has no self-loops or multiple edges.  The graph is connected.         Input Input is given from Standard Input in the following format:  N  M  A_1  B_1  A_2  B_2  :  A_M  B_M       Output Find the maximum possible number of edges that can be added.        Sample Input 1 6 5
1 2
2 3
3 4
4 5
5 6      Sample Output 1 4  If we add edges as shown below, four edges can be added, and no more.        Sample Input 2 5 5
1 2
2 3
3 1
5 4
5 1      Sample Output 2 5  Five edges can be added, for example, as follows:   Add an edge connecting Vertex 5 and Vertex 3 .  Add an edge connecting Vertex 5 and Vertex 2 .  Add an edge connecting Vertex 4 and Vertex 1 .  Add an edge connecting Vertex 4 and Vertex 2 .  Add an edge connecting Vertex 4 and Vertex 3 .

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)


colors = [0] * n
def dfs(v, color):
    colors[v] = color
    for to in edges[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and (not dfs(to, -color)):
            return False

    return True

if dfs(0, 1):
    x = colors.count(1)
    print(x * (n - x) - m)

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

Solution (Python):
"""
奇数本の辺で成り立つ閉路があれば、全ての頂点同士を1本の辺で結ぶことができる。
そうでない場合は、奇数本の辺をたどってたどり着ける頂点同士は全て1本の辺で結ぶことができる。
奇数本の閉路があるかどうかを、どうやって判定するか？
二部グラフ判定を行う。
二部グラフ判定ってどうやるんだっけ？→となりのノードに違う色をつけていって、矛盾がなければ二部グラフ。矛盾があれば二部グラフじゃない。
"""
import sys
sys.setrecursionlimit(200000)
N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

n = len(edges)
colors = [-1]*(n+1)
def judgeBiGragh(edges):
    def paint(v,c):
        if colors[v] == -1:
            colors[v] = c
            nxC = (c+1)%2
            for nxV in edges[v]:
                result = paint(nxV,nxC)
                if result == False:
                    return result
        else:
            if colors[v] != c:
                return False
        return True
    return paint(1,0)

def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
if judgeBiGragh(edges):
    cnt0 = colors.count(0)
    cnt1 = colors.count(1)
    ans = cnt0*cnt1 - M
else:
    ans = choose(N,2)-M

print(ans)

Solution (Python):
from networkx import*
n,*t=map(str.split,open(0))
n,m=map(int,n)
try:a,b=map(len,bipartite.sets(Graph(t)));a*=b
except:a=n*~-n//2
print(a-m)

Solution (Python):
from networkx import*
n,*t=map(str.split,open(0))
n,m=map(int,n)
g=Graph(t)
try:a,b=map(len,bipartite.sets(g));a*=b
except:a=n*~-n//2
print(a-m)

Solution (Python):
from networkx import*
n,*t=map(str.split,open(0))
n,m=map(int,n)
g=Graph()
g.add_edges_from(t)
try:a,b=map(len,bipartite.sets(g));a*=b
except:a=n*~-n//2
print(a-m)

Solution (Python):
from networkx import*
n,*t=[t.split()for t in open(0)]
n,m=map(int,n)
g=Graph()
g.add_edges_from(t)
try:a,b=map(len,bipartite.sets(g));a*=b
except:a=n*~-n//2
print(a-m)

Solution (Python):
from networkx import*
(n,m),*t=[[*map(int,t.split())]for t in open(0)]
g=Graph()
g.add_edges_from(t)
try:a,b=map(len,bipartite.sets(g));a*=b
except:a=n*~-n//2
print(a-m)

Solution (Python):
from networkx import*
(n,m),*t=[[*map(int,t.split())]for t in open(0)]
g=Graph()
g.add_edges_from(t)
try:a,b=map(len,algorithms.bipartite.sets(g));a*=b
except:a=n*~-n//2
print(a-m)

Solution (Python):
(n,m),*t=[map(int,t.split())for t in open(0)]
*e,=eval('[],'*-~n)
for a,b in t:e[a]+=b,;e[b]+=a,
q=[g:=1]
f=q*2+[-1]*n
for v in q:
 for w in e[v]:
  if~f[w]:g&=f[v]^f[w]
  else:f[w]=f[v]^1;q+=w,
r=sum(f)
print((n*~-n//2,r*(n-r))[g]-m)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ns[a].append(b)
    ns[b].append(a)
    
def is_bip(ns):
    start = 0
    q = [start]
    cs = [None]*n
    cs[start] = 1
    while q:
        u = q.pop()
        c = cs[u]
        cc = int(not c)
        for v in ns[u]:
            if cs[v] is None:
                cs[v] = cc
                q.append(v)
            elif cs[v]==c:
                return False, None
    return True, cs

res, cs = is_bip(ns)
if res:
    n1 = sum(cs)
    n2 = n - n1
    ans = n1*n2 - m
else:
    ans = n*(n-1)//2 - m
print(ans)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

Q = deque()
Q.append(0)
C = [-1] * N
C[0] = 0

B = True
while len(Q) > 0:
    q = Q.popleft()
    pc = C[q]
    for g in G[q]:
        if C[g] == -1:
            C[g] = 1 - pc
            Q.append(g)
            continue
        if C[g] == pc:
            B = False

if not B:
    print((N * (N - 1) // 2) - M)
else:
    W = C.count(0)
    B = C.count(1)
    print(W * B - M)

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.buffer.readline
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    mod = 10**9 + 7
    n, m = nm()
    G = [list() for _ in range(n)]
    for _ in range(m):
        u, v = nm()
        u -= 1; v -= 1
        G[u].append(v)
        G[v].append(u)
    col = [-1]*n
    q = deque([0])
    col[0] = 1
    while q:
        v = q.popleft()
        for x in G[v]:
            if col[x] < 0:
                col[x] = col[v] ^ 1
                q.append(x)
            elif col[x] == col[v]:
                print(n * (n-1) // 2 - m)
                return
    bl = sum(col)
    wh = n - bl
    print(bl * wh - m)
    return

solve()

Solution (Python):

class Tree(object):
    def __init__(self, N):
        self.tree   = [[] for _ in range(N)]
        self.colors = [0  for _ in range(N)]

    def add_node(self, a, b):
        self.tree[a].append(b)
    
    def is_bipartite_graph(self, v, color):
        self.colors[v] = color
        for to in self.tree[v]:
            if self.colors[to] == color:
                return False
            if self.colors[to] == 0 and not self.is_bipartite_graph(to, -color):
                return False
        return True
    
    def count_node(self, color):
        return self.colors.count(color)
    
if __name__ == "__main__":

    import sys
    sys.setrecursionlimit(200000)
    
    N, M = map(int, input().split())
    tree = Tree(N)
    for _ in range(M):
        a, b = map(int, input().split())
        tree.add_node(a-1, b-1)
        tree.add_node(b-1, a-1)
    
    
    is_bpr = tree.is_bipartite_graph(0, 1)
    if is_bpr:
        bla = tree.count_node(1)
        whi = N - bla
        print(bla*whi-M)
    else:
        print(int(N*(N-1)/2-M))

Solution (Python):
import sys
sys.setrecursionlimit(100000)

N,M = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(M):
  u,v = 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
    
    

  return True

if dfs(0,1):
  print(color.count(1)*color.count(0) - M)
else:
  print(N*(N-1)//2 - M)

Solution (Python):
n,m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    a,b = list(map(int,input().split()))
    link[a-1].append(b-1)
    link[b-1].append(a-1)

def isbi():
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]
    visited = set()
    cnt = 0
    while q:
        now, c = q.pop()
        if now in visited:
            if colors[now] != c:
                return False
            continue
        visited.add(now)
        colors[now] = c
        cnt += c
        for nxt in link[now]:
            q.append((nxt, c ^ 1))
    return cnt

ret = isbi()
if not ret:
    ans = n*(n-1)//2 - m
else:
    ans=ret*(n-ret) - m
print(ans)

Solution (Python):
n,m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    a,b = list(map(int,input().split()))
    link[a-1].append(b-1)
    link[b-1].append(a-1)

from collections import defaultdict
from collections import deque
visited = [0] * n

Q = deque()
Q.append([0,1]) 
while Q:
    now,color = Q.popleft()
    if color==1:
        nxt_c = 2
    else:
        nxt_c = 1

    for nxt in link[now]:
        if visited[nxt] == nxt_c:
            continue
        if visited[nxt] != 0 and visited[nxt] !=nxt_c:
            ans = n*(n-1)//2 - m
            print(ans)
            exit()
        visited[nxt] = nxt_c
        Q.append([nxt,nxt_c])

b_cnt=0
w_cnt=0
for c in visited:
    if c==1:
        b_cnt+=1
    else:
        w_cnt+=1

print(b_cnt*w_cnt - m)

Solution (Python):



import queue
from collections import Counter
N,M = map(int,input().split())
ans = [-1]*N
pas = [[] for _ in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    pas[u-1].append(v-1)
    pas[v-1].append(u-1)

q = queue.Queue()
q.put(0)
ans[0] = 0
flag = True
while (not q.empty()):
    now = q.get()
    nowa = ans[now]
    for i in pas[now]:
        if ans[i] == -1:
            if nowa == 0:
                ans[i] = 1
            else:
                ans[i] = 0
            q.put(i)
        else:
            if ans[i] == nowa:
                flag = False

if flag:
    c = Counter(ans)
    zer = c[0]
    one = c[1]
    print(zer*one-M)
else:
    print(N*(N-1)//2-M)

Solution (Python):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)

cl = [-1] * (N+1)
cl[1] = 0
is_bipartite = True
stack = [1]
while stack:
    v = stack.pop()
    for c in G[v]:
        if cl[c] != -1 and cl[c] == cl[v]:
            is_bipartite = False
            break
        if cl[c] == -1:
            cl[c] = 1 - cl[v]
            stack.append(c)
    if not is_bipartite:
        break
if is_bipartite:
    print(cl.count(0) * cl.count(1) - M)
else:
    print(N * (N - 1) // 2 - M)

Solution (Python):
import sys
sys.setrecursionlimit(100000)

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

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

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


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)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    edge = [ZZ() for _ in range(M)]
    E = defaultdict(list)
    for a, b in edge:
        E[a].append(b)
        E[b].append(a)

    color = [0] * (N+1)

    def is_bi(v, c):
        color[v] = c
        for to in E[v]:
            if color[to] == c: return False
            if color[to] == 0 and not is_bi(to, -c): return False
        return True

    if is_bi(1, 1):
        x = color.count(1)
        output = x * (N - x) - M
    else: output = N * (N - 1) // 2 - M
    print(output)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

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

C = [-1]*n
def is_bipartite(v, color):
  C[v] = color
  for nv in G[v]:
    if C[nv] != -1 and color == C[nv]:
      return False
    if C[nv] == -1:
      if not is_bipartite(nv, color ^ 1):
        return False
  return True

if is_bipartite(0, 0):
  b = C.count(0)
  w = n - b
  ans = b*w - m
else:
  ans = n*(n-1)//2 - m
print(ans)

Solution (Python):
N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  graph[a-1].append(b-1); graph[b-1].append(a-1)

dist = [2] * N
dist[0] = 0
d = [[0, -1]]
num = {0:1, 1:0}
while d:
  node, par = d.pop()
  children = graph[node]
  for child in children:
    if child == par:
      continue
    if dist[child] < 2:
      if dist[child] == (dist[node] + 1) % 2:
        continue
      print(N*(N-1)//2 - M)
      quit()
    else:
      dist[child] = (dist[node] + 1) % 2
      num[dist[child]] += 1
      d.append([child, node])

print(num[0] * num[1] - M)

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


class Vertex:
    def __init__(self, value):
        self.edge = []
        self.value = value


visited = []
flg = True      
def dfs(G, v, pv, col):
    global flg

    visited[v] = True
    G[v].value = col

    for nv in G[v].edge:
        if visited[nv]:
            if nv != pv and G[nv].value == G[v].value:
                flg = False
            continue
        dfs(G, nv, v, (col + 1) % 2)


def main():
    N, M = map(int, input().split())
    G = [Vertex(0) for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        G[a].edge.append(b)
        G[b].edge.append(a)
    
    for _ in range(N):
        visited.append(False)
    dfs(G, 0, -1, 0)

    if flg:
        bw = [0, 0]     
        for i in range(N):
            bw[G[i].value] += 1
        print(bw[0] * bw[1] - M)
    else:
        print(N*(N-1) // 2 - M)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10**9)

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


adj = [[] for j in range(N)]
for edge in edges:
    x, y = edge
    adj[x-1].append(y)
    adj[y-1].append(x)

color = [0] * N


def dfs(node, c):
    color[node-1] = c
    for i in adj[node-1]:
        if c == color[i-1]:
            return False
        if color[i-1] == 0 and not dfs(i, -c):
            return False
    return True

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

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

michi = [[] for i in range(N)]
for i in range(M):
  tempa, tempb = map(int,input().split())
  michi[tempa-1].append(tempb-1)
  michi[tempb-1].append(tempa-1)

  
colors = [0 for i in range(N)]

def dfs(v,color):
  colors[v] = color
  for to in michi[v]:
    if colors[to] == color:
      return False
    if colors[to] == 0 and not dfs(to,-color):
      return False
  return True

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

Solution (Python):
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N)]
        
        self._size = [1] * N
        self._even = [i%2 for i in range(0,N)]
        self._odd =[(i+1)%2 for i in range(0,N)]

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) 
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
            self._even[gy] += self._even[gx]
            self._odd[gy] += self._odd[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]
            self._even[gx] += self._even[gy]
            self._odd[gx] += self._odd[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

    def calc_comb(self):
        N=len(self._parent)
        ans=0
        for i in range(N):
            if self.find_root(i) ==i:
                ans+=self._even[i]*self._odd[i]
        return ans


import sys

input=sys.stdin.readline

N,M=map(int,input().split())
uf=UnionFindVerSize(2*N)
for i in range(M):
    a,b=map(int,input().split())
    uf.unite(2*a-2,2*b-1)
    uf.unite(2*b-2,2*a-1)

ans=uf.calc_comb()
for i in range(N):
    if uf.is_same_group(2*i,2*i+1):
        ans-=1

ans//=2
print(ans-M)

Solution (Python):
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N)]
        
        self._size = [1] * N
        self._even = [i%2 for i in range(0,N)]
        self._odd =[(i+1)%2 for i in range(0,N)]

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) 
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
            self._even[gy] += self._even[gx]
            self._odd[gy] += self._odd[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]
            self._even[gx] += self._even[gy]
            self._odd[gx] += self._odd[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

    def calc_comb(self):
        N=len(self._parent)
        ans=0
        for i in range(N):
            if self.find_root(i) ==i:
                ans+=self._even[i]*self._odd[i]
        return ans


import sys

N,M=map(int,input().split())
uf=UnionFindVerSize(2*N)
for i in range(M):
    a,b=map(int,input().split())
    uf.unite(2*a-2,2*b-1)
    uf.unite(2*b-2,2*a-1)

ans=uf.calc_comb()
for i in range(N):
    if uf.is_same_group(2*i,2*i+1):
        ans-=1

ans//=2
print(ans-M)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
WHITE = 1
BLACK = 0
UNCON = -1

def dfs(v,c):
	color[v] = c

	for n in edge[v]:

		if(color[n] != UNCON):
			if(color[n] == c):
				return False
			continue
		if(dfs(n,1-c) == False):
			 return False
	return True

n,m = map(int, input().split())
edge=[[] for i in range(n+1)]
color=[UNCON for i in range(n+1)]
for i in range(m):
	a,b = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)


is_bip = True
for v in range(1,n+1):
	if(color[v] != -1):
		continue
	if(dfs(1,1)==False):
		is_bip = False

if(is_bip):
	wnum = 0
	bnum = 0

	for v in range(1,n+1):
		if(color[v] == WHITE):
			wnum += 1
		else:
			bnum += 1
	print(wnum*bnum-m)
else:
	print(int(n*(n-1)/2)-m)

Solution (Python):
"""
グラフが二部グラフかどうかを判定する。
二部グラフであれば、AグループのノードとBグループのノード同士をそれぞれ結ぶことができる。
二部グラフでない場合、すべてのノード同士を結ぶことができる。
"""
import math
from collections import Counter
import sys
sys.setrecursionlimit(200000)
def choose(n):
    return math.factorial(n)//(math.factorial(n-2)*math.factorial(2))
N,M = map(int,input().split())
edges = [[]for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,input().split())
    edges[A].append(B)
    edges[B].append(A)

colors = [-1]*(N+1)
def f(n,p):
    c = colors[n]
    for v in edges[n]:
        if v != p:
            if colors[v] == -1:
                colors[v] = 1 if c==0 else 0
                f(v,n)
            elif colors[v] == c:
                print(choose(N)-M)
                exit()
colors[1]=0
f(1,0)
count1 = colors.count(0)
count2 = colors.count(1)
print(count1*count2-M)

Solution (Python):
import sys

sys.setrecursionlimit(100000000)


def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for next_v in g[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 = map(int, input().split())

    g = {}
    for i in range(m):
        a, b = 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)
    
    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()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
s=[[]for i in range(n+1)]
c=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
def dfs(v,t):
    c[v]=t
    
    for i in s[v]:
        if c[i]==t:
            return False
        if c[i]==0 and not dfs(i,-t):
            return False
    else:
        return True
if dfs(1,1):
    q=c.count(1)
    print((n-q)*q-m)
else:
    print((n*(n-1)//2)-m)

Solution (Python):
n,m=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
import sys
sys.setrecursionlimit(10**6)
dep=[-1 for i in range(n+1)]
color=[0 for i in range(n+1)]
def dfs(s,d,c):
    dep[s]=d
    color[s]=c
    for i in edge[s]:
        if dep[i]==-1:
            if not dfs(i,d+1,-c):
                return False
        else:
            if color[i]==c:
                return False
    return True
if dfs(1,0,1):
    print(color.count(1)*color.count(-1)-m)
else:
    print(n*(n-1)//2-m)

Solution (Python):
n,m=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
import sys
sys.setrecursionlimit(10**6)
dep=[-1 for i in range(n+1)]
color=[0 for i in range(n+1)]
def dfs(s,d,c):
    dep[s]=d
    color[s]=c
    for i in edge[s]:
        if dep[i]==-1:
            if not dfs(i,d+1,-c):
                return False
        else:
            if color[i]==c:
                return False
    return True
if dfs(1,0,1):
    print(color.count(1)*color.count(-1)-m)
else:
    print(n*(n-1)//2-m)

Solution (Python):
n,m = map(int,input().split())
edg = [[] for i in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  edg[a].append(b)
  edg[b].append(a)
  
check1 = [0] * n
check0 = [0] * n

from collections import deque

q = deque()
q.append((0,1))
check0[0] = 1

while q:
  p,t = q.pop()
  for e in edg[p]:
    if t:
      if check1[e]:continue
      check1[e] = 1
      q.appendleft((e,0))
    else:
      if check0[e]:continue
      check0[e] = 1
      q.appendleft((e,1))
ans = 0
sc0 = sum(check0)
sc1 = sum(check1)
for i in range(n):
  if check0[i]:
    if check1[i]:
      ans += n - 1
    else:
      ans += sc1
  else:
      ans += sc0
print(ans//2 - m)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

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

def dfs(u, c):
    color[u] = c
    for v in graph[u]:
        if color[v] == c:
            return False
        if color[v] == 0 and not dfs(v, -c):
            return False
        
    return True

graph = [[] for _ in range(N)]
for a, b in X:
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

color = [0] * N
if dfs(0, 1):
    c = sum(v == 1 for v in color)
    print(c * (N - c) - M)
else:
    print(N * (N - 1) // 2 - M)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

seen = [-1] * (N + 1)
seen[1] = 1
node = [1]
while node:
    s = node.pop()
    x = seen[s]
    for t in edge[s]:
        if seen[t] == -1:
            seen[t] = 1 ^ x
            node.append(t)
        elif seen[t] == 1 ^ x:
            continue
        else:
            ans = N * (N - 1) // 2 - M
            print(ans)
            exit()

X = seen.count(1)
ans = 0
for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    ans += X - len(edge[i])
print(ans)

Solution (Python):
n,m = map(int,input().split())
even_odd = [[False,False] for _ in range(n)]
path = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)

stack = [(0,0)]
even_odd[0][0] = True
evencnt = 0
while stack:
    p,ev = stack.pop()
    if ev == 0:
        evencnt += 1
        if even_odd[p][ev^1]:
            evencnt = -1
            break
    nev = ev^1
    for nxt in path[p]:
        if even_odd[nxt][nev]:continue
        even_odd[nxt][nev] = True
        stack.append((nxt,nev))
if evencnt == -1:
    print(n*(n-1)//2 - m)
else:
    print(evencnt*(n-evencnt) - m)

Solution (Python):
from collections import deque
n,m = map(int, input().split())
G = [[]for i in range(n)]
for _ in range(m):
    a,b = map(lambda z: int(z)-1,input().split())
    G[a].append(b)
    G[b].append(a)

color = [-1 for _ in range(n)]
queue = deque([0])
color[0] = 1
two = True
while queue:
    now = queue.popleft()
    for to in G[now]:
        if color[to] == color[now]:
            two = False
            break
        if color[to] == -1:
            color[to] = 1 - color[now]
            queue.append(to)

if two:
    print(sum(color)*(n-sum(color)) - m)
else:
    print(n*(n-1)//2 - m)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))







def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if not directed:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = LI()
A,B = LIR(M,2)

pt = edges_to_pt(A,B,N)

odd = [False]*N
even = [False]*N
even[0] = True

q = [0]
c = 1
flag = False
while q:
    q1 = []
    for v in q:
        for u in pt[v]:
            if c%2:
                if even[u]:
                    flag = True
                    break
                if not odd[u]:
                    odd[u] = True
                    q1.append(u)
            else:
                if odd[u]:
                    flag = True
                    break
                if not even[u]:
                    even[u] = True
                    q1.append(u)                
        if flag:
            break
    if flag:
        break
    q = q1
    c += 1

if flag:
    print(N*(N-1)//2 - M)
else:
    odds = 0
    evens = 0
    for i in range(N):
        if odd[i]:
            odds += 1
        else:
            evens += 1
    print(odds*evens - M)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)


def f(u,c):
    color[u] = c
    for v in graph[u]:
        if color[v] == 0: 
            if not f(v,-c):
                return False
        else:
            if color[v] == c: 
                return False
    return True 

flag = True
color = [0 for _ in range(N)]
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            flag = False
            break

if flag: 
    ans = color.count(1)*color.count(-1) - M
else:
    ans = N*(N-1)//2 - M

print(int(ans))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def is_bipartite(graph, colors):
    stack = [(0, 1)]
    while stack:
        v, color = stack.pop()
        colors[v] = color
        for child in graph[v]:
            if colors[child] == color:
                return False
            if colors[child] == 0:
                stack.append((child, -color))
    return True


def solve():
    N, M = map(int, rl().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        graph[b].append(a)
    
    colors = [0] * N
    if is_bipartite(graph, colors):
        w = colors.count(1)
        ans = w * (N - w) - M
    else:
        ans = N * (N - 1) // 2 - M
    print(ans)


if __name__ == '__main__':
    solve()