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:
import sys
sys.setrecursionlimit(10**6)
WHITE = 1
BLACK = 0
UNCON = -1

def dfs(v,c):
	color[v] = c
#	print(v,c,color[v])
	for n in edge[v]:
#		print("   ",n)
		if(color[n] != UNCON):
			if(color[n] == c):
				return False
			continue
		if(dfs(n,1-c) == False):
			 return False
	return True

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

#print(edge)
is_bip = True
for v in range(1,n+1):
	if(color[v] != -1):
		continue
	if(dfs(1,1)==False):
		is_bip = False

if(is_bip):
	wnum = 0
	bnum = 0
#	print(color)
	for v in range(1,n+1):
		if(color[v] == WHITE):
			wnum += 1
		else:
			bnum += 1
	print(wnum*bnum-m)
else:
	print(int(n*(n-1)/2)-m)

Submission status: Accepted

Solution code:
"""
グラフが二部グラフかどうかを判定する。
二部グラフであれば、AグループのノードとBグループのノード同士をそれぞれ結ぶことができる。
二部グラフでない場合、すべてのノード同士を結ぶことができる。
"""
import math
from collections import Counter
import sys
sys.setrecursionlimit(200000)
def choose(n):
    return math.factorial(n)//(math.factorial(n-2)*math.factorial(2))
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)

colors = [-1]*(N+1)
def f(n,p):
    c = colors[n]
    for v in edges[n]:
        if v != p:
            if colors[v] == -1:
                colors[v] = 1 if c==0 else 0
                f(v,n)
            elif colors[v] == c:
                print(choose(N)-M)
                exit()
colors[1]=0
f(1,0)
count1 = colors.count(0)
count2 = colors.count(1)
print(count1*count2-M)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000000)


def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for next_v in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v]:
                return False
            continue
        seen[next_v] = 1-current_color
        # 再帰的に探索
        if not dfs(g, next_v, seen, 1 - current_color):
            return False
    return True


def main():
    n, m = map(int, input().split())

    g = {}
    for i in range(m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a-1, [])
        dic_a.append(b-1)
        dic_b = g.setdefault(b-1, [])
        dic_b.append(a-1)
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True
    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, 0, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        white = len([x for x in seen if x == 0])
        black = n - white

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

main()

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
    # print('start :'+str(c))
    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())
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
import sys
sys.setrecursionlimit(10**6)
dep=[-1 for i in range(n+1)]
color=[0 for i in range(n+1)]
def dfs(s,d,c):
    dep[s]=d
    color[s]=c
    for i in edge[s]:
        if dep[i]==-1:
            if not dfs(i,d+1,-c):
                return False
        else:
            if color[i]==c:
                return False
    return True
if dfs(1,0,1):
    print(color.count(1)*color.count(-1)-m)
else:
    print(n*(n-1)//2-m)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
edg = [[] for i in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  edg[a].append(b)
  edg[b].append(a)
  
check1 = [0] * n
check0 = [0] * n

from collections import deque

q = deque()
q.append((0,1))
check0[0] = 1

while q:
  p,t = q.pop()
  for e in edg[p]:
    if t:
      if check1[e]:continue
      check1[e] = 1
      q.appendleft((e,0))
    else:
      if check0[e]:continue
      check0[e] = 1
      q.appendleft((e,1))
ans = 0
sc0 = sum(check0)
sc1 = sum(check1)
for i in range(n):
  if check0[i]:
    if check1[i]:
      ans += n - 1
    else:
      ans += sc1
  else:
      ans += sc0
print(ans//2 - m)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

seen = [-1] * (N + 1)
seen[1] = 1
node = [1]
while node:
    s = node.pop()
    x = seen[s]
    for t in edge[s]:
        if seen[t] == -1:
            seen[t] = 1 ^ x
            node.append(t)
        elif seen[t] == 1 ^ x:
            continue
        else:
            ans = N * (N - 1) // 2 - M
            print(ans)
            exit()

X = seen.count(1)
ans = 0
for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    ans += X - len(edge[i])
print(ans)

Submission status: Accepted

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

stack = [(0,0)]
even_odd[0][0] = True
evencnt = 0
while stack:
    p,ev = stack.pop()
    if ev == 0:
        evencnt += 1
        if even_odd[p][ev^1]:
            evencnt = -1
            break
    nev = ev^1
    for nxt in path[p]:
        if even_odd[nxt][nev]:continue
        even_odd[nxt][nev] = True
        stack.append((nxt,nev))
if evencnt == -1:
    print(n*(n-1)//2 - m)
else:
    print(evencnt*(n-evencnt) - m)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
G = [[]for i in range(n)]
for _ in range(m):
    a,b = map(lambda z: int(z)-1,input().split())
    G[a].append(b)
    G[b].append(a)

color = [-1 for _ in range(n)]
queue = deque([0])
color[0] = 1
two = True
while queue:
    now = queue.popleft()
    for to in G[now]:
        if color[to] == color[now]:
            two = False
            break
        if color[to] == -1:
            color[to] = 1 - color[now]
            queue.append(to)

if two:
    print(sum(color)*(n-sum(color)) - m)
else:
    print(n*(n-1)//2 - m)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 適当に根を決める
# 根から偶数回でも奇数回でも行ける点があれば，結局全部繋げる
# なければ，偶奇が異なるものだけ繋げる

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if not directed:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = LI()
A,B = LIR(M,2)

pt = edges_to_pt(A,B,N)

odd = [False]*N
even = [False]*N
even[0] = True

q = [0]
c = 1
flag = False
while q:
    q1 = []
    for v in q:
        for u in pt[v]:
            if c%2:
                if even[u]:
                    flag = True
                    break
                if not odd[u]:
                    odd[u] = True
                    q1.append(u)
            else:
                if odd[u]:
                    flag = True
                    break
                if not even[u]:
                    even[u] = True
                    q1.append(u)                
        if flag:
            break
    if flag:
        break
    q = q1
    c += 1

if flag:
    print(N*(N-1)//2 - M)
else:
    odds = 0
    evens = 0
    for i in range(N):
        if odd[i]:
            odds += 1
        else:
            evens += 1
    print(odds*evens - M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)


def f(u,c):
    color[u] = c
    for v in graph[u]:
        if color[v] == 0: # まだ塗られていない場合
            if not f(v,-c):
                return False
        else:
            if color[v] == c: # 隣接している頂点が同色の場合 二部グラフではない
                return False
    return True 

flag = True
color = [0 for _ in range(N)]
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            flag = False
            break

if flag: # 二部グラフ
    ans = color.count(1)*color.count(-1) - M
else:
    ans = N*(N-1)//2 - M

print(int(ans))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def is_bipartite(graph, colors):
    stack = [(0, 1)]
    while stack:
        v, color = stack.pop()
        colors[v] = color
        for child in graph[v]:
            if colors[child] == color:
                return False
            if colors[child] == 0:
                stack.append((child, -color))
    return True


def solve():
    N, M = map(int, rl().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        graph[b].append(a)
    
    colors = [0] * N
    if is_bipartite(graph, colors):
        w = colors.count(1)
        ans = w * (N - w) - M
    else:
        ans = N * (N - 1) // 2 - M
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

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

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

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

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

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

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

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

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

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

Submission status: Accepted

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


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


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

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

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())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
flag = True
color = [-1] * n
que = deque()
que.append((0,0))
while que:
    u, c = que.popleft()
    if color[u] == -1:  # 未探索の時
        color[u] = c
        for e in g[u]:
            que.append((e, c ^ 1))  # ^はxor
    else:
        if color[u] != c:
            flag = False
            break
if flag:
    w = len([i for i in color if i == 0])
    ans = w * (n - w) - m
else:
    ans = (n * (n - 1) // 2 - m)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 解説AC
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

color = [0] * N

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

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

Submission status: Accepted

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

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

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

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

    return sum(sign)

s = isBipartite()

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

Submission status: Accepted

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

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

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

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

    return sum(sign)

s = isBipartite()

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

Submission status: Accepted

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

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

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

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

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

    return sum(sign)

s = isBipartite()

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

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

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

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

if is_bipartite():
    b = colors.count(1)
    w = N-b
    print(b*w-M)
else:
    whole = N*(N-1)//2
    print(whole-M)

Submission status: Accepted

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
from collections import deque


def main():

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

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

    # bipartite graph
    side = sum(side)
    print(side * (N - side) - M)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

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

    N,M = map(int,input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        
    print(bipartite_graph(edge,N,M))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


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


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

ok = False
tag = [-1] * n


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


dfs()

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

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

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

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

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

color = [-1]*n;

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

Submission status: Accepted

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

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

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

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

colors = [0]*n

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(1000000)
# 頂点数と辺数を入力
N, M = map(int, input().split())
# グラフの入力
G = [[] for _ in range(N)]  # 頂点数Nだけ準備
color = [-1] * N  # 未訪問は-1とする
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
# 探索
flag = True
dist = [-1] * N
# dist[0] = 0
que = deque([])
for v in range(N):
    if dist[v] != -1:  # 探索済みの時はスルー
        continue
    dist[v] = 0
    que.append(v)
    while que:
        v = que.popleft()
        for nv in G[v]:
            if dist[nv] == -1:  # 未訪問の時
                dist[nv] = dist[v] + 1
                que.append(nv)
            else:  # すでに訪問済みの時は整合性を確認
                if dist[v] == dist[nv]:
                    flag = False
if flag:
    w = [i for i in dist if i % 2 == 0]
    b = [i for i in dist if i % 2 != 0]
    ans = len(w) * len(b) - M
else:
    ans = N * (N - 1) // 2 - M
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

# 二部グラフ判定
def dfs(u, c):
    color[u] = c  # 訪問したら指定の色で塗る
    for v in G[u]:  # uからつながっている頂点を順に取り出す
        if color[v] != -1:  # すでに訪問していた場合
            if color[v] == c:
                return False  # 隣接する頂点が同じ色のときはFalse
            else:
                continue
        else:  # 未訪問の時は色は違う色にしてDFSで再帰的に探索
            if not dfs(v, 1 - c):  # FalseだったらFalseを返す
                return False
    return True


# 頂点数と辺数を入力
N, M = map(int, input().split())
# グラフの入力
G = [[] for _ in range(N)]  # 頂点数Nだけ準備
color = [-1] * N  # 未訪問は-1とする
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
# 探索
flag = True
for i in range(N):
    if color[i] == -1:
        if not dfs(i, 0):
            flag = False
            break
if flag:
    ans = color.count(1) * color.count(0) - M
else:
    ans = N * (N - 1) // 2 - M
print(ans)

Submission status: Accepted

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

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

  return True


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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

import collections
from collections import deque

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

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
    Col = [-1] * N
    q = deque()
    q.append((0, 0))
    bipartite = True
    while q:
        nnode, ncol = q.pop()
        if Col[nnode] == -1:
            Col[nnode] = ncol
            for e in Edge[nnode]: q.append((e, ncol ^ 1))
        else:
            if Col[nnode] != ncol:
                bipartite = False
                break
    
    if bipartite:
        zero, one = 0, 0
        for i, n in enumerate(Col):
            if n == 0: zero += 1
            else: one += 1
        print(zero * one - M)
    else:
        print(N * (N - 1) // 2 - M)
    return 0

if __name__ == "__main__":
    solve()