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
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def dfs(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    stack = [(0,start)]
    
    while stack:
        cost, cur_node = stack.pop()

        # 未探索のノードをstackに入れる
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                stack.append((dist[nex_node],nex_node))
                
    return dist

def isnibu(graph:list, dist:list) -> bool:
    for i,edges in enumerate(graph):
        for _, j in edges:
            if dist[i]%2 == dist[j]%2:
                return False
    
    return True
    
    

n,m = li()

adj_lst = [set() for _ in range(n)]

for _ in range(m):
    a,b = li_()
    
    adj_lst[a].add((1,b))
    adj_lst[b].add((1,a))
    
dist = dfs(adj_lst, n, 0)

nibu = isnibu(adj_lst, dist)

ans = 0
if isnibu(adj_lst, dist):
    ans = sum([dist[i]%2 == 1 for i in range(n)]) * sum([dist[i]%2 == 0 for i in range(n)]) - m
    
else:
    ans = n*(n-1)//2 - m
    
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

G = [[] for i in range(N)]
for _ in range(M):
    Ai, Bi = map(int, input().split())
    G[Ai - 1].append(Bi - 1)
    G[Bi - 1].append(Ai - 1)

color = [0] * N
def dfs(v, c):
    '''
    頂点vをcで塗る　そこから深さ優先探索で交互に塗っていく
    '''
    color[v] = c
    for i in G[v]:
        if color[i] == c:
            return False
        if color[i] == 0 and not(dfs(i, -c)):
            return False
    return True

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

Submission status: Accepted

Solution code:
from collections import defaultdict 
import sys

sys.setrecursionlimit(10**8)


N,M = map(int,input().split())
dict = defaultdict(set)

for i in range(M):
	a,b = list(map(int,input().split()))
	dict[a].add(b)
	dict[b].add(a)


color = [0 for i in range(N+1)]
nibu = True

def dfs(v,c):
	u'''
	v : 現在のグラフの頂点
	c : vのグラフのcolor
	queue : 探索済みのグラフの頂点
	res   : 二部グラフの判定 bool
	'''

	global color
	global nibu 

	for i in list(dict[v]):
		if color[i] == c:#隣の頂点が同じ値を与えられている際Falseを返す
			nibu = False
			break
		elif color[i] == 0:	#探索済みでなければ再帰する
			color[i] = c*-1		#0ならcとは異なる値を格納
			dfs(i,-c)		#引数に-cとすることで,cが1=>-1=>1を繰り返す


color[1] = 1  #始点色分けする

dfs(1,1)

if nibu:
	b = color.count(1)
	w = color.count(-1)
	ans = b * w - M
else:
	ans = N * (N-1)//2 - M
	
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
adjL = [[] for v in range(N)]
for e in range(M):
    A, B = map(int, input().split())
    adjL[A - 1].append(B - 1)
    adjL[B - 1].append(A - 1)

# 二部グラフかどうかを判定する（頂点を1or-1で塗っていく）
colors = [0] * N

def dfs(vNow, color):
    colors[vNow] = color # 頂点vNowをcolorで塗る
    for v in adjL[vNow]:
        if colors[v] == color:
            # 隣接する頂点vが同じ色で彩色済みならば、二部グラフではない
            return False
        if colors[v] == 0 and not dfs(v, -color):
            # 隣接する頂点vが未彩色ならば、もう１つの色で塗ってみる
            return False

    return True


IsBipartite = dfs(0, 1)

if IsBipartite:
    # 二部グラフである場合
    num = colors.count(1)
    print(num * (N - num) - M)
else:
    # 二部グラフでない場合
    print(N * (N - 1) // 2 - M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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)

memo = [0 for i in range(n)]
color = [-1 for i in range(n)]
black = 0
white = 0
flag = 0


def search(v):
    for i in graph[v]:
        if memo[i] == 0:
            memo[i] = 1
            color[i] = (color[v] + 1) % 2
            if color[i] == 0:
                global black
                black += 1
            else:
                global white
                white += 1
            search(i)
        else:
            if color[v] == color[i]:
                global flag
                flag = 1

memo[0] = 1
color[0] = 0
black += 1
search(0)

if flag == 1:
    print(n*(n-1)//2 - m)
else:
    print(black * white - m)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
edge = [[] for i 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)
# -1 → 0,1に塗っていきます
color=[-1 for i in range(n)]
def dfs(pos):
    ret = True
    for i in range(len(edge[pos])):
        to = edge[pos][i]
        if color[to] == -1:
            color[to] = 1 ^ color[pos]
            ret &= dfs(to)
        else:
            ret &= not (color[to]==color[pos])
    return ret

color[0]=0
if dfs(0):
    black, white = 0, 0
    for i in range(n):
        if color[i]==0:
            black += 1
        else:
            white += 1
    print(black*white-m)
else:
    print(n*(n-1)//2-m)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return map(int, input().split())
N, M = inpl()
G = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = inpl()
    G[a].append(b)
    G[b].append(a)

visited = [False] * (N+1)
color = [0] * (N+1)

Q = deque()
Q.append(1)

bipartite = True
while Q:
    p = Q.popleft()
    if visited[p]:
        continue
    visited[p] = True
    for q in G[p]:
        if visited[q]:
            if color[p] == color[q]:
                bipartite = False
                break
        else:
            color[q] = color[p]^1
            Q.append(q)

if bipartite:
    B = sum(color)
    W = N - B
    print(B*W-M)
else:
    print(N*(N-1)//2 - M)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**7)
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	
#print nl


def dfs(v):
	F[v]=1
	for i in nl[v]:
		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			#２部グラフではない
			print N*(N-1)/2-M
			sys.exit()
		else:
			continue
		#print v,i,color,F
		
		if F[i]==0:
			dfs(i)


F=[0]*(N+1)
color=[0]*(N+1)
color[1]="w"
dfs(1)

#２部グラフの場合
print color.count("b")*color.count("w")-M

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
from collections import Counter

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

color = [0 for i in range(N+1)]

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

color[1] = 1
que = deque([1])
concatenation = False

while len(que):
    p = que.popleft()
    for q in list(G[p]):
        if color[q] == 0:
            color[q] = -color[p]
            que.append(q)
        elif color[q] == color[p]:
            concatenation = True
            break
    
if concatenation:
    print(int(N*(N-1)/2-M))
else:
    B = Counter(color)[1]
    W = Counter(color)[-1]
    print(B*W-M)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(v, c):
    flgs[v] = c
    for i in range(len(G[v])):
        if flgs[G[v][i]] == c:
            return False
        if flgs[G[v][i]] == 0 and not dfs(G[v][i], -c):
            return False

    return True


if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [[] for _ in range(N + 1)]
    for i in range(M):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)

    # 二部グラフ判定をする
    bi_flg = True
    flgs = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        if flgs[i] == 0:
            if not dfs(i, 1):
                bi_flg = False

    if bi_flg:
        # 二部グラフならBW-M
        print(flgs.count(1) * flgs.count(-1) - M)
    else:
        # 二部グラフでないなら全辺-M
        print((N * (N - 1) // 2) - M)

Submission status: Accepted

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

N,M = map(int,raw_input().split())
es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  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 = (sum(colors) + N) // 2
  w = N-b
  print(b*w - M)
else:
  all = N*(N-1) // 2
  print(all - M)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,m = LI()
    e = collections.defaultdict(set)
    t = [0] * n
    for _ in range(m):
        a,b = LI_()
        e[a].add(b)
        e[b].add(a)

    q = [0]
    t[0] = 1
    for i in range(n):
        c = q[i]
        tc = t[c]
        for d in e[c]:
            if t[d] == 0:
                t[d] = 3-tc
                q.append(d)
            elif t[d] == tc:
                return n*(n-1) // 2 - m

    a = sum(t) - n

    return a*(n-a) - m


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys


# 再帰深度の制限
REC_LIMIT = 100000

# 頂点の色
UNDEF = 0
WHITE = 1
BLACK = -WHITE


# 所与のグラフが二部グラフならば，(True, color[])を返す
# さもなければ，(False, None)を返す
# 参考：『プログラミングコンテストチャレンジブック』（第2版）p.94
def is_bipartite_graph(adj_list):
    n = len(adj_list)  # 頂点数
    color = [UNDEF] * n

    # 頂点をWHITEとBLACKで塗っていく
    def dfs(v, c):
        color[v] = c
        for u in adj_list[v]:
            if color[u] == c:
                # 隣接頂点が同色で塗られていたら不可
                return False
            if color[u] == UNDEF and not dfs(u, -c):
                # 隣接頂点が未彩色なら，反対の色で塗れるか
                return False
        return True  # すべて色を塗れた
    for i in range(n):
        if color[i] == 0:
            # 未彩色なら，WHITEで塗ってみる
            if not dfs(i, WHITE):
                return (False, None)
    return (True, color)


def compute_max_additional_edges(n, m, adj_list):
    is_bi, color = is_bipartite_graph(adj_list)
    if not is_bi:
        # 二部グラフではない場合
        return n * (n - 1) // 2 - m
    else:
        # 二部グラフである場合
        w = sum(c == WHITE for c in color)
        b = sum(c == BLACK for c in color)
        return w * b - m


def main():
    # 最大再帰深度の再設定
    sys.setrecursionlimit(REC_LIMIT)
    # 入力の読み込み
    n, m = (int(x) for x in input().split())
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        a, b = (int(x) - 1 for x in input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    res = compute_max_additional_edges(n, m, adj_list)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
問題
http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_c
解説
https://img.atcoder.jp/code-festival-2017-qualb/editorial.pdf
参考
http://code-festival-2017-qualb.contest.atcoder.jp/submissions/1666106
'''
from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))

def is_biparate(links):
    '''
    0=white,1=blackとする
    2部グラフなら黒に塗られている頂点の数を返す
    2部グラフでないなら-1を返す。
    '''
    
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]  #0=white, 1=blackとする
    visited = set()
    while q:
        v, c = q.pop()
        if v in visited:
            if colors[v] != c: #最初に塗られた色とは反対の色が塗られるなら
                return -1
            continue
        visited.add(v)
        colors[v] = c
        for u in links[v]:
            q.append((u, c ^ 1))  #0^1=1 1^1=0 vとは反対の色を塗る
    return sum(colors)  #1の数 = blackの数
 




n, m = readLine_int_list()
g = [set() for _ in range(n)]

def main():
    for _ in range(m):
        a, b = readLine_int_list()
        a -= 1
        b -= 1
        g[a].add(b)
        g[b].add(a)
    
    
    
    bp1 = is_biparate(g)
    if bp1 == -1:
        '''
        2部グラフではない場合
            結論：完全グラフになるまで辺を追加できる
            →why
                奇サイクル上のある点をvとする
                s → v → tが偶数長でも、 奇サイクルの他の頂点を余計に経由することで奇数長になる
                s → tが奇数長になれば線が引ける
                つまり、任意の頂点間において奇数長が存在することになる
            完全グラフの辺の数は、n * (n - 1) // 2
            これには元あった辺の数まで含まれているので、 -m する
        '''
        max_m = n * (n - 1) // 2
    else:
        '''
        2部グラフの場合
            結論:(blackの数*whiteの数)本、線ができる
            why
                奇数閉路が存在しない => 異なる色間は必ず奇数長、同色間は必ず偶数長 
                1. whiteとblackの間は奇数長のパスが存在する ->線が引ける
                2. 同じ色どうしには奇数長のパスは存在しない -> 線は引かれない
                black=3, white=2の時の線の引き方 = b*w
            b*wにはパスの長さが1つまりもともとのパスが含まれてるので、-m　する
        '''
        max_m = bp1 * (n - bp1)
        
    print(max_m - m)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))

def is_biparate(links):
    '''
    0=white,1=blackとする
    2部グラフなら黒に塗られている頂点の数を返す
    2部グラフでないなら-1を返す。
    '''
    
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]  #0=white, 1=blackとする
    visited = set()
    while q:
        v, c = q.pop()
        if v in visited:
            if colors[v] != c: #最初に塗られた色とは反対の色が塗られるなら
                return -1
            continue
        visited.add(v)
        colors[v] = c
        for u in links[v]:
            q.append((u, c ^ 1))  #0^0=1 1^1=0 vとは反対の色を塗る
    return sum(colors)  #1の数 = blackの数
 




n, m = readLine_int_list()
g = [set() for _ in range(n)]

def main():
    for _ in range(m):
        a, b = readLine_int_list()
        a -= 1
        b -= 1
        g[a].add(b)
        g[b].add(a)
    
    
    
    bp1 = is_biparate(g)
    if bp1 == -1:
        '''
        2部グラフではない場合
            結論：完全グラフになるまで辺を追加できる
            →why
                奇サイクル上のある点をvとする
                s → v → tが偶数長でも、 奇サイクルの他の頂点を余計に経由することで奇数長になる
                s → tが奇数長になれば線が引ける
                つまり、任意の頂点間において奇数長が存在することになる
            完全グラフの辺の数は、n * (n - 1) // 2
            これには元あった辺の数まで含まれているので、 -m する
        '''
        max_m = n * (n - 1) // 2
    else:
        '''
        2部グラフの場合
            結論:(blackの数*whiteの数)本、線ができる
            why
                奇数閉路が存在しない => 異なる色間は必ず奇数長、同色間は必ず偶数長 
                1. whiteとblackの間は奇数長のパスが存在する ->線が引ける
                2. 同じ色どうしには奇数長のパスは存在しない -> 線は引かれない
                black=3, white=2の時の線の引き方 = b*w
            b*wにはパスの長さが1つまりもともとのパスが含まれてるので、-m　する
        '''
        max_m = bp1 * (n - bp1)
        
    print(max_m - m)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def is_biparate(links):
    '''
    0=white,1=blackとする
    2部グラフなら黒に塗られている頂点の数を返す
    2部グラフでないなら-1を返す。
    '''
    
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]  #0=white, 1=blackとする
    visited = set()
    while q:
        v, c = q.pop()
        if v in visited:
            if colors[v] != c: #最初に塗られた色とは反対の色が塗られるなら
                return -1
            continue
        visited.add(v)
        colors[v] = c
        for u in links[v]:
            q.append((u, c ^ 1))  #0^0=1 1^1=0 vとは反対の色を塗る
    return sum(colors)  #1の数 = blackの数
 
 
n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
 
bp1 = is_biparate(links)

if bp1 == -1:
    '''
    2部グラフではない場合
        結論：完全グラフになるまで辺を追加できる
        →why
            奇サイクル上のある点をvとする
            s → v → tが偶数長でも、 奇サイクルの他の頂点を余計に経由することで奇数長になる
            s → tが奇数長になれば線が引ける
            つまり、任意の頂点間において奇数長が存在することになる
        完全グラフの辺の数は、n * (n - 1) // 2
        これには元あった辺の数まで含まれているので、 -m する
    '''
    max_m = n * (n - 1) // 2
else:
    '''
    2部グラフの場合
        結論:(blackの数*whiteの数)本、線ができる
        why
            奇数閉路が存在しない => 異なる色間は必ず奇数長、同色間は必ず偶数長 
            1. whiteとblackの間は奇数長のパスが存在する ->線が引ける
            2. 同じ色どうしには奇数長のパスは存在しない -> 線は引かれない
            black=3, white=2の時の線の引き方 = b*w
        b*wにはパスの長さが1つまりもともとのパスが含まれてるので、-m　する
    '''
    max_m = bp1 * (n - bp1)
    
print(max_m - m)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
G = dict()
for i in range(N):
    G[i+1] = []
color_list = [0] * N

close = False

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

# color
color_list[0] = 1
for q in G[1]:
    color_list[q-1] = -1

que = deque(G[1])

while len(que) > 0:
    p = que.popleft()
    for q in G[p]:
        if color_list[q-1] == 0:
            color_list[q-1] = - color_list[p-1]
            que.append(q)
        elif color_list[q-1] == color_list[p-1]:
            close = True
            break

if close == True:
    print(N*(N-1) // 2 - M)
else:
    print(color_list.count(1)*color_list.count(-1) - M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5 + 1)

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

valid = [True for i in range(n)]

def dfs(x):
    ret = 1
    valid[x] = False
    for y in sus[x]:
        if valid[y]:
            valid[y] = False
            ret += dfs(y)
    return ret

color = [-1 for i in range(n)]
sol = 0
cnt = [0, 0]

def boji(x):
    global cnt
    cnt[color[x]] += 1
    for y in sus[x]:
        if color[y] == -1:
            color[y] = 1 - color[x]
            if boji(y):
                return True
        elif color[y] == color[x]:
            return True
    return 0

for i in range(n):
    if color[i] == -1 and valid[i]:
        cnt = [0, 0]
        color[i] = 0
        if boji(i) == 0:
            sol += cnt[0] * cnt[1]
        else:
            d = dfs(i)
            sol += d * (d - 1) // 2
print(sol - m)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
color = [-1] * N
def dfs(v, c):
    if color[v] != -1:
        return color[v] == c
    else:
        color[v] = c
        ret = True
        for w in edge[v]:
            ret &= dfs(w, c ^ 1)
        return ret

if dfs(0, 0) == False:
    print(N * (N - 1) // 2 - M)
else:
    c1 = color.count(0)
    c2 = color.count(1)
    assert(c1 + c2 == N)
    print(c1 * c2 - M)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    la = [None] * (n + 1)
    xt = [None] * (2 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 1
    st = [1]
    pu = st.append
    po = st.pop
    col = [None] * (n + 1)
    col[1] = 1
    while st:
        x = po()
        y = la[x]
        nc = 3 - col[x]
        while y is not None:
            t = dat[y]
            if col[t] is None:
                col[t] = nc
                pu(t)
            else:
                col[t] |= nc
            y = xt[y]
    ans = 0
    p = [0] * 3
    for i in xrange(1, n + 1):
        if col[i] == 3:
            ans = 0
            break
        ans += p[col[i]]
        p[col[i]] += 1
    print n * (n - 1) / 2 - m - ans
main()

Submission status: Accepted

Solution code:
def is_biparate(links):
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]
    visited = set()
    cnt = 0
    while q:
        v, c = q.pop()
        if v in visited:
            if colors[v] != c:
                return False
            continue
        visited.add(v)
        colors[v] = c
        cnt += c
        for u in links[v]:
            q.append((u, c ^ 1))
    return cnt


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

bp1 = is_biparate(links)
if is_biparate(links):
    max_m = bp1 * (n - bp1)
else:
    max_m = n * (n - 1) // 2
print(max_m - m)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
from collections import deque
que = deque()
col = [-1]*n
que.append(0)
col[0] = 0
g = [0]*2
g[0] = 1
yes = 1
while que:
    v = que.popleft()
    for t in G[v]:
        if col[t] == -1:
            col[t] = col[v]^1
            g[col[t]] += 1
            que.append(t)
        else:
            if col[t] == col[v]:
                yes = 0
if yes:
    ans = g[0]*g[1]
    for v in range(n):
        for t in G[v]:
            if v < t and col[v] != col[t]:
                ans -= 1
    print(ans)
else:
    print(n*(n-1)//2 - m)

Submission status: Runtime Error

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

color = [-1]*n
color[0] = 0
explored = {0}
next = deque(connect[0])
exploring =deque()
Yes = True
explored.add(0)
while next:
    now = next.popleft()
    exploring.extend(connect[now])
    while exploring:
        a = exploring.popleft()
        if color[a] == -1:
            color[a]=(color[now]+1)%2
        elif color[a] == (color[now]+1)%2:
            pass
        else:
            Yes = False
        if a not in explored:
            next.append(a)
        explored.add(a)
if -1 in color and Yes:
    fjasodjasodg


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

Submission status: Runtime Error

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

color = [-1]*n
color[0] = 0
explored = {0}
next = deque(connect[0])
exploring =deque()
Yes = True
explored.add(0)
while next:
    now = next.popleft()
    exploring.extend(connect[now])
    while exploring:
        a = exploring.popleft()
        if color[a] == -1:
            color[a]=(color[now]+1)%2
        elif color[a] == (color[now]+1)%2:
            pass
        else:
            Yes = False
        if a not in explored:
            next.append(a)
        explored.add(a)
if -1 in color:
    fjasodjasodg


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

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict
N, M = map(int, input().split())
graph = [[] for _ in range(N)]

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


visited = [False for _ in range(N)]
color = [0 for _ in range(N)]

def dfs(now, c):

    color[now] = c

    for adj in graph[now]:
        if color[adj] == c:
            return False

        if color[adj] == 0 and not dfs(adj, -c):
            return False

    return True

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

Submission status: Runtime Error

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

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

C = [-1 for _ in range(N)] 
visited = set()

def DFS(p, c):
  C[p] = c
  flag = True
  for q in I[p]:
    #print(p,q)
    if C[q] == c:
      return False
    elif C[q] == -1:
      if not DFS(q, 1-c):
        return False
  return True

#print(DFS(0, 0))
#print(C)
print(C.count(0)*C.count(1)-M if DFS(0, 0) else N*(N-1)//2-M)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10**10)

def dfs(v):
    flag = True

    for nxt in edge[v]:
        if l[v] == l[nxt]:
            return False
        elif l[v] + l[nxt] == 1:
            continue
        else:
            l[nxt] = 1 - l[v]
            cnt[1-l[v]] += 1
            flag &= dfs(nxt)
    
    return flag
        

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)

l = [-1] * n
l[0] = 0
cnt = [1, 0]

if dfs(0):
    print(cnt[0] * cnt[1] - m)
else:
    print(n * (n - 1) // 2 - m)

Submission status: Runtime Error

Solution code:
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)
x=[0]*n
x[0]=1
def dfs(r,node):
  for mode in edge[node]:
    if r==mode:continue
    x[mode]=1^x[node]
    dfs(node,mode)
dfs(-1,0)
print(x.count(0)*x.count(1)-m)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(n):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
x=[0]*n
x[0]=1
def dfs(r,node):
  for mode in edge[node]:
    if r==mode:continue
    x[mode]=1^x[node]
    dfs(node,mode)
dfs(-1,0)
print(x.count(0)*x.count(1)-m)

Submission status: Runtime Error

Solution code:
from collections import deque
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: Runtime Error

Solution code:
"""
奇数本の辺で成り立つ閉路があれば、全ての頂点同士を1本の辺で結ぶことができる。
そうでない場合は、奇数本の辺をたどってたどり着ける頂点同士は全て1本の辺で結ぶことができる。
奇数本の閉路があるかどうかを、どうやって判定するか？
二部グラフ判定を行う。
二部グラフ判定ってどうやるんだっけ？→となりのノードに違う色をつけていって、矛盾がなければ二部グラフ。矛盾があれば二部グラフじゃない。
"""
import sys
sys.setrecursionlimit(200000)
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)

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

Solution code:
"""
奇数本の辺で成り立つ閉路があれば、全ての頂点同士を1本の辺で結ぶことができる。
そうでない場合は、奇数本の辺をたどってたどり着ける頂点同士は全て1本の辺で結ぶことができる。
奇数本の閉路があるかどうかを、どうやって判定するか？
二部グラフ判定を行う。
二部グラフ判定ってどうやるんだっけ？→となりのノードに違う色をつけていって、矛盾がなければ二部グラフ。矛盾があれば二部グラフじゃない。
"""
def judgeBiGragh(edges):
    n = len(edges)
    colors = [-1]*(n+1)
    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)

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)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
if judgeBiGragh(edges):
    ans = (N//2)*(N-N//2) - M
else:
    ans = choose(N,2)-M

print(ans)

Submission status: Runtime Error

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

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

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

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

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

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