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.



Sample input:
6 5
1 2
2 3
3 4
4 5
5 6


Sample output:
4

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
d=[-1]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([(1,0)])
d[1]=0
while q:
  now,par=q.popleft()
  for to in e[now]:
    if to==par:continue
    if d[to]==-1:
      d[to]=(d[now]+1)%2
      q.append((to,now))
    elif d[to]==d[now]%2:
      print(n*(n-1)//2-m)
      exit()
p=sum(d)+1
print(p*(n-p)-m)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
d=[-1]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([(1,0)])
d[1]=0
a,b=0,0
while q:
  now,par=q.popleft()
  for to in e[now]:
    if to==par:continue
    if d[to]==-1:
      d[to]=(d[now]+1)%2
      a+=1
      q.append((to,now))
    elif d[to]!=d[now]%2:b+=1
    else:
      print(n*(n-1)//2-m)
      exit()
p=sum(d)+1
print(p*(n-p)-a-b//2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    def dfs(node, color):
        # 二部グラフ判定。隣接ノードを自分と異なる色にぬれるか、をチェックする。
        # 黒いノードを-1、白を1、無色を0とする。
        node_color[node] = color
        adjnodes = edges[node]
        for anode in adjnodes:
            anode_color = node_color[anode]
            if anode_color == 0:
                dfs(anode, -color)
            elif anode_color == color:
                gisnibu[0] = 0
                break
            else:
                pass

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

#print(dfs(0,1),colors)
if dfs(0,1): #もし二部グラフなら
  one = 0; zero = 0
  for x in colors:
    if x == 1:
      one += 1
    else:
      zero += 1
  ans = one*zero-M
else:
  ans = N*(N-1)//2-M
print(ans)

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  n,m=map(int,input().split())
  g=[[] for _ in range(n)]
  for _ in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    g[a].append(b)
    g[b].append(a)
  dp=[[False]*2 for _ in range(n)]
  dp[0][0]=True
  bfs=deque([0])
  while bfs:
    top=bfs.popleft()
    cur,par=top>>1,top&1
    for to in g[cur]:
      if not dp[to][par^1]:
        dp[to][par^1]=True
        bfs.append((to<<1)+(par^1))
  x=0;y=0;z=0
  for i in range(n):
    if dp[i][0] and dp[i][1]:
      x+=1
    elif dp[i][0]:
      y+=1
    elif dp[i][1]:
      z+=1
  ans=-m
  ans+=x*(x-1)>>1
  ans+=x*(y+z)
  ans+=y*z
  print(ans)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
 
 
colors = [0] * n
def dfs(v, color):
    colors[v] = color
    for to in edges[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and (not dfs(to, -color)):
            return False
 
    return True
 
if dfs(0, 1):
    x = colors.count(1)
    print(x * (n - x) - m)
 
else:
    print(n * (n - 1) // 2 - m)

Submission status: Accepted

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

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

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

# 2部グラフかどうかを判定する
# 色の初期化、0:未着色
colors = [0]*n
def dfs(v, color):
    """
    parm v: node
    param color: 1 or -1
    """
    colors[v] = color
    for to in g[v]:
        if colors[to] == color:
            return False
        
        if colors[to] == 0:
            if not dfs(to, -color):
                return False
    return True

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

if is_bipartite():
    # すべての対抗で辺が張れる
    print(colors.count(-1)*colors.count(1) - m)
else:
    # すべての対抗の辺が張れる
    print((n*(n-1))//2 - m)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

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

from collections import deque

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

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

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

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


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

	#print(Q)

	f=0

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


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


	ans-=m

	print(ans)

















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

#二部グラフか否か判定  
vis = [0 for _ in range(N)]
q = deque([(0,0)])
is_bip = True
#print(clr)
while q:
  p, c = q.popleft()
  clr[p] = c
  vis[p] = 1
  for x, w in adj[p]:
    if vis[x] == 0:
      q.append((x,(w+c)%2))
      #print((x,(w+c)%2))
    else: 
      if (clr[x] + c) % 2 == 0:
        is_bip = False
        break
  if not is_bip:
    break
    
#ここから問題特有の処理
if is_bip:#二部グラフの場合
  apple = clr.count(0)
  orange = clr.count(1)
  #print(apple,orange,M)
  print(apple*orange-M)
  
else:#二部グラフでない場合
  print(N*(N-1)//2-M)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)


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

    return True

if dfs(0, 1):
    x = colors.count(1)
    print(x * (n - x) - m)

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

Submission status: Accepted

Solution code:
"""
奇数本の辺で成り立つ閉路があれば、全ての頂点同士を1本の辺で結ぶことができる。
そうでない場合は、奇数本の辺をたどってたどり着ける頂点同士は全て1本の辺で結ぶことができる。
奇数本の閉路があるかどうかを、どうやって判定するか？
二部グラフ判定を行う。
二部グラフ判定ってどうやるんだっけ？→となりのノードに違う色をつけていって、矛盾がなければ二部グラフ。矛盾があれば二部グラフじゃない。
"""
import sys
sys.setrecursionlimit(200000)
N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

n = len(edges)
colors = [-1]*(n+1)
def judgeBiGragh(edges):
    def paint(v,c):
        if colors[v] == -1:
            colors[v] = c
            nxC = (c+1)%2
            for nxV in edges[v]:
                result = paint(nxV,nxC)
                if result == False:
                    return result
        else:
            if colors[v] != c:
                return False
        return True
    return paint(1,0)

def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
if judgeBiGragh(edges):
    cnt0 = colors.count(0)
    cnt1 = colors.count(1)
    ans = cnt0*cnt1 - M
else:
    ans = choose(N,2)-M

print(ans)

Submission status: Accepted

Solution code:
from networkx import*
n,*t=map(str.split,open(0))
n,m=map(int,n)
try:a,b=map(len,bipartite.sets(Graph(t)));a*=b
except:a=n*~-n//2
print(a-m)

Submission status: Accepted

Solution code:
from networkx import*
n,*t=map(str.split,open(0))
n,m=map(int,n)
g=Graph(t)
try:a,b=map(len,bipartite.sets(g));a*=b
except:a=n*~-n//2
print(a-m)

Submission status: Accepted

Solution code:
from networkx import*
n,*t=map(str.split,open(0))
n,m=map(int,n)
g=Graph()
g.add_edges_from(t)
try:a,b=map(len,bipartite.sets(g));a*=b
except:a=n*~-n//2
print(a-m)

Submission status: Accepted

Solution code:
from networkx import*
n,*t=[t.split()for t in open(0)]
n,m=map(int,n)
g=Graph()
g.add_edges_from(t)
try:a,b=map(len,bipartite.sets(g));a*=b
except:a=n*~-n//2
print(a-m)

Submission status: Accepted

Solution code:
from networkx import*
(n,m),*t=[[*map(int,t.split())]for t in open(0)]
g=Graph()
g.add_edges_from(t)
try:a,b=map(len,bipartite.sets(g));a*=b
except:a=n*~-n//2
print(a-m)

Submission status: Accepted

Solution code:
from networkx import*
(n,m),*t=[[*map(int,t.split())]for t in open(0)]
g=Graph()
g.add_edges_from(t)
try:a,b=map(len,algorithms.bipartite.sets(g));a*=b
except:a=n*~-n//2
print(a-m)

Submission status: Accepted

Solution code:
(n,m),*t=[map(int,t.split())for t in open(0)]
*e,=eval('[],'*-~n)
for a,b in t:e[a]+=b,;e[b]+=a,
q=[g:=1]
f=q*2+[-1]*n
for v in q:
 for w in e[v]:
  if~f[w]:g&=f[v]^f[w]
  else:f[w]=f[v]^1;q+=w,
r=sum(f)
print((n*~-n//2,r*(n-r))[g]-m)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ns[a].append(b)
    ns[b].append(a)
    
def is_bip(ns):
    start = 0
    q = [start]
    cs = [None]*n
    cs[start] = 1
    while q:
        u = q.pop()
        c = cs[u]
        cc = int(not c)
        for v in ns[u]:
            if cs[v] is None:
                cs[v] = cc
                q.append(v)
            elif cs[v]==c:
                return False, None
    return True, cs

res, cs = is_bip(ns)
if res:
    n1 = sum(cs)
    n2 = n - n1
    ans = n1*n2 - m
else:
    ans = n*(n-1)//2 - m
print(ans)

Submission status: Accepted

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

Q = deque()
Q.append(0)
C = [-1] * N
C[0] = 0

B = True
while len(Q) > 0:
    q = Q.popleft()
    pc = C[q]
    for g in G[q]:
        if C[g] == -1:
            C[g] = 1 - pc
            Q.append(g)
            continue
        if C[g] == pc:
            B = False

if not B:
    print((N * (N - 1) // 2) - M)
else:
    W = C.count(0)
    B = C.count(1)
    print(W * B - M)

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.buffer.readline
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    mod = 10**9 + 7
    n, m = nm()
    G = [list() for _ in range(n)]
    for _ in range(m):
        u, v = nm()
        u -= 1; v -= 1
        G[u].append(v)
        G[v].append(u)
    col = [-1]*n
    q = deque([0])
    col[0] = 1
    while q:
        v = q.popleft()
        for x in G[v]:
            if col[x] < 0:
                col[x] = col[v] ^ 1
                q.append(x)
            elif col[x] == col[v]:
                print(n * (n-1) // 2 - m)
                return
    bl = sum(col)
    wh = n - bl
    print(bl * wh - m)
    return

solve()

# T = ni()
# for _ in range(T):
#     solve()

Submission status: Accepted

Solution code:
# coding:utf-8
class Tree(object):
    def __init__(self, N):
        self.tree   = [[] for _ in range(N)]
        self.colors = [0  for _ in range(N)]

    def add_node(self, a, b):
        self.tree[a].append(b)
    # 二部グラフか判定する関数
    def is_bipartite_graph(self, v, color):
        self.colors[v] = color
        for to in self.tree[v]:
            if self.colors[to] == color:
                return False
            if self.colors[to] == 0 and not self.is_bipartite_graph(to, -color):
                return False
        return True
    
    def count_node(self, color):
        return self.colors.count(color)
    
if __name__ == "__main__":

    import sys
    sys.setrecursionlimit(200000)
    # input data
    N, M = map(int, input().split())
    tree = Tree(N)
    for _ in range(M):
        a, b = map(int, input().split())
        tree.add_node(a-1, b-1)
        tree.add_node(b-1, a-1)
    
    # tree dp
    is_bpr = tree.is_bipartite_graph(0, 1)
    if is_bpr:
        bla = tree.count_node(1)
        whi = N - bla
        print(bla*whi-M)
    else:
        print(int(N*(N-1)/2-M))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

color = [None] * N
def dfs(n, c):
  color[n] = c
  for nei in adj[n]:
    if color[nei] is not None:
      if color[nei] == c: 
        return False
    elif not dfs(nei, 1-c):
      return False
    # else:
    #   dfs(nei, 1-c)

  return True

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

Submission status: Accepted

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

def isbi():
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]
    visited = set()
    cnt = 0
    while q:
        now, c = q.pop()
        if now in visited:
            if colors[now] != c:
                return False
            continue
        visited.add(now)
        colors[now] = c
        cnt += c
        for nxt in link[now]:
            q.append((nxt, c ^ 1))
    return cnt

ret = isbi()
if not ret:
    ans = n*(n-1)//2 - m
else:
    ans=ret*(n-ret) - m
print(ans)

Submission status: Accepted

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

from collections import defaultdict
from collections import deque
visited = [0] * n

Q = deque()
Q.append([0,1]) # 1:black, 2: white
while Q:
    now,color = Q.popleft()
    if color==1:
        nxt_c = 2
    else:
        nxt_c = 1

    for nxt in link[now]:
        if visited[nxt] == nxt_c:
            continue
        if visited[nxt] != 0 and visited[nxt] !=nxt_c:
            ans = n*(n-1)//2 - m
            print(ans)
            exit()
        visited[nxt] = nxt_c
        Q.append([nxt,nxt_c])

b_cnt=0
w_cnt=0
for c in visited:
    if c==1:
        b_cnt+=1
    else:
        w_cnt+=1

print(b_cnt*w_cnt - m)

Submission status: Accepted

Solution code:
# 2部グラフは特別ケース。
# 2部グラフの時、各ノードは色の違うノードとしか奇数長サイクルを持たない。
# 2部グラフでない時、各ノードは必ず全ノードと奇数長サイクルを持つ。
import queue
from collections import Counter
N,M = map(int,input().split())
ans = [-1]*N
pas = [[] for _ in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    pas[u-1].append(v-1)
    pas[v-1].append(u-1)

q = queue.Queue()
q.put(0)
ans[0] = 0
flag = True
while (not q.empty()):
    now = q.get()
    nowa = ans[now]
    for i in pas[now]:
        if ans[i] == -1:
            if nowa == 0:
                ans[i] = 1
            else:
                ans[i] = 0
            q.put(i)
        else:
            if ans[i] == nowa:
                flag = False

if flag:
    c = Counter(ans)
    zer = c[0]
    one = c[1]
    print(zer*one-M)
else:
    print(N*(N-1)//2-M)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

cl = [-1] * (N+1)
cl[1] = 0
is_bipartite = True
stack = [1]
while stack:
    v = stack.pop()
    for c in G[v]:
        if cl[c] != -1 and cl[c] == cl[v]:
            is_bipartite = False
            break
        if cl[c] == -1:
            cl[c] = 1 - cl[v]
            stack.append(c)
    if not is_bipartite:
        break
if is_bipartite:
    print(cl.count(0) * cl.count(1) - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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

visited = [False]*(N+1)
colors = [None] * (N)
is_bipartite = True

## improved dfs ###
def dfs(node, c):
  colors[node-1] = c
  visited[node] = True
  for nei in adj_list[node]:
    if colors[nei-1] == c:
      return False
    if not visited[nei] and not dfs(nei, 1-c):
      return False

  return True

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    edge = [ZZ() for _ in range(M)]
    E = defaultdict(list)
    for a, b in edge:
        E[a].append(b)
        E[b].append(a)

    color = [0] * (N+1)

    def is_bi(v, c):
        color[v] = c
        for to in E[v]:
            if color[to] == c: return False
            if color[to] == 0 and not is_bi(to, -c): return False
        return True

    if is_bi(1, 1):
        x = color.count(1)
        output = x * (N - x) - M
    else: output = N * (N - 1) // 2 - M
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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)

C = [-1]*n
def is_bipartite(v, color):
  C[v] = color
  for nv in G[v]:
    if C[nv] != -1 and color == C[nv]:
      return False
    if C[nv] == -1:
      if not is_bipartite(nv, color ^ 1):
        return False
  return True

if is_bipartite(0, 0):
  b = C.count(0)
  w = n - b
  ans = b*w - m
else:
  ans = n*(n-1)//2 - m
print(ans)

Submission status: Accepted

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

dist = [2] * N
dist[0] = 0
d = [[0, -1]]
num = {0:1, 1:0}
while d:
  node, par = d.pop()
  children = graph[node]
  for child in children:
    if child == par:
      continue
    if dist[child] < 2:
      if dist[child] == (dist[node] + 1) % 2:
        continue
      print(N*(N-1)//2 - M)
      quit()
    else:
      dist[child] = (dist[node] + 1) % 2
      num[dist[child]] += 1
      d.append([child, node])

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

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


class Vertex:
    def __init__(self, value):
        self.edge = []
        self.value = value


visited = []
flg = True      # 2部グラフかどうか
def dfs(G, v, pv, col):
    global flg

    visited[v] = True
    G[v].value = col

    for nv in G[v].edge:
        if visited[nv]:
            if nv != pv and G[nv].value == G[v].value:
                flg = False
            continue
        dfs(G, nv, v, (col + 1) % 2)


def main():
    N, M = map(int, input().split())
    G = [Vertex(0) for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        G[a].edge.append(b)
        G[b].edge.append(a)
    
    for _ in range(N):
        visited.append(False)
    dfs(G, 0, -1, 0)

    if flg:
        bw = [0, 0]     # [black, white]
        for i in range(N):
            bw[G[i].value] += 1
        print(bw[0] * bw[1] - M)
    else:
        print(N*(N-1) // 2 - M)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]

#隣接リストで管理
adj = [[] for j in range(N)]
for edge in edges:
    x, y = edge
    adj[x-1].append(y)
    adj[y-1].append(x)

color = [0] * N

#二部グラフ判定
def dfs(node, c):
    color[node-1] = c
    for i in adj[node-1]:
        if c == color[i-1]:
            return False
        if color[i-1] == 0 and not dfs(i, -c):
            return False
    return True

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

Submission status: Accepted

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

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

michi = [[] for i in range(N)]
for i in range(M):
  tempa, tempb = map(int,input().split())
  michi[tempa-1].append(tempb-1)
  michi[tempb-1].append(tempa-1)
#print(michi)
  
colors = [0 for i in range(N)]

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

if dfs(0,1):
  a = colors.count(1)
  b = colors.count(-1)
  #print(colors)
  print(a*b-M)
else:
  print(N*(N-1)//2 - M)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N
        self._even = [i%2 for i in range(0,N)]
        self._odd =[(i+1)%2 for i in range(0,N)]

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
            self._even[gy] += self._even[gx]
            self._odd[gy] += self._odd[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]
            self._even[gx] += self._even[gy]
            self._odd[gx] += self._odd[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

    def calc_comb(self):
        N=len(self._parent)
        ans=0
        for i in range(N):
            if self.find_root(i) ==i:
                ans+=self._even[i]*self._odd[i]
        return ans


import sys

input=sys.stdin.readline

N,M=map(int,input().split())
uf=UnionFindVerSize(2*N)
for i in range(M):
    a,b=map(int,input().split())
    uf.unite(2*a-2,2*b-1)
    uf.unite(2*b-2,2*a-1)

ans=uf.calc_comb()
for i in range(N):
    if uf.is_same_group(2*i,2*i+1):
        ans-=1

ans//=2
print(ans-M)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N
        self._even = [i%2 for i in range(0,N)]
        self._odd =[(i+1)%2 for i in range(0,N)]

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
            self._even[gy] += self._even[gx]
            self._odd[gy] += self._odd[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]
            self._even[gx] += self._even[gy]
            self._odd[gx] += self._odd[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

    def calc_comb(self):
        N=len(self._parent)
        ans=0
        for i in range(N):
            if self.find_root(i) ==i:
                ans+=self._even[i]*self._odd[i]
        return ans


import sys

N,M=map(int,input().split())
uf=UnionFindVerSize(2*N)
for i in range(M):
    a,b=map(int,input().split())
    uf.unite(2*a-2,2*b-1)
    uf.unite(2*b-2,2*a-1)

ans=uf.calc_comb()
for i in range(N):
    if uf.is_same_group(2*i,2*i+1):
        ans-=1

ans//=2
print(ans-M)