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:
#!usr/bin/env python3
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


#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
# print(color)
# print(flag)

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

Submission status: Accepted

Solution code:
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
# MOD = 998244353


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)

Submission status: Accepted

Solution code:
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:  # 2部グラフ
			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]:  # 2部グラフでない
				print(N*(N-1)//2-M)
				sys.exit()
		
DFS(0)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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():
    # print('bipartite', par)
    evens = par.count(0)
    odds = n - evens
    print(odds * evens - m)
else:
    # print('not bipartite', par)
    print(n * (n - 1) // 2 - m)

# 全ての奇数路にパスが張れる
# 1 : 既に張られている
# 3 : 張れる
# >= 5 : 途中に長さ3のパスを張ると長さが2減るので、奇数のまま2ずつ減らして3になる

# 二部グラフでない場合、奇サイクルが存在するので、
# 偶数路だったパスには、奇サイクルを挟んだ奇数路がある
# すべての頂点間にパスが張れる

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#設定
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 #sからの距離
		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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)

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

Submission status: Accepted

Solution code:
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)      
# ans
if bl:
  # 二部グラフ
  x = sum(color[1:])
  y = N-x
  print(x*y-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())
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) # c^1 == xor (0+1==True)
dfs(1, 0)      
bl = all(color[a] != color[b] for a, b in AB)      
# ans
if bl:
  # 二部グラフ
  x = sum(color[1:])
  y = N-x
  print(x*y-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())
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)      
# ans
if bl:
  # 二部グラフ
  x = sum(color[1:])
  y = N-x
  print(x*y-M)
else:
  # 完全グラフ
  print(N*(N-1)//2-M)

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C - 3 Steps
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:
    # 完全グラフにする(奇数長のパスがある場合は必ず2ずつ減らしていけば長さが3になる)
    answer = N*(N-1)//2 - M

print(answer)

Submission status: Accepted

Solution code:
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:
    # 完全グラフにする(奇数長のパスがある場合は必ず2ずつ減らしていけば長さが3になる)
    answer = N*(N-1)//2 - M

print(answer)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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