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

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

  return True

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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

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

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

  return True

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

Submission status: Runtime Error

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

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

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

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

  return True

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

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

    color = [0] * (N+1)

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

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

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

colors = [-1]*(N+1)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
def dfs(n,c):
    if colors[n] == -1:
        colors[n] = c
        for nx in edges[n]:
            dfs(nx,(c+1)%2)
    else:
        if colors[n] != c:
            print(choose(N,2)-M)
            exit()
dfs(1,0)
white = colors.count(0)
black = N - white
print(white*black-M)

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(2000000)

    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 paint(n,p,c):
        ret = 1
        if colors[n]!=-1 and colors[n]!=c:
            ret = 0
        else:
            colors[n] = c
            for nx in edges[n]:
                if nx != p:
                    ret = min(ret,paint(nx,n,(c+1)%2))
        return ret

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

    print(ans)

main()

Submission status: Runtime Error

Solution code:
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 paint(n,p,c):
    ret = 1
    if colors[n]!=-1 and colors[n]!=c:
        ret = 0
    else:
        colors[n] = c
        for nx in edges[n]:
            if nx != p:
                ret = min(ret,paint(nx,n,(c+1)%2))
    return ret

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

print(ans)

Submission status: Runtime Error

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

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

color = [0] * N

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

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
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:
        for i in range(n):
            st = "white" if seen[i] == 0 else "black"
            print(str(i) + ":" + st)
    else:
        print("is not bipartite")

main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(1000000)

def triangle(m, g):
    for i in range(m):
        nex_ls = g[i]
        for nex in nex_ls:
            for nex2 in g[nex]:
                if nex2 == i:
                    continue
                if nex2 in nex_ls:
                    return True
    return False


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, set())
        dic_a.add(b-1)
        dic_b = g.setdefault(b-1, set())
        dic_b.add(a-1)

    if triangle(m, g):
        line_max = int((n-1)*n/2)
        print(line_max - m)
    else:
        if n % 2 == 0:
            line_max = int(n*n/4)
            print(line_max - m)
        else:
            line_max = int((n*n - 1)/2)
            print(line_max - m)


main()

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:

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

Solution code:

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)

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

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

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

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

print(int(ans))

Submission status: Runtime Error

Solution code:

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)

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

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

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

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

print(int(ans))

Submission status: Runtime Error

Solution code:

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)

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

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

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

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

print(int(ans))

Submission status: Runtime Error

Solution code:

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)

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

def f(v,c):
    color[v] = c
    for j in range(len(graph[v])):
        if color[ graph[v][j] ] == c: # 隣接している頂点が同色の場合 二部グラフではない
            return False
        elif (color[graph[v][j]] ==0 and not f(graph[v][j],-c)):
            return False
    return True 

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

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

print(int(ans))

Submission status: Runtime Error

Solution code:

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)

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

def f(v,c):
    color[v] = c
    for i in range(len(graph[v])):
        if color[ graph[v][i] ] ==c:
            return False
        elif (color[graph[v][i]] ==0 and not f(graph[v][i],-c)):
            return False
    return True 

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

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

print(int(ans))

Submission status: Runtime Error

Solution code:

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)

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

def f(v,c):
    color[v] = c
    for i in range(len(graph[v])):
        if color[ graph[v][i] ] ==c:
            return False
        elif color[graph[v][i]] ==0 and not f(graph[v][i],-c):
            return False
    return True 

k = 1
for i in range(N):
    if color[i] == 0:
        if not f(i,1):
            k = -1

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

print(int(ans))

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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):
    global ok, tag
    if tag[i] != -1:
        if tag[i] != c:
            ok = True
        return
    tag[i] = c
    for j in e[i]:
        dfs(j, (c + 1) % 2)


dfs()

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

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

Solution code:
import sys

sys.setrecursionlimit(5000)

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

Solution code:
import sys

sys.setrecursionlimit(3000)

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

Solution code:
# 二部グラフ判定
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: Runtime Error

Solution code:

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

Solution code:
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: Runtime Error

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

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

g = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)


class Tree:
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += 1
                self.dfs(v)
                self.depth -= 1
            elif (self.depths[u] - self.depths[v]) % 2 == 0:
                return False

        self.colors[u] = self.BLACK

        return True


tree = Tree(g)
if tree.dfs(0):
    black = len([x for x in tree.depths if x % 2])
    white = len([x for x in tree.depths if x % 2 == 0])
    ans = black * white - m

else:
    raise Exception
    ans = n * (n - 1) // 2 - m

print(ans)

Submission status: Runtime Error

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

def is_bipartite(v, r, d):
    color[v] = d
    for u in E[v]:
        if u == r:
            continue
        if color[u] == d:
            return False
        is_bipartite(u, v, (d + 1) % 2)
    return True

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

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

if is_bipartite(0, -1, 0):
    b = sum(color)
    w = N - b
    print(b * w - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Runtime Error

Solution code:
from collections import deque

def dfs():
    global color
    global edge
    color = [-1] * n
    edge = [[] for _ in range(n)]

    q = deque([])
    q.append(0)
    color[0] = 1
    
    while q:
        p = q.pop()
        for u in edge[p]:
            if color[u] == -1:
                color[u] = (color[p] + 1) % 2
                q.append(u)
            else:
                if color[u] == color[p]:
                    return False
    return True

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

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


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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def is_biparty(g):
    u = list(g.keys())[0]
    s = [u]
    c = {}
    c[u] = True
    while s:
        u = s.pop()
        for v in g[u]:
            if v not in c:
                c[v] = not c[u]
                s.append(v)
            else:
                if c[v] == c[u]:
                    return False

    return True, c

@mt
def slv(N, M, AB):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    b, c = is_biparty(g)
    if b:
        d = Counter(c.values())
        return d[True] * d[False] - M
    else:
        return N * (N-1) // 2 - M


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter


def dfs(x):
    res = True
    for e in edge[x]:
        if color[e] is None:
            color[e] = 0 if color[x] else 1
            res &= dfs(e)
        else:
            if color[e] == color[x]:
                res &= False
            else:
                res &= True
    return res


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 = [None] * N
color[0] = 0
isBin = dfs(0)

if isBin:
    C = Counter(color)
    print(C[0] * C[1] - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Runtime Error

Solution code:
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    [g[b-1].append(a-1) for a,b in ab]
    ans=[None]*n
    ans[0]=0
    temp=[0]
    while temp:
        i=temp.pop()
        for j in g[i]:
            if ans[j]==None:
                ans[j]=ans[i]^True
                temp.append(j)
            else:
                if ans[i]^ans[j]==0:
                    #print(n*(n-1)//2-m)
                    print(1/0)
                    return 0
    print((ans.count(0)*(ans.count(0)-1)//2)*(ans.count(1)*(ans.count(1)-1)//2)-m)
main()

Submission status: Runtime Error

Solution code:
class BinPartite:
    def __init__(self, N, es):
        self.colors = [0 for i in range(N)]
        self.es = es

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

    def color_cnt(self, color):
        return self.colors.count(color)

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


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

Bp = BinPartite(N, e_list)
if Bp.is_bipartite():
    b = Bp.color_cnt(1)
    w = Bp.color_cnt(-1)
    print(b*w-M)
else:
    print(N*(N-1)//2 - M)