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 itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)




n,m = map(int,input().split())
G = defaultdict(set)
color = [0 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    G[a-1].add(b-1)
    G[b-1].add(a-1)

color[0]=1
que = deque([0])
bipartite = True
while len(que):
    p = que.popleft()
    for q in list(G[p]):
        if color[q] == 0:
            color[q] = -color[p]
            que.append(q)
        elif color[q] == color[p]:
            bipartite = False
            break
if bipartite:
    print(color.count(1)*color.count(-1)-m)
else:
    print(n*(n-1)//2-m)

Solution (Python):
from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = map(int, input().split())
 

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

nodes_color = {node:0 for node in range(1, N+1)}

nibu = True
stack = [1]

nodes_color[1] = 1

while stack:
    node = stack.pop()
    for next_node in l[node]:
        if nodes_color[next_node]==0:
            stack.append(next_node)
            nodes_color[next_node] = - nodes_color[node]
        else:
            if nodes_color[next_node]==nodes_color[node]:
                nibu = False
                break
    if not nibu:
        break

if nibu:
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))

Solution (Python):
n,m = map(int, input().split())


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


nibu = True
stack = [0]
col = [-1 for i in range(n)]
col[0]=0
while stack:
    p = stack.pop()
    for x in l[p]:
        if col[x]==-1:
            stack.append(x)
            if col[p]==0:
                col[x]=1
            else:
                col[x]=0
        else:
            if col[x]==col[p]:
                nibu = False
                break
    if not nibu:
        break

if nibu:
    print(col.count(1)*col.count(0)-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)
color=[0]*N
color[0]=1
que=deque()
que.append(0)
nibu=True
bla=1
whi=0
while(que):
    x=que.pop()
    for i in G[x]:
        if color[i]==color[x]:
            nibu=False
            break
        if color[i]==-color[x]:
            continue
        if color[i]==0:
            color[i]=-color[x]
            if color[i]==1:
                bla+=1
            else:
                whi+=1
            que.append(i)
            continue

if not nibu:
    print(N*(N-1)//2-M)
if nibu:
    print(bla*whi-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)
color=[-1]*N  
def dfs(x):
  for i in G[x]:
    if color[i]==-1:
      color[i]=1^color[x]
      dfs(i)
    elif color[i]==color[x]:
      print((N*(N-1))//2-M)
      exit()
color[0]=0
dfs(0)
b=0
for i in range(N):
  b+=color[i]
print(b*(N-b)-M)

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

color = [-1 for i in range(N)]
visits = [False for i in range(N)]
paths = deque()


def Bipartial():
    paths.append(0)
    color[0] = 0
    while paths:
        x = paths.pop()
        visits[x] = True
        for g in G[x]:
            if visits[g] and color[g] == color[x]:
                return False
            elif not visits[g]:
                paths.append(g)
                color[g] = (color[x]+1) % 2
    return True


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

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
Edges=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1; b-=1
    Edges[a].append(b)
    Edges[b].append(a)
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

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

if isbipartite():
    black=(sum(Colors)+n)//2
    white=n-black
    print(black*white-m)
else:
    print(n*(n-1)//2-m)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
Edges=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1; b-=1
    Edges[a].append(b)
    Edges[b].append(a)
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

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

if isbipartite():
    black=(sum(Colors)+n)//2
    white=n-black
    print(black*white-m)
else:
    print(n*(n-1)//2-m)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
F = sys.stdin
N, M = map(int, F.readline().strip("\n").split())
Edge = [[] for _ in range(N)]
for _ in range(M):
    A, B = 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)

Solution (Python):


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(input())
def MAP(): return 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


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)

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

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

visited = [-1 for i in range(n)]

edge = [[]for i in range(n)]

flag = True


def dfs(p,color):
    global flag
    if visited[p] == -1:
        visited[p] = color
        for next in edge[p]:
            dfs(next,color^1)
    elif visited[p] != color:
        flag = False




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

dfs(0,0)


if(flag):
    cnt = 0
    for i in range(n):
        if(visited[i] == 1): cnt += 1
    print(cnt*(n-cnt)-m)

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

Solution (Python):

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



color = [0] * N



def dfs(v, c):
    color[v] = c
    for to in G[v]:
        if color[to] == c:
            return False

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

    return True


Bipartite = dfs(0, 1)

if Bipartite:
    White = color.count(1)
    Black = color.count(-1)
    print(White * Black - M)

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

Solution (Python):

import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    g[a].append(b)
    g[b].append(a)
color=[0 for i in range(n)]
def check(v,c):
    color[v]=c
    for i in range(len(g[v])):
        if color[g[v][i]]==c:
            return False
        if color[g[v][i]]==0 and not check(g[v][i],-c):
            return False
    return True

for i in range(n):
    if color[i]==0:
        if not check(i,1):
            print(int((n-1)/2*n)-m)
            break
else:
    x,y=0,0
    for i in range(n):
        if color[i]==1:
            x+=1
        else:
            y+=1
    print(x*y-m)
    exit()

Solution (Python):
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
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)
kyo = [-1]*n
def dfs(x,y,z):
        for i in g[x]:
                if i == y: continue
                if kyo[i] == -1:
                        kyo[i] = (z+1)%2
                        dfs(i,x,z+1)
                else:
                        if kyo[i] !=  (z+1)%2:
                                print(n*(n-1)//2-m)
                                exit()
                
kyo[0] = 0
dfs(0,0,0)
ki = 0
gu = 0
for i in kyo:
        if i %2 == 0:
                gu += 1
        else:
                ki += 1
print(gu*ki-m)

Solution (Python):
N,M=map(int,input().split())
G=[set() for i in range(N)]
a=[0 for i in range(M)]
b=[0 for i in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].add(b[i])
    G[b[i]].add(a[i])
q=[0]
reached=[0 for i in range(N)];reached[0]=1
color=[0 for i in range(N)];color[0]=1
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if reached[p]==1:
            continue
        reached[p]=1
        color[p]=-color[r]
        q.append(p)
flag=1
for i in range(M):
    if color[a[i]]+color[b[i]]!=0:
        flag=0
        break
if flag==1:
    X=0
    Y=0
    for i in range(N):
        if color[i]==1:
            X+=1
        else:
            Y+=1
    print(X*Y-M)
else:
    print(-M+(N*(N-1))//2)

Solution (Python):
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)

Solution (Python):



import sys
sys.setrecursionlimit(100000)
fin = sys.stdin.readline

N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(elem) - 1 for elem in fin().split()]
    adj[a].append(b)
    adj[b].append(a)


def judge_bipartite(adj, v, color, colors):
    colors[v] = color
    for neighbor in adj[v]:
        if colors[neighbor] is None:
            if not judge_bipartite(adj, neighbor, 1 - color, colors):
                return False
        else:
            if colors[neighbor] == color:
                return False
    else:
        return True

colors = [None] * N
bipartite = judge_bipartite(adj, 0, 0, colors)

if not bipartite:
    print(N * (N - 1) // 2 - M)
else:
    num_b = sum([v == 0 for v in colors])
    num_w = N - num_b
    print(num_b * num_w - M)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
fin = sys.stdin.readline

N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(elem) - 1 for elem in fin().split()]
    adj[a].append(b)
    adj[b].append(a)


def judge_bipartite(adj, v, color, colors):
    colors[v] = color
    for neighbor in adj[v]:
        if colors[neighbor] is None:
            if not judge_bipartite(adj, neighbor, 1 - color, colors):
                return False
        else:
            if colors[neighbor] == color:
                return False
    else:
        return True

colors = [None] * N
bipartite = judge_bipartite(adj, 0, 0, colors)

if not bipartite:
    print(N * (N - 1) // 2 - M)
else:
    num_b = sum([v == 0 for v in colors])
    num_w = N - num_b
    print(num_b * num_w - M)

Solution (Python):
N, M = map(int, input().split())
V = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    V[A].append(B)
    V[B].append(A)

L = [-1]*(N+1)
L[1] = 0
al = False

from collections import deque
Open = deque()
Open.append(1)
Close = set()
while len(Open)>0:
    v = Open.pop()
    Close.add(v)
    for v2 in V[v]:
        if v2 not in Close:
            Open.append(v2)
        if L[v2] == -1:
            L[v2] = 1-L[v]
        elif L[v] + L[v2] != 1:
            al = True
            break
    if al:
        break

if al:
    print(N*(N-1)//2-M)
else:
    c = L.count(1)
    print(c*(N-c)-M)

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

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


color = [0] * N



def dfs(v, c):
    color[v] = c
    for to in G[v]:
        if color[to] == c:
            return False

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

    return True


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

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def dfs(graph:list, node:int, start:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    stack = [(0,start)]
    
    while stack:
        cost, cur_node = stack.pop()

        
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                stack.append((dist[nex_node],nex_node))
                
    return dist

def isnibu(graph:list, dist:list) -> bool:
    for i,edges in enumerate(graph):
        for _, j in edges:
            if dist[i]%2 == dist[j]%2:
                return False
    
    return True
    
    

n,m = li()

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

for _ in range(m):
    a,b = li_()
    
    adj_lst[a].add((1,b))
    adj_lst[b].add((1,a))
    
dist = dfs(adj_lst, n, 0)

nibu = isnibu(adj_lst, dist)

ans = 0
if isnibu(adj_lst, dist):
    ans = sum([dist[i]%2 == 1 for i in range(n)]) * sum([dist[i]%2 == 0 for i in range(n)]) - m
    
else:
    ans = n*(n-1)//2 - m
    
print(ans)

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def dfs(graph:list, node:int, start:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    stack = [(0,start)]
    
    while stack:
        cost, cur_node = stack.pop()

        
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                stack.append((dist[nex_node],nex_node))
                
    return dist

def isnibu(graph:list, dist:list) -> bool:
    for i,edges in enumerate(graph):
        for _, j in edges:
            if dist[i]%2 == dist[j]%2:
                return False
    
    return True
    
    

n,m = li()

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

for _ in range(m):
    a,b = li_()
    
    adj_lst[a].add((1,b))
    adj_lst[b].add((1,a))
    
dist = dfs(adj_lst, n, 0)

nibu = isnibu(adj_lst, dist)

ans = 0
if isnibu(adj_lst, dist):
    ans = sum([dist[i]%2 == 1 for i in range(n)]) * sum([dist[i]%2 == 0 for i in range(n)]) - m
    
else:
    ans = n*(n-1)//2 - m
    
print(ans)

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

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

G = [[] for i in range(N)]
for _ in range(M):
    Ai, Bi = map(int, input().split())
    G[Ai - 1].append(Bi - 1)
    G[Bi - 1].append(Ai - 1)

color = [0] * N
def dfs(v, c):
    '''
    頂点vをcで塗る　そこから深さ優先探索で交互に塗っていく
    '''
    color[v] = c
    for i in G[v]:
        if color[i] == c:
            return False
        if color[i] == 0 and not(dfs(i, -c)):
            return False
    return True

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

Solution (Python):
from collections import defaultdict 
import sys

sys.setrecursionlimit(10**8)


N,M = map(int,input().split())
dict = defaultdict(set)

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


color = [0 for i in range(N+1)]
nibu = True

def dfs(v,c):
	u'''
	v : 現在のグラフの頂点
	c : vのグラフのcolor
	queue : 探索済みのグラフの頂点
	res   : 二部グラフの判定 bool
	'''

	global color
	global nibu 

	for i in list(dict[v]):
		if color[i] == c:
			nibu = False
			break
		elif color[i] == 0:	
			color[i] = c*-1		
			dfs(i,-c)		


color[1] = 1  

dfs(1,1)

if nibu:
	b = color.count(1)
	w = color.count(-1)
	ans = b * w - M
else:
	ans = N * (N-1)//2 - M
	
print(ans)

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

N, M = map(int, input().split())
adjL = [[] for v in range(N)]
for e in range(M):
    A, B = map(int, input().split())
    adjL[A - 1].append(B - 1)
    adjL[B - 1].append(A - 1)


colors = [0] * N

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

    return True


IsBipartite = dfs(0, 1)

if IsBipartite:
    
    num = colors.count(1)
    print(num * (N - num) - M)
else:
    
    print(N * (N - 1) // 2 - M)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
Table=[[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    Table[a-1].append(b-1)
    Table[b-1].append(a-1)
visit=[False]*N
iro=[-1]*N
kei=deque()
def nibu():
    kei.append(0)
    iro[0]=0
    while kei:
        x = kei.pop()
        visit[x]=True
        for i in Table[x]:
            if visit[i] and iro[i] == iro[x]:
                return False
            elif not visit[i]:
                kei.append(i)
                iro[i]=(iro[x]+1)%2
    return True
if nibu():
    B = iro.count(0)
    W = iro.count(1)
    ans = B*W-M
else:
    ans = (N*(N-1))//2 -M
print(ans)

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

memo = [0 for i in range(n)]
color = [-1 for i in range(n)]
black = 0
white = 0
flag = 0


def search(v):
    for i in graph[v]:
        if memo[i] == 0:
            memo[i] = 1
            color[i] = (color[v] + 1) % 2
            if color[i] == 0:
                global black
                black += 1
            else:
                global white
                white += 1
            search(i)
        else:
            if color[v] == color[i]:
                global flag
                flag = 1

memo[0] = 1
color[0] = 0
black += 1
search(0)

if flag == 1:
    print(n*(n-1)//2 - m)
else:
    print(black * white - m)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
edge = [[] for i 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)

color=[-1 for i in range(n)]
def dfs(pos):
    ret = True
    for i in range(len(edge[pos])):
        to = edge[pos][i]
        if color[to] == -1:
            color[to] = 1 ^ color[pos]
            ret &= dfs(to)
        else:
            ret &= not (color[to]==color[pos])
    return ret

color[0]=0
if dfs(0):
    black, white = 0, 0
    for i in range(n):
        if color[i]==0:
            black += 1
        else:
            white += 1
    print(black*white-m)
else:
    print(n*(n-1)//2-m)

Solution (Python):

from collections import deque
def inpl(): return map(int, input().split())
N, M = inpl()
G = [[] for _ in range(N+1)]

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

visited = [False] * (N+1)
color = [0] * (N+1)

Q = deque()
Q.append(1)

bipartite = True
while Q:
    p = Q.popleft()
    if visited[p]:
        continue
    visited[p] = True
    for q in G[p]:
        if visited[q]:
            if color[p] == color[q]:
                bipartite = False
                break
        else:
            color[q] = color[p]^1
            Q.append(q)

if bipartite:
    B = sum(color)
    W = N - B
    print(B*W-M)
else:
    print(N*(N-1)//2 - M)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	



def dfs(v):
	F[v]=1
	for i in nl[v]:
		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			
			print N*(N-1)/2-M
			sys.exit()
		else:
			continue
		
		
		if F[i]==0:
			dfs(i)


F=[0]*(N+1)
color=[0]*(N+1)
color[1]="w"
dfs(1)


print color.count("b")*color.count("w")-M

Solution (Python):
from collections import deque
from collections import defaultdict
from collections import Counter

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

color = [0 for i in range(N+1)]

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

color[1] = 1
que = deque([1])
concatenation = False

while len(que):
    p = que.popleft()
    for q in list(G[p]):
        if color[q] == 0:
            color[q] = -color[p]
            que.append(q)
        elif color[q] == color[p]:
            concatenation = True
            break
    
if concatenation:
    print(int(N*(N-1)/2-M))
else:
    B = Counter(color)[1]
    W = Counter(color)[-1]
    print(B*W-M)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(v, c):
    flgs[v] = c
    for i in range(len(G[v])):
        if flgs[G[v][i]] == c:
            return False
        if flgs[G[v][i]] == 0 and not dfs(G[v][i], -c):
            return False

    return True


if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [[] for _ in range(N + 1)]
    for i in range(M):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)

    
    bi_flg = True
    flgs = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        if flgs[i] == 0:
            if not dfs(i, 1):
                bi_flg = False

    if bi_flg:
        
        print(flgs.count(1) * flgs.count(-1) - M)
    else:
        
        print((N * (N - 1) // 2) - M)

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

N,M = map(int,raw_input().split())
es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_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 = (sum(colors) + N) // 2
  w = N-b
  print(b*w - M)
else:
  all = N*(N-1) // 2
  print(all - M)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,m = LI()
    e = collections.defaultdict(set)
    t = [0] * n
    for _ in range(m):
        a,b = LI_()
        e[a].add(b)
        e[b].add(a)

    q = [0]
    t[0] = 1
    for i in range(n):
        c = q[i]
        tc = t[c]
        for d in e[c]:
            if t[d] == 0:
                t[d] = 3-tc
                q.append(d)
            elif t[d] == tc:
                return n*(n-1) // 2 - m

    a = sum(t) - n

    return a*(n-a) - m


print(main())

Solution (Python):


import sys



REC_LIMIT = 100000


UNDEF = 0
WHITE = 1
BLACK = -WHITE





def is_bipartite_graph(adj_list):
    n = len(adj_list)  
    color = [UNDEF] * n

    
    def dfs(v, c):
        color[v] = c
        for u in adj_list[v]:
            if color[u] == c:
                
                return False
            if color[u] == UNDEF and not dfs(u, -c):
                
                return False
        return True  
    for i in range(n):
        if color[i] == 0:
            
            if not dfs(i, WHITE):
                return (False, None)
    return (True, color)


def compute_max_additional_edges(n, m, adj_list):
    is_bi, color = is_bipartite_graph(adj_list)
    if not is_bi:
        
        return n * (n - 1) // 2 - m
    else:
        
        w = sum(c == WHITE for c in color)
        b = sum(c == BLACK for c in color)
        return w * b - m


def main():
    
    sys.setrecursionlimit(REC_LIMIT)
    
    n, m = (int(x) for x in input().split())
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        a, b = (int(x) - 1 for x in input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    res = compute_max_additional_edges(n, m, adj_list)
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
'''
問題
http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_c
解説
https://img.atcoder.jp/code-festival-2017-qualb/editorial.pdf
参考
http://code-festival-2017-qualb.contest.atcoder.jp/submissions/1666106
'''
from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))

def is_biparate(links):
    '''
    0=white,1=blackとする
    2部グラフなら黒に塗られている頂点の数を返す
    2部グラフでないなら-1を返す。
    '''
    
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]  
    visited = set()
    while q:
        v, c = q.pop()
        if v in visited:
            if colors[v] != c: 
                return -1
            continue
        visited.add(v)
        colors[v] = c
        for u in links[v]:
            q.append((u, c ^ 1))  
    return sum(colors)  
 




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

def main():
    for _ in range(m):
        a, b = readLine_int_list()
        a -= 1
        b -= 1
        g[a].add(b)
        g[b].add(a)
    
    
    
    bp1 = is_biparate(g)
    if bp1 == -1:
        '''
        2部グラフではない場合
            結論：完全グラフになるまで辺を追加できる
            →why
                奇サイクル上のある点をvとする
                s → v → tが偶数長でも、 奇サイクルの他の頂点を余計に経由することで奇数長になる
                s → tが奇数長になれば線が引ける
                つまり、任意の頂点間において奇数長が存在することになる
            完全グラフの辺の数は、n * (n - 1) // 2
            これには元あった辺の数まで含まれているので、 -m する
        '''
        max_m = n * (n - 1) // 2
    else:
        '''
        2部グラフの場合
            結論:(blackの数*whiteの数)本、線ができる
            why
                奇数閉路が存在しない => 異なる色間は必ず奇数長、同色間は必ず偶数長 
                1. whiteとblackの間は奇数長のパスが存在する ->線が引ける
                2. 同じ色どうしには奇数長のパスは存在しない -> 線は引かれない
                black=3, white=2の時の線の引き方 = b*w
            b*wにはパスの長さが1つまりもともとのパスが含まれてるので、-m　する
        '''
        max_m = bp1 * (n - bp1)
        
    print(max_m - m)
    

if __name__ == "__main__":
    main()