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
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m = myinput()
ab = [ list(myinput()) for _ in range(m) ]

g = [ [] for _ in range(n) ]
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)


def dfs(g):
    color = [0]*n
    stack = deque()
    stack.append([0,1])
    while stack:
        tmp = stack.pop()
        v = tmp[0]
        c = tmp[1]
        color[v] = c
        for i in g[v]:
            if color[i]==c:
                return False,[]
            elif color[i]==0:
                stack.append([i,-1*c])
    return True,color

flag,color =  dfs(g)

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

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


def dfs(u, c):
    color[u] = c
    for v in g[u]:
        if color[v] != -1:
            if color[v] == c:
                return False
        else:
            if not dfs(v, c ^ 1):
                return False
    return True


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)

flag = True
color = [-1] * n
for i in range(n):
    if color[i] == -1:
        if not dfs(i, 0):
            flag = False
            break
if flag:
    w = color.count(0)
    ans = w * (n - 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 _ 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)
flag = True
color = [-1] * n
que = deque()
que.append((0,0))
while que:
    u, c = que.popleft()
    if color[u] == -1:  
        color[u] = c
        for e in g[u]:
            que.append((e, c ^ 1))  
    else:
        if color[u] != c:
            flag = False
            break
if flag:
    w = len([i for i in color if i == 0])
    ans = w * (n - w) - m
else:
    ans = (n * (n - 1) // 2 - m)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N, M, *L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for a,b in zip(*[iter(L)]*2):
  dic[a].append(b)
  dic[b].append(a)
color = [0]*(N+1)
def dfs(v,c):
  color[v] = c
  for u in dic[v]:
    if color[u]==c:
      return False
    if color[u]==0 and not dfs(u,-c):
      return False
  return True
for i in range(1,N+1):
  if color[i]==0:
    if not dfs(i,1):
      print(N*(N-1)//2-M)
      break
else:
  w = sum(c==1 for c in color)
  b = N-w
  print(w*b-M)

Solution (Python):

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)

color = [0] * N

def is_bipartite():
    """ 二部グラフか判定する """
    stack = [(0,1)]
    while stack:
        v, c = stack.pop()
        color[v] = c
        for w in edge[v]:
            if color[w] == c: return False
            if color[w] == 0:
                stack.append((w, (-1) * c))
    return True

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

Solution (Python):
N, M = map(int, input().split())
edges = [[] for _ in range(N)]

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

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

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

    return sum(sign)

s = isBipartite()

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

Solution (Python):
N, M = map(int, input().split())
edges = [[] for _ in range(N)]

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

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

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

    return sum(sign)

s = isBipartite()

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

Solution (Python):
N, M = map(int, input().split())
edges = [[] for _ in range(N)]

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

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

        if sign[now] != -1 and sign[now] != p:
            return -1
        if sign[now] == p:
            continue
        sign[now] = p

        for to in edges[now]:
            st.append((to, (p + 1) % 2))

    return sum(sign)

s = isBipartite()

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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for i in range(N)]
for a,b in AB:
    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 = N-b
    print(b*w-M)
else:
    whole = N*(N-1)//2
    print(whole-M)

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

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

connection=[[] for i in range(n)]
for i in range(m):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

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

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

if dfs(0,1)==0:
  print(n*(n-1)//2-m)
  sys.exit()

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

B=bfs(0)
cta=0;ctb=0
for i in range(n):
  if B[i]%2==0:
    cta+=1
  else:
    ctb+=1
print(cta*ctb-m)

Solution (Python):
from collections import deque


def main():

    N, M = map(int, input().split())
    G = [set() for _ in range(N)]
    for _ in range(M):
        A, B = map(lambda x: int(x) - 1, input().split())
        G[A].add(B)
        G[B].add(A)

    q = deque([0])
    side = [-1] * N
    side[0] = 0
    while q:
        v = q.pop()
        for n in G[v]:
            if side[n] != -1:
                
                if side[n] != (side[v] + 1) % 2:
                    print(int(N * (N - 1) / 2) - M)
                    exit()
                continue
            q.appendleft(n)
            side[n] = (side[v] + 1) % 2

    
    side = sum(side)
    print(side * (N - side) - M)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from sys import stdin
def main():
    N,M = map(int,stdin.readline().split())
    edge = defaultdict(list)
    color = [-1]*N
    for _ in range(M):
        a,b = map(int,stdin.readline().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    stack = [0]
    color[0] = 0
    flag = 1
    while stack:
        u = stack.pop()
        for v in edge[u]:
            if color[v] == -1:
                stack.append(v)
                if color[u] == 0:
                    color[v] = 1
                else:
                    color[v] = 0
            if color[u] == color[v]:flag = 0;break
    if flag:
        B = 0
        W = 0
        for c in color:
            if c == 1:
                B += 1
            else:W += 1
        ans = B*W-M
    else:
        ans = N*(N-1)//2-M
    
    print(ans)


if __name__ == "__main__":
    main()

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

def main():
        
    def bipartite_graph(edge,N,M):
        dist = [-1 for _ in range(N)]
        col = [0 for _ in range(N)]
        dist[0],col[0] = 0,1
        q = deque([(0,1)])
        while q:
            now,nc = q.popleft()
            for fol in edge[now]:
                if col[fol] == 0:
                    col[fol] = -1*nc
                    q.append((fol,-1*nc))
                elif col[fol] == nc:
                    return (N*(N-1))//2-M
        a = col.count(1)
        return a*(N-a)-M

    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)
        
    print(bipartite_graph(edge,N,M))
    
if __name__ == "__main__":
    main()

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


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


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

ok = False
tag = [-1] * n


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


dfs()

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

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

def dfs(G, v, cur):
    color[v] = cur;

    for next_v in G[v] :
        if not(color[next_v] == -1) :
            if color[next_v] == cur :
                return 0;
            continue;
        if not(dfs(G,next_v,1-cur)):
            return 0;
    return 1;

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

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

color = [-1]*n;

if dfs(G,0,0) :
    print(sum(color)*(n-sum(color))-m);
else :
    print(n*(n-1)//2-m);

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

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

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)

colors = [0]*n

ans = -m
if dfs(0,1):
  b = (sum(colors)+n)//2
  w = n-b
  ans += b*w
else:
  ans += n*(n-1)//2
print(ans)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(1000000)

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

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

flag = True
dist = [-1] * N

que = deque([])
for v in range(N):
    if dist[v] != -1:  
        continue
    dist[v] = 0
    que.append(v)
    while que:
        v = que.popleft()
        for nv in G[v]:
            if dist[nv] == -1:  
                dist[nv] = dist[v] + 1
                que.append(nv)
            else:  
                if dist[v] == dist[nv]:
                    flag = False
if flag:
    w = [i for i in dist if i % 2 == 0]
    b = [i for i in dist if i % 2 != 0]
    ans = len(w) * len(b) - M
else:
    ans = N * (N - 1) // 2 - M
print(ans)

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


def dfs(u, c):
    color[u] = c  
    for v in G[u]:  
        if color[v] != -1:  
            if color[v] == c:
                return False  
            else:
                continue
        else:  
            if not dfs(v, 1 - c):  
                return False
    return True



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

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

flag = True
for i in range(N):
    if color[i] == -1:
        if not dfs(i, 0):
            flag = False
            break
if flag:
    ans = color.count(1) * color.count(0) - M
else:
    ans = N * (N - 1) // 2 - M
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
import numpy as np 
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = map(lambda x: int(x)-1, input().split())
  g[u] += [v]
  g[v] += [u]

col = [0]*n 
def dfs(u, c):
  col[u] = c 
  for v in g[u]:
    if col[v] == c:
      return False
    if (col[v] == 0 and not dfs(v, -c)):
      return False

  return True


if dfs(0, 1):
  col = np.array(col)
  b = len(col[col==1])
  w = len(col) - b
  print(b*w-m)
else:
  print(n*(n-1)//2-m)

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
stack = [(1,1)]
color = [0]*(n+1)
flg = 0
while stack:
  x,c = stack.pop()
  color[x] = c
  for y in graph[x]:
    if color[y] == 0:
      stack.append((y,3-c))
    elif color[y] == color[x]:
      flg = 1
      break
  else:
    continue
  break
if flg:
  print(n*(n-1)//2-m)
else:
  print(color.count(1)*color.count(2)-m)

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

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

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

for i in range(m):
    b[a[i][0]-1].append(a[i][1]-1)
    b[a[i][1]-1].append(a[i][0]-1)

import collections
from collections import deque

INF = -10 ** 9
dis = [INF for i in range(n)]
def bfs(s):
    d = deque()
    d.append(s)
    dis[s]=0
    flag = True

    while len(d):
        x = d.popleft()

        for i in range(len(b[x])):
            y=b[x][i]
            if dis[y] == INF:
                d.append(y)
                dis[y]=dis[x]+1
            else:
                if dis[y]%2!=dis[x]%2:
                    continue
                else:
                    flag=False
    return flag
q=bfs(0)
if q:
    v=0
    w=0
    for i in range(n):
        if dis[i]%2==0:
            v+=1
        else:
            w+=1
    print(v*w-m)

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

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

def run():
  N, M = map(int, input().split())
  g = {}
  for m in range(M):
    A, B = map(int, input().split())
    g.setdefault(B, []).append(A)
    g.setdefault(A, []).append(B)
  visited = [0]*N
  visited[0] = 1
  def dfs(now):
    for nxt in g[now]:
      if visited[nxt-1] == 0:
        visited[nxt-1] = visited[now-1]*(-1)
        if not dfs(nxt):
          return False
      else:
        if visited[nxt-1] != visited[now-1]*(-1):
          return False
    return True
  if dfs(1):
    print(visited.count(1)*visited.count(-1)-M)
  else:
    print(N*(N-1)//2-M)
  
if __name__ == '__main__':
  run()

Solution (Python):
from collections import deque
n,m=map(int,input().split())
edges=[[] for _ in range(n)]
visited=[-1 for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  edges[a-1].append(b-1)
  edges[b-1].append(a-1)
def dfs(edges,visited):
  stack=deque([0])
  visited[0]=0
  while stack:
    x=stack.pop()
    for newx in edges[x]:
      if visited[newx]==visited[x]:
        return False,sum(visited)
      elif visited[newx]==-1:
        visited[newx]=(visited[x]+1)%2
        stack.append(newx)
  return True,sum(visited)
ok,b=dfs(edges,visited)
if ok:
  print(b*(n-b)-m)
else:
  print(n*(n-1)//2-m)

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    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)
    Col = [-1] * N
    q = deque()
    q.append((0, 0))
    bipartite = True
    while q:
        nnode, ncol = q.pop()
        if Col[nnode] == -1:
            Col[nnode] = ncol
            for e in Edge[nnode]: q.append((e, ncol ^ 1))
        else:
            if Col[nnode] != ncol:
                bipartite = False
                break
    
    if bipartite:
        zero, one = 0, 0
        for i, n in enumerate(Col):
            if n == 0: zero += 1
            else: one += 1
        print(zero * one - M)
    else:
        print(N * (N - 1) // 2 - M)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    """
    辺(a,b)を結べるかどうかは、(a,b)の距離が奇数長かどうかと等しい
    なぜなら、(a,b)が奇数長なら(a,b)の間の3-stepを1-stepで出来るような辺を張れるのでいずれ3-stepになる。
    
    1.二部グラフでないなら、奇数サイクルが1つ以上存在する
        ―奇数サイクルがあるなら、サイクル上のvを通るようなpath(s,t)が存在し、それが偶数長でも余計に奇数サイクルを通ることで奇数長のパスを見つける事ができる
    2.二部グラフならグループ1とグループ2の任意の点を結ぶパスは奇数長になり、同グループのパスは偶数長になる
    """
    N,M=MI()
    edge = [[]for _ in range(N)]
    for _ in range(M):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    
    group = [-1]*N
    group[0] = 0

    def is_bipartite():
        stack = [0]
        while stack:
            v = stack.pop()
            for to in edge[v]:
                if group[to]!=-1 and group[to]==group[v]:
                    return False
                if group[to]==-1:
                    stack.append(to)
                    group[to] = group[v]^1
        return True

    bipartite = is_bipartite()
    if bipartite:
        g1 = group.count(0)
        g2 = N-g1
        ans = g1*g2
    else:
        ans = N*(N-1)//2
    ans -= M
    print(ans)

                
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)


d = [10 ** 6 for _ in range(N + 1)]
d[1] = 0
Q = dq([1])
while len(Q):
  p = Q.popleft()
  for q in e[p]:
    if d[q] > d[p] + 1:
      Q.append(q)
      d[q] = d[p] + 1
c = [[0] * 2 for _ in range(N + 1)]
wh = 0
gr = 0
for x in range(1, N + 1):
  for y in e[x]:
    dy = d[y] % 2
    c[x][dy] = 1
  cc = (c[x][0] & c[x][1])
  wh += c[x][0]
  gr += cc

if gr:
  print(N * (N - 1) // 2 - M)
  exit(0)

res = 0
for x in range(1, N + 1):
  res += wh * c[x][1]

  

print(res - M)

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

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

g = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

import sys

sys.setrecursionlimit(10 ** 6)


class Tree:
    WHITE = 0
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v, w in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += w
                self.dfs(v)
                self.depth -= w

        self.colors[u] = self.BLACK

    def bipartite_graph(self, u, c):
        self.colors[u] = c
        for v in self.adj[u]:
            if self.colors[v] == c:
                return False
            if self.colors[v] == self.WHITE and not self.bipartite_graph(v, -c):
                return False

        return True


tree = Tree(g)
if tree.bipartite_graph(0, tree.GRAY):
    black = tree.colors.count(tree.GRAY)
    white = tree.colors.count(tree.BLACK)
    ans = black * white - m

else:
    ans = n * (n - 1) // 2 - m

print(ans)

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

def root(v):
    if v == par[v]:
        return v
    par[v] = root(par[v])
    return par[v]

def unite(u, v):
    u = root(u)
    v = root(v)
    if u == v:
        return
    if rank[u] < rank[v]:
        u, v = v, u
    par[v] = u
    if rank[u] == rank[v]:
        rank[u] += 1

def same(u, v):
    return root(u) == root(v)

N, M = map(int, input().split())
par = list(range(2 * N))
rank = [0] * (2 * N)
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b + N)
    unite(a + N, b)

if same(0, N):
    print(N * (N - 1) // 2 - M)
else:
    c = 0
    for i in range(N):
        c += same(0, i)
    print(c * (N - c) - M)

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

def is_bipartite(v, d):
    color[v] = d
    for u in E[v]:
        if color[u] == d:
            return False
        elif color[u] != -1:
            continue
        if not is_bipartite(u, (d + 1) % 2):
            return False
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
color = [-1] * N

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

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

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

N,M=map(int,input().split())
g = [[] for _ 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)

F = [-1 for _ in range(N)]
def dfs(s,f):
    global F
    global g
    F[s] = f
    for d in g[s]:
        if  F[d] == -1:
            if f == 1:
                if not dfs(d,0):
                    return False
            else:
                if not dfs(d,1):
                    return False
        else:
            if F[d] == f:
                return False
    return True

if dfs(0,0):
    f1 = F.count(1)
    f0 = F.count(0)
    print(f1*f0-M)
else:
    print(N*(N-1)//2 - M)

Solution (Python):
from collections import deque

def dfs():
    q = deque([])
    q.append(0)
    color[0] = 1
    
    while q:
        p = q.pop()
        for u in edge[p]:
            if color[u] == -1:
                color[u] = (color[p] + 1) % 2
                q.append(u)
            else:
                if color[u] == color[p]:
                    return False
    return True

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
color = [-1] * n

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


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

Solution (Python):
from collections import deque

def dfs():
    global color
    color = [-1] * n
    q = deque([])
    q.append(0)
    color[0] = 1
    
    while q:
        p = q.pop()
        for u in edge[p]:
            if color[u] == -1:
                color[u] = (color[p] + 1) % 2
                q.append(u)
            else:
                if color[u] == color[p]:
                    return False
    return True

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)


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

Solution (Python):
n,m = map(int, input().split())
e = [set() for _ in range(n)]
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    e[u].add(v)
    e[v].add(u)

def dfs():
    col = [-1]*n
    col[0] = 0
    q = [0]
    while len(q)>0:
        v = q.pop()
        c = col[v]
        for u in e[v]:
            if col[u]<0:
                col[u] = (c+1)%2
                q.append(u)
            else:
                if c==col[u]:
                    return False
    return True

if not dfs():
    print(n*(n-1)//2 - m)
    exit()

visited = [False]*n
visited[0] = True
num = [0,0]
q = [(0,0)]
while len(q)>0:
    u,d = q.pop()
    num[d%2] += 1
    for v in e[u]:
        if visited[v]:
            continue
        q.append((v,d+1))
        visited[v] = True

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

Solution (Python):
import sys
sys.setrecursionlimit(500*500)

def cal_bw(now, value, record, g):
  search_li = g[now]
  record[now] = value
  for s in search_li:
    if record[s] == value:
      return False
    if record[s] != -1:
      continue
    record = cal_bw(s, (value+1)>>1 == 0, record, g)
    if not record:
      return False
  return record

def run():
  N, M = map(int, input().split())
  g = {}
  for m in range(M):
    a, b = map(int, input().split())
    g.setdefault(a, []).append(b)
    g.setdefault(b, []).append(a)
  record = [-1]*(N+1)
  record = cal_bw(1, 0, record, g)
  
  if record:
    print(record.count(0)*record.count(1) - M)
  else:
    print(N*(N-1)//2 - M)
    
if __name__ == '__main__':
    run()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def is_biparty(g):
    u = list(g.keys())[0]
    s = [u]
    c = {}
    c[u] = True
    while s:
        u = s.pop()
        for v in g[u]:
            if v not in c:
                c[v] = not c[u]
                s.append(v)
            else:
                if c[v] == c[u]:
                    return False, None

    return True, c

@mt
def slv(N, M, AB):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    b, c = is_biparty(g)
    if b:
        d = Counter(c.values())
        return d[True] * d[False] - M
    else:
        return N * (N-1) // 2 - M


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
edges = [set() for _ in range(N)]
for _ in range(M):
    a, b = inpl()
    a -= 1
    b -= 1
    edges[a].add(b)
    edges[b].add(a)

L = [0] * 2
signs = [None] * N
pool = [(0,0)]
while pool:
    n, s = pool.pop()
    if signs[n] is None:
        signs[n] = s
        L[s] += 1
        for c in edges[n]:
            edges[c].remove(n)
            pool.append((c,1-s))
    elif signs[n] == s:
        continue
    else:
        ans = N*(N-1)//2 - M
        break
else:
    ans = L[0]*L[1] - M

print(ans)