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
input=sys.stdin.readline
n,m=map(int,input().split())
edge=[[] for i 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)
Chk=[0]*n
Odd=False
T=[0]
Chk[0]=1
while T:
  t=T.pop()
  for g in edge[t]:
    if not Chk[g]:
      Chk[g]=Chk[t]*(-1)
      T.append(g)
    elif Chk[g]*Chk[t]==1:
      Odd=True
if Odd:
  print(n*(n-1)//2-m)
else:
  c=Chk.count(1)
  print(c*(n-c)-m)

Solution (Python):
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  
rs = lambda: stdin.readline().rstrip()  

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


color = [None] * (N+1) 
color[1] = 0
stack = [1]
bool = True
while stack:
    node = stack.pop()
    for n in graph[node]:
        if color[n] == None:
            color[n] = 1 - color[node]
            stack.append(n)
        elif color[n] == color[node]:
            bool = False
        else:
            continue

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

Solution (Python):
def bipartite(g):
    s = [(0, 1)]
    c = [0] * n
    while s:
        v, color = s.pop()
        c[v] = color
        for node in g[v]:
            if c[node] == c[v]:
                return False, None
            if c[node] == 0:
                s.append((node, -color))
    return True, c

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)
b, colors = bipartite(g)
if b:
    x = colors.count(1)
    print(x * (n - x) - m)
else:
    print(n * (n - 1) // 2 - m)

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]
PATH = [[] for _ in range(N+1)]

for a, b in AB:
    PATH[a].append(b)
    PATH[b].append(a)

color = [None] * (N+1)
color[1] = 0
q = deque([1])

while q:
    x = q.popleft()
    for y in PATH[x]:
        if color[y] is None:
            color[y] = 1 - color[x]
            q.append(y)

bl = all([color[a] != color[b] for a, b in AB])

ans = 0
if bl:
    x = sum(color[1:])
    y = N - x
    ans = x * y - M
else:
    ans = (N * (N-1) // 2) - M

print(ans)

Solution (Python):
from collections import Counter
import sys


sys.setrecursionlimit(10 ** 6)


def dfs(x):
    res = True
    for e in edge[x]:
        if color[e] is None:
            color[e] = 0 if color[x] else 1
            res &= dfs(e)
        else:
            if color[e] == color[x]:
                res &= False
            else:
                res &= True
    return res


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)

color = [None] * N
color[0] = 0
isBin = dfs(0)

if isBin:
    C = Counter(color)
    print(C[0] * C[1] - M)
else:
    print(N * (N - 1) // 2 - M)

Solution (Python):
N,M = map(int,input().split())

adj = [list() for _ in range(N)]

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


res = 0

color = [None]*N

for x in range(N):
    if color[x] is not None:
        continue
    
    cnt = [0,1]
    stack = [x]
    color[x] = True
    flag = True
    while stack:
        v = stack.pop()
        c = not color[v]
        for u in adj[v]:
            if color[u] is None:
                stack.append(u)
                color[u] = c
                cnt[c] += 1
            elif flag:
                flag = c == color[u]

    if flag:
        res += cnt[0]*cnt[1]
    else:
        cnt = sum(cnt)
        res += cnt*(cnt-1)//2

print(res-M)

Solution (Python):
import sys
sys.setrecursionlimit(pow(10, 7))

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

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

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

if dfs(v=0, c=0):
	k = sum(color)
	print(k*(n-k) - m)
else:
	print(n*(n-1)//2 - m)

Solution (Python):
import sys
sys.setrecursionlimit(pow(10, 7)) 



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


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
if dfs(0, 1):
    print(len([i for i in colors if i == -1])*len([j for j in colors if j == 1]) - M)
else:
    print(N * (N-1) // 2 - M)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
G = {}
for _ in range(M):
    A,B = map(int,input().split())
    if A not in G:
        G[A] = []
    G[A].append(B)
    if B not in G:
        G[B] = []
    G[B].append(A)
color = [-1 for _ in range(N+1)]
que = deque([1])
color[1] = 0
flag = 0
while que:
    cur = que.popleft()
    for x in G[cur]:
        if color[x]<0:
            color[x] = (color[cur]+1)%2
            que.append(x)
        else:
            if color[x]==(color[cur]+1)%2:continue
            else:
                flag=1
                break
    if flag==1:break
if flag==0:
    n = color.count(0)
    m = color.count(1)
    cnt = n*m-M
else:
    cnt = (N*(N-1))//2-M
print(cnt)

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

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

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

colors = [0 for i in range(N + 1)]
def dfs(v, color):
    colors[v] = color
    for t in edge[v]:
        if colors[t] == color:
            return False
        if colors[t] == 0 and not dfs(t, -color):
            return False
    return True

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

if is_bipartite():
    
    cB, cW = 0, 0
    for c in colors[1:]:
        if c == 1:
            cB += 1
        else:
            cW += 1
    print(cB * cW - M)
else:
    print(N * (N - 1) // 2 - M)

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

    
    col=[-1]*n
    col[0]=0
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv in E[v]:
            if(col[v]==col[nv]): 
                print(n*(n-1)//2-m)
                return
            elif(col[nv]!=-1 and col[nv]^col[v]): continue
            col[nv]=1-col[v]
            Q.append(nv)

    
    even=col.count(0)
    odd=col.count(1)
    print(even*odd-m)
resolve()

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

    
    col=[-1]*n
    col[0]=0
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv in E[v]:
            if(col[v]==col[nv]): 
                print(n*(n-1)//2-m)
                return
            elif(col[nv]!=-1 and col[nv]^col[v]): continue
            col[nv]=1-col[v]
            Q.append(nv)

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

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

Solution (Python):
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    [g[b-1].append(a-1) for a,b in ab]
    ans=[None]*n
    ans[0]=0
    temp=[0]
    while temp:
        i=temp.pop()
        for j in g[i]:
            if ans[j]==None:
                ans[j]=ans[i]^True
                temp.append(j)
            else:
                if ans[i]^ans[j]==0:
                    print(n*(n-1)//2-m)
                    return 0
    print(ans.count(0)*ans.count(1)-m)
main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
class BinPartite:
    def __init__(self, N, es):
        self.colors = [0 for i in range(N)]
        self.es = es

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

    def color_cnt(self, color):
        return self.colors.count(color)

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


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

Bp = BinPartite(N, e_list)
if Bp.is_bipartite():
    b = Bp.color_cnt(1)
    w = Bp.color_cnt(-1)
    print(b*w-M)
else:
    print(N*(N-1)//2 - M)

Solution (Python):
N,M = map(int,input().split())
e_list = [[] for i in range(N)]
for i in range(M):
    a,b = map(lambda x:int(x)-1, input().split())
    e_list[a].append(b)
    e_list[b].append(a)
bin_or_not = True
ans = (N-1)*N//2 - M
w_or_b = [-1]*N
stack = [0]
w_or_b[0] = 0
while stack:
    x = stack.pop()
    for i in e_list[x]:
        if w_or_b[i] >= 0:
            bin_or_not = w_or_b[x]^w_or_b[i]
        else:
            w_or_b[i] = (w_or_b[x] + 1)%2
            stack.append(i)
        if not bin_or_not:
            break
    if not bin_or_not:
        break
if bin_or_not:
    w =  w_or_b.count(0)
    b = w_or_b.count(1)
    ans = w*b - M
print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([random.randint(0,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

n,m=LI()
g,c=GI(n,m)

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

def IsBipartite():
    q=[0]
    v[0]=0
    while q:
        c=q.pop()
        for n in g[c]:
            if v[n]==-1:
                q.append(n)
                v[n]=1-v[c]
            elif v[n]==v[c]:
                return False
    return True

if IsBipartite():
    ans=sum(v)*(n-sum(v))-m
else:
    ans=n*(n-1)//2-m
print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([random.randint(0,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

n,m=LI()
g,c=GI(n,m)

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

def bfs(x):
    q=[x]
    v[x]=0
    while q:
        c=q.pop()
        for n in g[c]:
            if v[n]==-1:
                q.append(n)
                v[n]=1-v[c]

bfs(0)

flg=True
for i in range(n):
    MM=max([v[nb] for nb in g[i]])
    mm=min([v[nb] for nb in g[i]])
    if MM==mm and MM!=v[i]:
        continue
    else:
        flg=False
        break


if flg:
    ans=sum(v)*(n-sum(v))-m
else:
    ans=n*(n-1)//2-m
print(ans)

Solution (Python):
from collections import deque

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

d = [None] * N

dic = {}

for i in range(M):

    a,b = map(int,input().split())
    a-=1
    b-=1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

q = deque([0])
d[0] = 0
flag = False

while len(q) > 0:

    now = q.popleft()

    for i in dic[now]:

        if d[i] == None:
            d[i] = (d[now] + 1) % 2
            q.append(i)


        elif d[i] != (d[now] + 1) % 2:
            flag = True
            break

if flag:
    print (N * (N-1) // 2 - M)

else:
    odd = 0
    even = 0

    for i in d:
        if i == 0:
            even += 1
        else:
            odd += 1

    
    print (odd * even - M)

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

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



visited = [-1] * N


def is_bipartite(v=0, color=0):
    flag = True
    visited[v] = color
    for nv in to[v]:
        ncolor = (color + 1) % 2
        if visited[nv] == -1:
            flag &= is_bipartite(nv, ncolor)
        elif visited[nv] != ncolor:
            return False
    return flag

if is_bipartite():
    a = sum(visited)
    b = N - a
    ans = a*b - M
else:
    ans = N*(N-1)//2 - M

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(100000)
from collections import defaultdict

G = defaultdict(list)


N, M = map(int, input().split())
visited = [[False for i in range(N)] for j in range(5)]
for i in range(M):
    v,u = map(int, input().split())
    G[v-1].append(u-1)
    G[u-1].append(v-1)


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

def dfs(pos, color):
    global COLOR
    COLOR[pos] = color
    ans = True
    for to in G[pos]:
        if COLOR[to] == color:
            return False
        elif COLOR[to] == 0:
            ans &= dfs(to, -color)
    return ans

if dfs(0, 1):
    count = 0
    for i in COLOR:
        if i == -1:
            count += 1
    another = N-count
    print(count*another-M)
else:
    
    print(N*(N-1)//2-M)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    bfs = [0]*n
    bfs[0] = 1
    q = deque([0])
    while q:
        x = q.popleft()
        if bfs[x] == 1:
            nb = 2
        elif bfs[x] == 2:
            nb = 1
        else:
            nb = 3
        for y in v[x]:
            if bfs[y]^nb:
                bfs[y] |= nb
                q.append(y)
    ans = 0
    f = [0]*3
    for b in bfs:
        if b == 1:
            ans += f[0]
            f[1] += 1
            f[2] += 1
        elif b == 2:
            ans += f[1]
            f[0] += 1
            f[2] += 1
        else:
            ans += f[2]
            f[0] += 1
            f[1] += 1
            f[2] += 1
    print(ans-m)
    return



if __name__ == "__main__":
    solve()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def bipartite_or_not(G, s=0):
    n = len(G)
    global color
    color = [0] * n
    color[s] = 1
    dq = deque([s])
    while dq:
        u = dq.popleft()
        for v in G[u]:
            if color[v] == 0:
                color[v] = -color[u]
                dq += [v]
            else:
                if color[u] == color[v]:
                    return False
    return True


n, m = LI()
G = [[] for _ in range(n)]
for a, b in LIR(m):
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


if bipartite_or_not(G):
    print(color.count(1) * color.count(-1) - m)
else:
    print(n * (n - 1) // 2 - m)

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

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

ok = True
color = [-1]*N
q = [0]
color[0] = 0
c = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np in graph[p]:
            if color[np] == -1:
                color[np] = c
                qq.append(np)
            elif color[np] != c:
                ok = False
                break
    if not ok: break
    q = qq

if not ok:
    ans = N*(N-1)//2 - M
else:
    s = sum(color)
    ans = s*(N-s) - M
print(ans)

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

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

"""
距離が３つ離れたやつを縮めて１にする処理。
・与えられたグラフが２部グラフの場合、あるノードから奇数個辺をたどった先は違う色で、偶数個辺をたどれば同じ色なので、
３→１変えてそこから先に２進んだ先とつないでも別の色としかつながることができない。異なる色どうしは全てつながることができる
・２部グラフでない場合、あるノードからあるノードに行くのに奇数回移動していく道筋と偶数回移動していく道筋が存在することになるから、
そこを起点にすれば最終的に全てのノードが繋がる
"""

es = defaultdict(list)

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


color = [0] * N

def dfs(a, c):
    color[a] = c
    for b in es[a]:
        if color[b] == c:
            return False
        if color[b] == 0 and not dfs(b, -c):
            return False

    return True



if dfs(0, 1):
    tmp = color.count(1)

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

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

n, m = map(int, input().split())
color = [-1]*n
edge = [list() 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)

flag = True


def dfs(i, pre, c):
    if color[i] == c:
        return
    elif color[i] == 1-c:
        global flag
        flag = False
        return
    color[i] = c
    for v in edge[i]:
        dfs(v, i, 1-c)


dfs(0, -1, 0)



if flag:
    print(color.count(1)*color.count(0)-m)
else:
    print(math.floor(n*(n-1)/2-m))

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

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





def bipartite():
    dist = [INF] * N
    que = deque([0])
    dist[0] = 0
    while que:
        v = que.pop()
        d = dist[v]
        for u in graph[v]:
            if dist[u] < INF and dist[u] % 2 == d % 2:
                
                return 0, 0
            if dist[u] == INF:
                que.appendleft(u)
                dist[u] = d + 1
    evens = len([v for v in range(N) if dist[v] % 2 == 0])
    odds = len([v for v in range(N) if dist[v] % 2 == 1])
    return evens, odds


evens, odds = bipartite()
if evens == odds == 0:
    
    count = N * (N - 1) // 2
else:
    count = evens * odds
ans = count - M
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
AB = [LIST() for _ in range(M)]

graph = defaultdict(list)
for A, B in AB:
	graph[A-1].append(B-1)
	graph[B-1].append(A-1)


color = [0] *  N
color[0] = 1
if N == 3:
	print(0)
	sys.exit()
	
def DFS(node):
	if not 0 in color:  
			w = color.count(1)
			print(w*(N-w)-M)
			sys.exit()
	for i in graph[node]:
		if not color[i]:
			color[i] = color[node] * (-1)
			DFS(i)
		else:
			if color[i] == color[node]:  
				print(N*(N-1)//2-M)
				sys.exit()
		
DFS(0)

Solution (Python):
N, M = map(int, input().split())
v = [set() for _ in range(N)]
for _ in range(M) :
    A, B = map(int, input().split())
    v[A-1].add(B-1)
    v[B-1].add(A-1)
    
visited = [[False] * N for _ in range(2)]
visited[0][0] = True

q = [(0, 0)]
while q :
    parity, cur = q.pop()
    parity ^= 1
    for nex in v[cur] :
        if visited[parity][nex] :
            continue
        visited[parity][nex] = True
        q.append((parity, nex))

o, e = 0, 0
for i in range(N) :
    if visited[0][i] and not visited[1][i] :
        e += 1
    elif not visited[0][i] and visited[1][i] :
        o += 1

print((N * (N - 1) - o * (o - 1) - e * (e - 1)) // 2 - M)

Solution (Python):
from collections import deque

N, M = map(int,input().split())
side = [[]for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    side[b-1].append(a-1)
node = [-1]*N
node[0] = 1
queue = deque([0])
while queue:
    q = queue.popleft()
    for i in side[q]:
        if node[i] == -1:
            node[i] = (node[q]+1)%2
            queue.append(i)
        elif node[i] == node[q]:
            print((N*(N-1))//2 - M)
            exit()
zerone = [0, 0]
for i in node:
    zerone[i] += 1
print(zerone[0] * zerone[1] - M)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import deque

edges = []
col = []

def is_bipartite():
    global col
    col = [-1 for _ in range(len(edges))]
    col[0] = 0
    que = deque([0])
    while len(que) != 0:
        q = que.popleft()
        for to in edges[q]:
            if col[to] == -1:
                col[to] = col[q] ^ 1
                que.append(to)
            else:
                if col[q] ^ 1 != col[to]:
                    return False
    return True


def main():
    global edges
    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)
    
    if is_bipartite():
        b = sum(col)
        print(b * (n - b) - m)
    else:
        
        print(n * (n-1) // 2 - m)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

g = [set() for _ in range(n)]
for _ in range(m):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add(b)
    g[b].add(a)

par = [-1] * n


def is_bipartite():
    dq = deque()
    dq.append(0)
    par[0] = 0

    while dq:
        v = dq.popleft()
        for u in g[v]:
            if par[u] != -1:
                if par[u] == (par[v] ^ 1):
                    continue
                else:
                    return False
            else:
                par[u] = (par[v] ^ 1)
                dq.append(u)
    return True


if is_bipartite():
    
    evens = par.count(0)
    odds = n - evens
    print(odds * evens - m)
else:
    
    print(n * (n - 1) // 2 - m)

Solution (Python):
def resolve():
    N,M = map(int,input().split())
    import collections
    n_dict = collections.defaultdict(list)
    for _ in range(M):
        a,b = map(int,input().split())
        n_dict[a].append(b)
        n_dict[b].append(a)

    color = [-1 for _ in range(N)]
    flag = False
    d = collections.deque()
    d.append((1,0))
    while d:
        n,c = d.pop()
        color[n-1] = c^1
        for a in n_dict[n]:
            if color[a-1] == -1:
                d.append((a,c^1))
            elif color[a-1] == c^1:
                flag = True

    cumsum = [0,0]
    for i in range(N):
        cumsum[color[i]] += 1
    ans = 0
    if flag:
        ans = cumsum[0] + cumsum[1]
        print(ans * (ans-1)//2 - M)
    else:
        print(cumsum[0] * cumsum[1] - M)    
resolve()

Solution (Python):
n,m = map(int,input().split())
g = [list() for _ in range(n+1)]
for _ in range(m):
  a,b = map(int,input().split())
  g[a].append(b)
  g[b].append(a)
bw = [-1]*(n+1)
bw[1] = 0
q = [1]
f = 0
while q:
  v = q.pop()
  for x in g[v]:
    if bw[x] >= 0:
      if bw[x] == bw[v]:
        f = 1
        break
      continue
    else:
      bw[x] = 1-bw[v]
      q.append(x)
if f:
  print(n*(n-1)//2 - m)
else:
  b = sum(bw)+1
  w = n - b
  print(b*w-m)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict
import queue


def getlist():
	return list(map(int, input().split()))
INF = float("inf")

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(0)
		self.W = [INF] * N 
		self.visit = ["No"] * N 
		self.visit[s] = "Yes"
		self.W[s] = 0
		self.judge = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.W[i] = self.W[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"
				
				else:
					if (self.W[i] - self.W[v] - 1) % 2 == 1:
						self.judge = "No"
						break


def main():
	N, M = getlist()
	G = Graph()
	for i in range(M):
		a, b = getlist()
		G.add_edge(a - 1, b - 1)
		G.add_edge(b - 1, a - 1)
	BF = BFS(G, 0, N)
	if BF.judge == "No":
		print(int(N * (N - 1) // 2) - M)
	else:
		even = 0
		odd = 0
		for i in BF.W:
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
		print(even * odd - M)

if __name__ == '__main__':
	main()

Solution (Python):
n,m,*t=map(int,open(0).read().split())
e=[[]for _ in'_'*n]
for a,b in zip(*[iter(t)]*2):
  e[a-1]+=b-1,
  e[b-1]+=a-1,
s=[0]
f=s+[-1]*~-n
while s:
  v=s.pop()
  p=f[v]^1
  for w in e[v]:
    if-1<f[w]:
      if f[w]!=p:
        print(n*~-n//2-m)
        exit()
    else:
      f[w]=p
      s+=w,
r=sum(f)
print(r*(n-r)-m)

Solution (Python):
n,m,*t=map(int,open(0).read().split());e=[[]for _ in'_'*n]
for a,b in zip(*[iter(t)]*2):e[a-1]+=b-1,;e[b-1]+=a-1,
s=[0];f=s+[-1]*~-n
while s:
 v=s.pop();p=f[v]^1
 for w in e[v]:
  if-1<f[w]:
   if f[w]^p:print(n*~-n//2-m);exit()
  else:f[w]=p;s+=w,
r=sum(f);print(r*(n-r)-m)