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):
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):


import sys

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 list4d(a, b, c, d, e): return [[[[e] * d for j in range(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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
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 = tuple([] for i in range(N))
for i in range(M):
    a, b = MAP()
    a -= 1
    b -= 1
    nodes[a].append(b)
    nodes[b].append(a)


color = [-1] * N
def check(u):
    stack = [(u, -1, 0)]
    while stack:
        u, prev, c = stack.pop()
        if color[u] == -1:
            color[u] = c
        else:
            if color[u] == c:
                continue
            else:
                return False
        for v in nodes[u]:
            if v != prev:
                stack.append((v, u, 1-c))
    return True

if check(0):
    a = sum(color)
    b = N - a
    ans = a*b - M
else:
    ans = N*(N-1) // 2 - M
print(ans)

Solution (Python):


import sys

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 list4d(a, b, c, d, e): return [[[[e] * d for j in range(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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
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 = tuple([] for i in range(N))
for i in range(M):
    a, b = MAP()
    a -= 1
    b -= 1
    nodes[a].append(b)
    nodes[b].append(a)


color = [-1] * N
def rec(u, prev, c):
    if color[u] == -1:
        color[u] = c
    else:
        if color[u] == c:
            return True
        else:
            return False
    for v in nodes[u]:
        if v != prev:
            if not rec(v, u, 1-c):
                return False
    return True

if rec(0, -1, 0):
    a = sum(color)
    b = N - a
    ans = a*b - M
else:
    ans = N*(N-1) // 2 - M
print(ans)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
def is_bipartite(G):
    n = len(G)
    color = [-1]*n
    que = deque([0])
    color[0] = 0
    while que:
        v = que.pop()
        c = color[v]
        for nv in G[v]:
            if color[nv]<0:
                color[nv] = 1-c
                que.append(nv)
            elif color[nv] == c:
                return False
    return color
color = is_bipartite(G)
if color:
    a = color.count(0)
    b = N-a
    print(a*b-M)
else:
    print(N*(N-1)//2-M)

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

N, M = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]
G = [[] for _ in range(N+1)]
for a,b in AB:  
  G[a].append(b)
  G[b].append(a)
color = [None]*(N+1)  
color[1] = 0
q = [1]

while q:
  x = q.pop()
  for y in G[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)      

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

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

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

def dfs(v, c):
  color[v] = c
  for e in G[v]:
    if color[e] == None:
      color[e] = 1 - color[v]      
      dfs(e, c^1) 
dfs(1, 0)      
bl = all(color[a] != color[b] for a, b in AB)      

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

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

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

def dfs(v, c):
  color[v] = c
  for e in G[v]:
    if color[e] == None:
      color[e] = 1 - color[v]
      dfs(e, c^1)
dfs(1, 0)      
bl = all(color[a] != color[b] for a, b in AB)      

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

Solution (Python):

from collections import deque
import sys
input = sys.stdin.readline
def isbipart(n,graph):  
  colors = [0 for i in range(n)]
  stack = deque([(0,1)])
  while stack:
    v,color = stack.pop()
    colors[v] = color
    for to in graph[v]:
      if colors[to] == color:
        return False
      if colors[to] == 0:
        stack.append((to,-color))
  return colors

def solve():
  n,m  =(int(i) for i in input().split())
  graph = [[] for _ in range(n)]
  for i in range(m):
    a,b = (int(i) for i in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
  colors = isbipart(n,graph)
  if colors:
    b = colors.count(1)
    w = n-b
    print(b*w-m)
  else:
    print(n*(n-1)//2-m)
solve()

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

N, M = map(int, input().split())
AB = [list(map(int, input().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)

colors = [None] * N

colors[0] = 0
que = [0]
while que:
    x = que.pop()
    for y in graph[x]:
        if colors[y] == None:
            colors[y] = 1 - colors[x]
            que.append(y)

is_bg = all(colors[a-1] != colors[b-1] for a, b in AB)

if is_bg:
    
    x = sum(colors)
    y = N - x
    answer = x*y - M
else:
    
    answer = N*(N-1)//2 - M

print(answer)

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
AB = [list(map(int, input().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)


colors = [None] * N
colors[0] = 0
q = [0]
while q:
    x = q.pop()
    for y in graph[x]:
        if colors[y] is None:
            colors[y] = 1 - colors[x]
            q.append(y)


is_bg = all(colors[a-1] != colors[b-1] for a, b in AB)

if is_bg:
    
    x = sum(colors)
    y = N - x
    answer = x*y - M
else:
    
    answer = N*(N-1)//2 - M

print(answer)

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

N, M = map(int, input().split())
AB = [list(map(int, input().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)


color = [None] * N
color[0] = 0
q = [0]
while q:
    x = q.pop()
    for y in graph[x]:
        if color[y] is None:
            color[y] = 1 - color[x]
            q.append(y)


is_bg = all(color[a-1] != color[b-1] for a, b in AB)

if is_bg:
    
    x = sum(color)
    y = N - x
    answer = x*y - M
else:
    
    answer = N*(N-1)//2 - M

print(answer)

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

n,m=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(m)]
edge=[[] for i in range(n+1)]
for a,b in ab:
    edge[a].append(b)
    edge[b].append(a)
    
color=[None]*(n+1)
color[1]=0
q=[1]

while q:
    x=q.pop()
    for j in edge[x]:
        if color[j] is None:
            color[j]=1-color[x]
            q.append(j)
bl = all(color[a]!=color[b] for a,b in ab)

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(1000000)

global color 
global adlist

def make_adlist(N, AB):
  global adlist
  for a, b in AB:
    adlist[a] += [b]
    adlist[b] += [a]

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

def main():
  global color 
  global adlist
  N, M = map(int, input().split())
  AB = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
  color = [0 for _ in range(N)]
  adlist = [[] for _ in range(N)]
  make_adlist(N, AB)
  if dfs(0, 1):
    B = color.count(-1)
    W = color.count(1)
    print(B*W-M)
  else:
    print(N*(N-1)//2-M)

if __name__ == "__main__":
  main()

Solution (Python):
import sys
input = sys.stdin.readline
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 = [None]*n
flag = True
def dfs(cur, c):
    global flag
    if color[cur] is not None:
        if color[cur] != c:
            flag = False
        return
    color[cur] = c
    for to in G[cur]:
        dfs(to, c^1)

dfs(0, 0)

if flag:
    a = sum(color)
    b = n-a
    ans = a*b-m
else:
    ans = n*(n-1)//2 - m
print(ans)

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

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

seen = [0] * (N+1)
que = deque()
que.append(1)
seen[1] = 1
finish = 0
flag = 0
cnt = 1
while que:
    if finish == 1:
        flag = 1
        break
    v = que.pop()
    for u in adj[v]:
        if seen[u] == 0:
            que.append(u)
            seen[u] = seen[v] * -1
            if seen[u] == 1:
                cnt += 1
        else:
            if seen[u] == seen[v]:
                finish = 1
                break

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

Solution (Python):
from collections import deque


def is_bipartite_graph(graph):
    """二部グラフかどうか判定し、黒色白色で塗り分けるときのそれぞれの頂点の個数を返す
    二部グラフでないときは(-1, -1)を返す
    """
    n = len(graph)
    visited = [-1] * n
    visited[0] = 0
    q = deque([0])
    while q:
        pos = q.pop()
        for next_pos in graph[pos]:
            if visited[next_pos] >= 0:
                if visited[next_pos] != visited[pos]:
                    continue
                else:
                    return -1, -1
            visited[next_pos] = visited[pos] ^ 1
            q.append(next_pos)
    cnt_0 = 0
    cnt_1 = 0
    for i in range(n):
        if visited[i]:
            cnt_1 += 1
        else:
            cnt_0 += 1
            
    return cnt_0, cnt_1
  
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

cnt_0, cnt_1 = is_bipartite_graph(graph)


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

else:
    ans = cnt_0 * cnt_1 - m
print(ans)

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

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

    for i in a[v]:
        if color[i] != -1:
            if color[i] == c:return False
            continue
        if dfs(i,1-c) == False:return False

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

for i in range(m):
    x,y= map(int,input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)
if dfs(0,0) == False:
    print(n*(n-1)//2-m)
else:print(color.count(0) * color.count(1) -m)

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect

import math
import heapq
from itertools import combinations, permutations

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

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

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

que = deque([])
que.append(0)
graph2[0] = 0
nibu = 1

num01 = dict()
num01[0] = 1
num01[1] = 0

while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if graph2[edge] == -1:
			graph2[edge] = (graph2[node] + 1) % 2
			que.append(edge)
			num01[graph2[edge]] += 1
		elif graph2[node] == graph2[edge]:
			nibu = 0

if nibu == 0:
	print(N*(N-1)//2 - M)
else:
	print(num01[0]*num01[1] - M)

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

Solution (Python):
n, m = map(int, input().split())
g = [[] for _ 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)

visit = [-1]*n
from collections import deque
s = deque()
s.append(0)
visit[0] = 0
flag = 0
while s:
  x = s.pop()
  for new_x in g[x]:
    if visit[new_x] == -1:
      visit[new_x] = (visit[x]+1)% 2
      s.append(new_x)
    elif visit[new_x] == visit[x]:
      flag = 1
      break
    else:
      continue
if flag == 0:
  print(sum(visit)*(n-sum(visit))-m)
else:
  print(n*(n-1)//2-m)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
E=[[]for _ in'_'*-~N]
for _ in'_'*M:
	a,b=map(int,input().split())
	E[a]+=[b]
	E[b]+=[a]
V=[0]*-~N
def f(i,x):
	if V[i]:
		return V[i]==x
	V[i]=x
	r=1
	for j in E[i]:
		r*=f(j,-x)
	return r
if f(1,1):
	print(V.count(1)*V.count(-1)-M)
else:
	print(N*~-N//2-M)

Solution (Python):
from collections import deque

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

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

dq = deque()
dq.append(0)

p = [None] * n
p[0] = 0

is_bipartite = True
while dq:
    v = dq.popleft()
    for u in e[v]:
        if p[u] is None:
            p[u] = 1 ^ p[v]
            dq.append(u)
        elif p[u] == p[v]:
            is_bipartite = False
            break
        else:
            
            pass

if is_bipartite:
    
    sp = sum(p)
    print(sp * (n - sp) - 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())

AB = [[int(x) for x in input().split()] for _ in range(M)]

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


color = [None] * (N+1)
color[1] = 0
q = [1]
while q:
    x = q.pop()
    for y in graph[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)

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

print(answer)

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

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

AB = [[int(x) for x in input().split()] for _ in range(M)]

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


color = [None] * (N+1)
color[1] = 0
q = [1]
while q:
    x = q.pop()
    for y in graph[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)

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

print(answer)

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

n, m = map(int, (input().split()))
dic = defaultdict(list)
seen = [-1] * (n+1)

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


def dfs(v, todo, color):
    if seen[v] == color:  
        return
    elif seen[v] == 1-color:  
        ans = 0.5 * n * (n-1) - m
        print(int(ans))
        sys.exit()

    seen[v] = color
    for new_v in todo:
        new_todo = dic[new_v]
        dfs(new_v, new_todo, 1-color)


dfs(1, dic[1], 0)
black = seen.count(0)
white = seen.count(1)
ans = black * white - m

print(int(ans))

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

n, m = map(int, (input().split()))
dic = defaultdict(list)
seen = [-1] * (n+1)

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


def dfs(v, todo, color):
    if seen[v] == color:  
        return
    elif seen[v] == 1-color:  
        global odd_cycle
        odd_cycle = True
        return

    seen[v] = color
    for new_v in todo:
        new_todo = dic[new_v]
        dfs(new_v, new_todo, 1-color)


odd_cycle = False
dfs(1, dic[1], 0)
if odd_cycle:
    ans = 0.5 * n * (n-1) - m
else:
    black = seen.count(0)
    white = seen.count(1)
    ans = black * white - m

print(int(ans))

Solution (Python):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*M]

E = [[] for _ in [0]*N]
for u,v in AB:
    E[u-1].append(v-1)
    E[v-1].append(u-1)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

d = dist_bfs(N,E,0)

co = sum(c%2 for c in d)
ce = N - co
check = False
for a,b in AB:
    a-=1
    b-=1
    if (d[a]+d[b])%2==0:
        check = True
        break
if check:
    ans = N*(N-1)//2 - M
else:
    ans = co*ce - M
print(ans)

Solution (Python):
N, M = map(int, input().split())
A, B = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)



G = [set() for _ in range(N + 1)]
for x, y in zip(A, B):
    G[x].add(y)
    G[y].add(x)
dp = [0 for _ in range(N + 1)]
q = []
q.append(1)
dp[1] = 1
is_bi = True
while q:
    i = q.pop()
    for j in G[i]:
        if dp[j] == 0:
            dp[j] = -dp[i]
            q.append(j)
        else:
            is_bi &= dp[j] == -dp[i]
ans = (
    sum(x == 1 for x in dp) * sum(x == -1 for x in dp) - M if is_bi else
    N * (N - 1) // 2 - M
)

print(ans)

Solution (Python):
class UnionFindTree():
    def __init__(self, N):
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(len(self.__parent_of)):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        adj[A-1].add(B-1)
        adj[B-1].add(A-1)
    uft = UnionFindTree(N)
    for i in range(N):
        adji = list(adj[i])
        x = adji[0]
        for y in adji[1:]:
            uft.unite(x, y)
    groups = uft.groups()
    if len(groups) == 1:
        print(N * (N-1) // 2 - M)
    else:
        print(len(groups[0]) * len(groups[1]) - M)


if __name__ == "__main__":
    main()

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

graph = [[] for _ in range(N)]
for x, y in edges:
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)

def dfs(s, c):
    q = deque()
    q.append(s)
    visited[s] = True
    color[s] = c
    
    while len(q) > 0:
        v = q.pop()
        for i in graph[v]:
            if visited[i] and color[i] == color[v]:
                return False
            
            if not visited[i]:
                visited[i] = True
                color[i] = -color[v]
                q.append(i)
                
    return True

visited = [False] * N
color = [0] * N

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

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

graph = [[] for _ in range(N)]
for x, y in edges:
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from operator import mul
from functools import reduce

def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


def dfs(v, cur):
    color[v] = cur
    
    for next_v in Graph[v]:
        if color[next_v] != -1:
            if color[next_v] != cur:
                continue
            else:
                return False
        elif not dfs(next_v, 1-cur):
            return False
    return True
        


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

for i in AB:
    Graph[i[0]-1].append(i[1]-1)
    Graph[i[1]-1].append(i[0]-1)

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
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, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

col = [-1] * N


def dfs(u, p, k):
    if col[u] != -1:
        if col[u] == k:
            return
        else:
            print(N * (N - 1) // 2 - M)
            exit()
    col[u] = k
    for w in G[u]:
        if w == p:
            continue
        dfs(w, u, k ^ 1)


dfs(0, -1, 0)
n, m = 0, 0
for i in range(N):
    if col[i] == 1:
        n += 1
    else:
        m += 1

print(n * m - M)

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 = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
G = defaultdict(set)
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 for i in range(len(G))]
color[0]=1

def Isbipartite(G):
    """
    color = [[0] for i in range(len(G))]
    color[0]=1
    """
    que=deque([0])
    bipartite = True
    while 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
    return bipartite


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

Solution (Python):
from collections import defaultdict, deque

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

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


colors = [0]*(N+1)

def dfs():
    que = deque([(1, 1)])

    while len(que):
        v, color = que.popleft()
        colors[v] = color
        for to in list(dic[v]):
            if (color == colors[to]):
                return False
            if (colors[to] == 0):
                que.append((to, -color))
                
    return True


flag = dfs()
b = colors.count(1)

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

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

Solution (Python):
def bipartite():
    color = {v: None for v in V}
    stack = [(V[0], 0)]
    parts = {0: [], 1:[]}
    while stack:
        v, c = stack.pop()
        if color[v] is not None: 
            continue
        color[v] = c
        parts[c].append(v)
        for u in E[v]:
            if color[u] is None: 
                stack.append((u, c^1)) 
            elif color[u] != c: 
                continue
            else: 
                return (None, None)
    return (parts[0], parts[1])
            
N, M = map(int, input().split())
V = range(1, N+1)
E = {v: [] for v in V}
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
p1, p2 = bipartite()
if p1 is None:
    print(N * (N-1) // 2 - M)
else:
    print(len(p1) * len(p2) - M)

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

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

colors = [None]*N
def dfs(curr, c):
    colors[curr] = c
    for node in edges[curr]:
        if colors[node] == colors[curr]:
            return False
        if colors[node] is None and not dfs(node, not c):
            return False
    return True

if not dfs(0, True):
    print((N*(N-1))//2 - M)
else:
    nw = sum(colors)
    print(nw*(N-nw)-sum([colors[a-1]^colors[b-1] for a, b in AB]))

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

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

colors = [0]*N
def dfs(curr, c):
    colors[curr] = c
    for node in edges[curr]:
        if colors[node] == colors[curr]:
            return False
        if colors[node]== 0 and not dfs(node, -c):
            return False
    return True

if not dfs(0, 1):
    print((N*(N-1))//2 - M)
else:
    WH = [c==1 for c in colors]
    nw = sum(WH)
    print(nw*(N-nw)-sum([WH[a-1]^WH[b-1] for a, b in AB]))

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

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
parity = [-1 for _ in range(n)]
valid = True

def dfs(x):
	global valid
	p = parity[x]
	for v in adj[x]:
		if parity[v] < 0:
			parity[v] = 1^p
			dfs(v)
		elif parity[v] == p:
			valid = False
			return
	return

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

parity[0] = 0
dfs(0)
if not valid:
	print((n*(n-1)//2) - m)
else:
	o = sum(parity)
	print(o*(n-o) - m)

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

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
parity = [-1 for _ in range(n)]
valid = True

def dfs(x):
	global valid
	p = parity[x]
	for v in adj[x]:
		if parity[v] < 0:
			parity[v] = 1^p
			dfs(v)
		elif parity[v] == p:
			valid = False
			return
	return

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

parity[0] = 0
dfs(0)
if not valid:
	print((n*(n-1)//2) - m)
else:
	o = sum(parity)
	print((n*(n-1)//2) - m - (o*(o-1)//2) - ((n-o)*(n-o-1)//2))

Solution (Python):
N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
dist=[-1]*N
dist[0]=0
check={0}
flag=False
while len(check)>0:
    if flag:
        break
    now=check.pop()
    for nex in branch[now]:
        if dist[nex]==-1:
            dist[nex]=(dist[now]+1)%2
            check|={nex}
        elif dist[nex]!=(dist[now]+1)%2:
            check=set()
            flag=True
            dist=[-1]*N
            break
if dist[0]==-1:
    print(N*(N-1)//2-M)
else:
    odd=dist.count(1)
    even=dist.count(0)
    print(odd*even-M)