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):
import sys,os,io
input = sys.stdin.readline

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
from collections import deque
cnts = [-1]*N
cnts[0] = 0
d = deque([(0,1)])
while len(d)>0:
  v,cnt = d.popleft()
  for w in edge[v]:
    if cnts[w]==-1:
      cnts[w] = cnt
    elif (cnt-cnts[w])%2==1:
      print(N*(N-1)//2-M)
      break
    elif w==0 or cnts[w]%2==1:
      continue
    d.append((w,cnt+1))
  else:
    continue
  break
else:
  n = sum(map(lambda x:x%2==1, cnts))
  ans = n*(N-n)-M
  print(ans)

Solution (Python):
from collections import deque


class Graph:
    def __init__(self, n):
        self.n = n
        self.edge = [[] for _ in range(n)]
        self.color = [-1] * n

    def add_edge(self, node1, node2):
        self.edge[node1].append(node2)
        self.edge[node2].append(node1)

    def is_bipartite_graph(self):
        self.color = [-1] * self.n

        for i in range(self.n):
            if self.color[i] == -1:
                self.color[i] = 0
                d = deque([(i, 0)])

                while d:
                    node, c = d.pop()
                    for j in self.edge[node]:
                        if self.color[j] == -1:
                            self.color[j] = c ^ 1
                            d.append((j, self.color[j]))
                        elif self.color[j] == c:
                            return False

        return True


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

g = Graph(N)

for i in range(M):
    A, B = map(int, input().split())
    g.add_edge(A-1, B-1)

if g.is_bipartite_graph():
    zero = g.color.count(0)
    print(zero * (N - zero) - M)
else:
    print(N * (N - 1) // 2 - M)

Solution (Python):
n,m=map(int, input().split())
e=[[]for _ in range(n)]
for _ in range(m):
    ai,bi=map(int, input().split())
    ai-=1;bi-=1
    e[ai].append(bi);e[bi].append(ai)

nibu=[-1]*n
nibu[0]=0
from collections import deque,Counter
q=deque([0])
al=False
while q:
    u=q.popleft()
    for v in e[u]:
        if nibu[v]>=0:
            if nibu[u]==nibu[v]:
                al=True
                break
        else:
            nibu[v]=nibu[u]^1
            q.append(v)
        
    if al:
        break
if not al:
    c=Counter(nibu)
    ans=c[0]*c[1]
    ans-=m
else:
    ans=n*(n-1)//2-m
print(ans)

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

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

graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(graph, queue, color):
    is_bigraph = True
    while queue:
        current = queue.pop()

        for _next in graph[current]:
            if color[_next] != -1:
                if color[_next] == color[current]:
                    is_bigraph = False
            else:
                color[_next] = 1 - color[current]
                queue.append(_next)
    return is_bigraph

queue = [1]
color = [-1] + [-1] * n
color[1] = 0

if dfs(graph, queue, color):
    print(color.count(0) * color.count(1) - m)
else:
    print((n * (n - 1)) // 2 - m)

Solution (Python):
import sys

sys.setrecursionlimit(10**6)
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,M = MI()
Graph = [[] for _ in range(N+1)]
for i in range(M):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)




colors = [0]*(N+1)


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


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

Solution (Python):

from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
	a,b = 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)

Solution (Python):

from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
	a,b = 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)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
connect = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    connect[a].append(b)
    connect[b].append(a)
color = [-1]*n
color[0] = 0
next = deque([0])
Yes = True
while next:
    now = next.popleft()
    C = (color[now]+1)%2
    for a in connect[now]:
        if color[a] != -1:
            if color[a] != C:
                Yes = False
            continue
        color[a] = C
        next.append(a)
if Yes:
    s=sum(color)
    print(s*(n-s)-m)
else:
    print(n*(n-1)//2-m)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
connect = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    connect[a].append(b)
    connect[b].append(a)
color = [-1]*n
color[0] = 0
next = deque([0])
Yes = True
while next:
    now = next.popleft()
    for a in connect[now]:
        if color[a] != -1:
            if color[a] != (color[now]+1)%2:
                Yes = False
            continue
        color[a] = (color[now]+1)%2
        next.append(a)
if Yes:
    s=sum(color)
    print(s*(n-s)-m)
else:
    print(n*(n-1)//2-m)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
connect = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    connect[a].append(b)
    connect[b].append(a)
 
color = [-1]*n
color[0] = 0
explored = {0}
next = deque([0])
exploring =deque()
Yes = True
 
while next:
    now = next.popleft()
    exploring.extend(connect[now])
    while exploring:
        a = exploring.popleft()
        if color[a] == -1:
            color[a]=(color[now]+1)%2
        elif color[a] == (color[now]+1)%2:
            pass
        else:
            Yes = False
        if a not in explored:
            next.append(a)
        explored.add(a)
 
 
 
if Yes:
    s=sum(color)
    print(s*(n-s)-m)
else:
    print(n*(n-1)//2-m)

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

color = [-1]*n
color[0] = 0
explored = {0}
next = deque([0])
exploring =deque()
Yes = True
explored.add(0)
while next:
    now = next.popleft()
    for a in connect[now]:
        if color[a] != -1:
            if color[a] != (color[now]+1)%2:
                Yes = False
            continue
        color[a] = (color[now]+1)%2
        next.append(a)
        
        
    '''
    exploring.extend(connect[now])
    while exploring:
        a = exploring.popleft()
        if color[a] == -1:
            color[a]=(color[now]+1)%2
        elif color[a] == (color[now]+1)%2:
            pass
        else:
            Yes = False
        if a not in explored:
            next.append(a)
        explored.add(a)
        '''
if Yes:
    s=sum(color)
    print(s*(n-s)-m)
else:
    print(n*(n-1)//2-m)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from collections import deque
stack = deque([0])
colors = [-1]*N
colors[0] = 0

while stack:
    v = stack.pop()
    for nx in graph[v]:
        if colors[nx]==-1:
            colors[nx] = colors[v]^1
            stack.append(nx)
        else:
            if colors[nx]==colors[v]:
                print(N*(N-1)//2-M)
                exit()

ones = sum(colors)
zeros = N-ones
print(ones*zeros-M)

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

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

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)
ans=0
colors=[0]*(n+1)
is_bipartite=dfs(1,1)
if is_bipartite==True:
  ans=colors.count(1)*colors.count(-1)-m
else:
  ans=(n*(n-1))//2-m
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
graph=[[] for _ in range(N)]
color=[-1]*N
for _ in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

def steps(v,col=0):
    color[v]=col
    for nv in graph[v]:
        if color[nv]!=-1:
            if color[nv]==col: return False
            continue
        if not steps(nv,1-col): return False
    return True

flag=True
for v in range(N):
    if color[v]!=-1: continue
    if not steps(v): flag=False

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

Solution (Python):

import sys
sys.setrecursionlimit(10**7)

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




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

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


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


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

if is_bipartite():
  B = colors.count(1)
  W = colors.count(-1)
  ans = B * W - M
else:
  ans = int(N * (N - 1) / 2) - M
  
  
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int,readline().split())
data = list(map(int,read().split()))

links = [[] for _ in range(n+1)]
it = iter(data)
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

color = [-1] * (n+1)
color[1] = 0
stack = [1]
while(stack):
    i = stack.pop()
    ci = color[i]
    for j in links[i]:
        if(color[j] == -1):
            color[j] = 1-ci
            stack.append(j)
        else:
            if(color[j]==ci):
                ans = (n*(n-1))//2 - m
                print(ans)
                exit()

n0 = color.count(0)
n1 = color.count(1)
ans = n0*n1 - m
print(ans)

Solution (Python):
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]

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


visited = [False for _ in range(N)]
color = [0 for _ in range(N)]

def dfs(now, c):

    color[now] = c

    for adj in graph[now]:
        if color[adj] == c:
            return False

        if color[adj] == 0 and not dfs(adj, -c):
            return False

    return True

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

Solution (Python):

from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]
for i in range(M):
    a,b=f()
    if not i:
        fa,fb=a,b
    G[a].append(b)
    G[b].append(a)
    
res=0
INF=10**9

def bfs(a):
    q=deque()
    q.append(a)
    d=[0]*(N+1)
    d[a]=1
    res=0
    while q:
        r=q.popleft()
        for nr in G[r]:
            if d[nr]==0:
                q.append(nr)
                d[nr]=-d[r]
            else:
                if d[nr]==d[r]:
                    return (False,[])
    return (True,d)
check=bfs(1)
if not check[0]:
    print((N*(N-1))//2-M)
else:
    print(check[1].count(1)*check[1].count(-1)-M)

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

def main():
    n, m = map(int, input().split())
    
    tree = [[] for _ in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    judge = True
    dist = [0]*n
    already = [False]*n
    not_yet = deque([0])
    already[0] = True
    while not_yet:
        key = not_yet.popleft()
        for v in tree[key]:
            if already[v]:
                if dist[v] != (dist[key] + 1) % 2:
                    judge = False
                continue
            already[v] = True
            dist[v] = (dist[key] + 1) % 2
            not_yet.append(v)
    
    if judge:
        sub = sum(dist)
        ans = sub * (n - sub) - m
    else:
        ans = n * (n - 1) // 2 - m
    
    print(ans)
    
    
    
    
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright






n,m=map(int,input().split())
G=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
C=[-1]*n
C[0]=0
def dfs(x):
    for v in G[x]:
        if C[v]==C[x]:
            print(n*(n-1)//2-m)
            exit()
        if C[v]==-1:
            C[v]=1-C[x]
            dfs(v)
dfs(0)
q=C.count(0)

print(q*(n-q)-m)

Solution (Python):
import sys

N, M = map(int, input().split())
sys.setrecursionlimit(10**6)
I = [[] for _ in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  I[a].append(b)
  I[b].append(a)

C = [-1 for _ in range(N)] 
visited = set()

def DFS(p, c):
  C[p] = c
  flag = True
  for q in I[p]:
    
    if C[q] == c:
      return False
    elif C[q] == -1:
      if not DFS(q, 1-c):
        return False
  return True



print(C.count(0)*C.count(1)-M if DFS(0, 0) else N*(N-1)//2-M)

Solution (Python):
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    def bfs(n, e, fordfs):
        
        W = [-1] * n
        
        W[e] = 0
        C = [0]*2
        C[0] = 1
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            color = 1^W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = color
                    que.append(ne)
                    C[color] += 1
                else:
                    if color!=W[ne]:
                        return n*(n-1)//2
        rep = C[0]*C[1]
        return rep
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    ans = bfs(N,0,V) - M
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):



def main():
    N, M = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    def dfs(s):
        """
        二部グラフか判定
        """
        stack = [s]
        color = [-1]*N
        color[s] = 0
        while stack:
            v = stack.pop()
            for u in G[v]:
                if color[u] != -1:
                    if color[u] == color[v]:
                        
                        return False, color
                    continue
                color[u] = color[v] ^ 1
                stack.append(u)
        return True, color

    is_bipartite, color = dfs(0)
    if is_bipartite:
        
        b = sum(color)
        w = N - b
        print(b*w - M)
    else:
        
        
        print(N*(N-1)//2 - M)


if __name__ == '__main__':
    main()

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

def bfs():
    q = deque([0])
    color = [0]*N
    color[0] = 1
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if color[nv]==0:
                color[nv] = -color[v]
                q.append(nv)
            else:
                if color[nv]==color[v]:
                    return [0]*N
        
    return color

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)

color = bfs()

if color==[0]*N:
    print(N*(N-1)//2-M)
else:
    b = color.count(1)
    w = N-b
    print(b*w-M)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
d=[-1]*(n+1)
for i in range(m):
  a,b=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)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
d=[-1]*(n+1)
for i in range(m):
  a,b=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)

Solution (Python):

def bipartite_graph_check(n,edge):
  color = [-1] * n
  for i in range(n):
    if color[i] != -1:
      continue
    stack = [i]
    color[i] = 0
    for node in stack:
      for mode in edge[node]:
        if color[mode] == -1:
          stack.append(mode)
          color[mode] = color[node] ^ 1
        elif color[mode] == color[node]:
          return False
  
  return color
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
if bipartite_graph_check(n,edge):
  color=bipartite_graph_check(n,edge)
  print(color.count(0)*color.count(1)-m)
else:
  print(n*(n-1)//2-m)

Solution (Python):
from sys import setrecursionlimit

setrecursionlimit(10**6)

def dfs(v):
    flag = True

    for nxt in edge[v]:
        if l[v] == l[nxt]:
            return False
        elif l[v] + l[nxt] == 1:
            continue
        else:
            l[nxt] = 1 - l[v]
            cnt[1-l[v]] += 1
            flag &= dfs(nxt)
    
    return flag
        

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

l = [-1] * n
l[0] = 0
cnt = [1, 0]

if dfs(0):
    print(cnt[0] * cnt[1] - m)
else:
    print(n * (n - 1) // 2 - m)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    def dfs(node, color):
        
        
        node_color[node] = color
        adjnodes = edges[node]
        for anode in adjnodes:
            anode_color = node_color[anode]
            if anode_color == 0:
                dfs(anode, -color)
            elif anode_color == color:
                gisnibu[0] = 0
                break
            else:
                pass

    
    n, m = map(int, input().split())
    edges = {e: [] for e in range(n)}
    e = map(int, read().split())
    for a, b in zip(e, e):
        a -= 1
        b -= 1
        edges[a].append(b)
        edges[b].append(a)

    
    node_color = [0] * n
    gisnibu = [1] * 1
    dfs(0, 1)

    
    if gisnibu[0]:
        r = node_color.count(1) * node_color.count(-1) - m
        print(r)
    else:
        r = (n * (n - 1)) // 2 - m
        print(r)

if __name__ == '__main__':
    main()

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

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

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

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


if dfs(0,1): 
  one = 0; zero = 0
  for x in colors:
    if x == 1:
      one += 1
    else:
      zero += 1
  ans = one*zero-M
else:
  ans = N*(N-1)//2-M
print(ans)

Solution (Python):
"""
奇数本で構成される閉路が存在している場合、全ての頂点同士を結ぶことができる
そうでない場合、、、
奇数本でつながっている辺同士は直接結ぶことができる＝グラフっは二部グラフとなっていて、
AグループとBグループのノード同士を結ぶことができる。
"""

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)

steps = [None]*(N+1)

def dfs(node,step):
    if steps[node] != None:
        if (step - steps[node])%2 == 1:
            return True
        else:
            return False
    else:
        steps[node] = step
        res = False
        for nx in edges[node]:
            res = res or dfs(nx,step+1)
        return res

res = dfs(1,0)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
if res:
    print(choose(N,2)-M)
else:
    for i in range(1,N+1):
        steps[i] %= 2
    odd = steps.count(1)
    even = N - odd
    print(odd*even-M)

Solution (Python):
def main():
  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())
    a-=1;b-=1
    g[a].append(b)
    g[b].append(a)
  dp=[[False]*2 for _ in range(n)]
  dp[0][0]=True
  bfs=deque([0])
  while bfs:
    top=bfs.popleft()
    cur,par=top>>1,top&1
    for to in g[cur]:
      if not dp[to][par^1]:
        dp[to][par^1]=True
        bfs.append((to<<1)+(par^1))
  x=0;y=0;z=0
  for i in range(n):
    if dp[i][0] and dp[i][1]:
      x+=1
    elif dp[i][0]:
      y+=1
    elif dp[i][1]:
      z+=1
  ans=-m
  ans+=x*(x-1)>>1
  ans+=x*(y+z)
  ans+=y*z
  print(ans)

if __name__=='__main__':
  main()

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):
import sys
sys.setrecursionlimit(10**7)

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

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



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)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()
    node = [-1] * N
    edge = [[] for _ in range(N)]
    for _ in range(M):
        a,b = _LI()
        edge[a].append(b)
        edge[b].append(a)

    node[0] = 0
    q = collections.deque()
    q.append((0,0))
    d = [0] * 2
    while q:
        u,c = q.popleft()
        for v in edge[u]:
            if c == node[v]:
                break
            if node[v] < 0:
                node[v] = 1-c
                q.append((v,node[v]))
        else:
            continue
        d[1] = N-1
        node = [0] * N
        break
    else:
        d[0] = node.count(0)
        d[1] = node.count(1)

    ans = 0
    for i in range(N):
        ans += d[1-node[i]] - len(edge[i])
    print(ans//2)

if __name__ == '__main__':
    main()

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




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import deque

def main():
	n,m=MI()

	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	

	D=[-1]*(n+1)


	Q=deque()
	Q.append([1,0])

	

	f=0

	while Q:
		
		now,d=Q.pop()
		D[now]=d
		for nx in G[now]:
			if D[nx]==-1:
				Q.append([nx,1-d])
			elif D[nx]!=d:
				continue
			else:
				f=1
				break


	if f==1:
		ans=(n*(n-1))//2
	else:
		ans=D.count(0)*D.count(1)


	ans-=m

	print(ans)

















if __name__ == "__main__":
	main()

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for _ in range(n+1)]
    for i in range(m):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)
    nms = [set([1]),set()]
    lst = [(1,0)]
    while lst:
        li,ti = lst.pop()
        for j in way[li]:
            if j in nms[ti]:
                print(n*(n-1)//2-m)
                exit()
            elif not j in nms[1-ti]:
                nms[1-ti].add(j)
                lst.append((j,1-ti))

    l0 = len(nms[0])
    l1 = len(nms[1])
    print(l0*l1-m)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N, M = map(int, input().split())
adj = [ [] for _ in range(N)]
clr = [-1 for _ in range(N)]


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


vis = [0 for _ in range(N)]
q = deque([(0,0)])
is_bip = True

while q:
  p, c = q.popleft()
  clr[p] = c
  vis[p] = 1
  for x, w in adj[p]:
    if vis[x] == 0:
      q.append((x,(w+c)%2))
      
    else: 
      if (clr[x] + c) % 2 == 0:
        is_bip = False
        break
  if not is_bip:
    break
    

if is_bip:
  apple = clr.count(0)
  orange = clr.count(1)
  
  print(apple*orange-M)
  
else:
  print(N*(N-1)//2-M)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from collections import deque,defaultdict,Counter
def main():
    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)
    
    ans = N*(N - 1)//2 - M
    color = [-1] * N
    q = deque([0])
    color[0] = 0
    bi = True
    while q:
        v = q.popleft()
        for e in G[v]:
            if color[e] >= 0:
                if color[e] == color[v]:
                    bi = False
                continue
            color[e] = color[v]^1
            q.append(e)
    if bi:
        white = 0
        black = 0
        for i in range(N):
            if color[i] == 0:
                white += 1
            else:
                black += 1
        ans -= white*(white - 1)//2 + black*(black - 1)//2
    print(ans)
if __name__ == '__main__':
    main()