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)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    """
    辺(a,b)を結べるかどうかは、(a,b)の距離が奇数長かどうかと等しい
    なぜなら、(a,b)が奇数長なら(a,b)の間の3-stepを1-stepで出来るような辺を張れるのでいずれ3-stepになる。
    
    1.二部グラフでないなら、奇数サイクルが1つ以上存在する
        ―奇数サイクルがあるなら、サイクル上のvを通るようなpath(s,t)が存在し、それが偶数長でも余計に奇数サイクルを通ることで奇数長のパスを見つける事ができる
    2.二部グラフならグループ1とグループ2の任意の点を結ぶパスは奇数長になり、同グループのパスは偶数長になる
    """
    N,M=MI()
    edge = [[]for _ in range(N)]
    for _ in range(M):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    
    group = [-1]*N
    group[0] = 0

    def is_bipartite():
        stack = [0]
        while stack:
            v = stack.pop()
            for to in edge[v]:
                if group[to]!=-1 and group[to]==group[v]:
                    return False
                if group[to]==-1:
                    stack.append(to)
                    group[to] = group[v]^1
        return True

    bipartite = is_bipartite()
    if bipartite:
        g1 = group.count(0)
        g2 = N-g1
        ans = g1*g2
    else:
        ans = N*(N-1)//2
    ans -= M
    print(ans)

                
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)


d = [10 ** 6 for _ in range(N + 1)]
d[1] = 0
Q = dq([1])
while len(Q):
  p = Q.popleft()
  for q in e[p]:
    if d[q] > d[p] + 1:
      Q.append(q)
      d[q] = d[p] + 1
c = [[0] * 2 for _ in range(N + 1)]
wh = 0
gr = 0
for x in range(1, N + 1):
  for y in e[x]:
    dy = d[y] % 2
    c[x][dy] = 1
  cc = (c[x][0] & c[x][1])
  wh += c[x][0]
  gr += cc

if gr:
  print(N * (N - 1) // 2 - M)
  exit(0)

res = 0
for x in range(1, N + 1):
  res += wh * c[x][1]

  #print(res, x)
#print(res)
print(res - M)

Submission status: Accepted

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)

import sys

sys.setrecursionlimit(10 ** 6)


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

    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, w in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += w
                self.dfs(v)
                self.depth -= w

        self.colors[u] = self.BLACK

    def bipartite_graph(self, u, c):
        self.colors[u] = c
        for v in self.adj[u]:
            if self.colors[v] == c:
                return False
            if self.colors[v] == self.WHITE and not self.bipartite_graph(v, -c):
                return False

        return True


tree = Tree(g)
if tree.bipartite_graph(0, tree.GRAY):
    black = tree.colors.count(tree.GRAY)
    white = tree.colors.count(tree.BLACK)
    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 root(v):
    if v == par[v]:
        return v
    par[v] = root(par[v])
    return par[v]

def unite(u, v):
    u = root(u)
    v = root(v)
    if u == v:
        return
    if rank[u] < rank[v]:
        u, v = v, u
    par[v] = u
    if rank[u] == rank[v]:
        rank[u] += 1

def same(u, v):
    return root(u) == root(v)

N, M = map(int, input().split())
par = list(range(2 * N))
rank = [0] * (2 * N)
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b + N)
    unite(a + N, b)

if same(0, N):
    print(N * (N - 1) // 2 - M)
else:
    c = 0
    for i in range(N):
        c += same(0, i)
    print(c * (N - c) - M)

Submission status: Accepted

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

def is_bipartite(v, d):
    color[v] = d
    for u in E[v]:
        if color[u] == d:
            return False
        elif color[u] != -1:
            continue
        if not is_bipartite(u, (d + 1) % 2):
            return False
    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, 0):
    b = sum(color)
    w = N - b
    print(b * w - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Accepted

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

N,M=map(int,input().split())
g = [[] for _ 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)

F = [-1 for _ in range(N)]
def dfs(s,f):
    global F
    global g
    F[s] = f
    for d in g[s]:
        if  F[d] == -1:
            if f == 1:
                if not dfs(d,0):
                    return False
            else:
                if not dfs(d,1):
                    return False
        else:
            if F[d] == f:
                return False
    return True

if dfs(0,0):
    f1 = F.count(1)
    f0 = F.count(0)
    print(f1*f0-M)
else:
    print(N*(N-1)//2 - M)

Submission status: Accepted

Solution code:
from collections import deque

def dfs():
    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())
edge = [[] for _ in range(n)]
color = [-1] * n

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: Accepted

Solution code:
from collections import deque

def dfs():
    global color
    color = [-1] * 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())
edge = [[] for _ in range(n)]

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


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: Accepted

Solution code:
n,m = map(int, input().split())
e = [set() for _ in range(n)]
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    e[u].add(v)
    e[v].add(u)

def dfs():
    col = [-1]*n
    col[0] = 0
    q = [0]
    while len(q)>0:
        v = q.pop()
        c = col[v]
        for u in e[v]:
            if col[u]<0:
                col[u] = (c+1)%2
                q.append(u)
            else:
                if c==col[u]:
                    return False
    return True

if not dfs():
    print(n*(n-1)//2 - m)
    exit()

visited = [False]*n
visited[0] = True
num = [0,0]
q = [(0,0)]
while len(q)>0:
    u,d = q.pop()
    num[d%2] += 1
    for v in e[u]:
        if visited[v]:
            continue
        q.append((v,d+1))
        visited[v] = True

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)

def cal_bw(now, value, record, g):
  search_li = g[now]
  record[now] = value
  for s in search_li:
    if record[s] == value:
      return False
    if record[s] != -1:
      continue
    record = cal_bw(s, (value+1)>>1 == 0, record, g)
    if not record:
      return False
  return record

def run():
  N, M = map(int, input().split())
  g = {}
  for m in range(M):
    a, b = map(int, input().split())
    g.setdefault(a, []).append(b)
    g.setdefault(b, []).append(a)
  record = [-1]*(N+1)
  record = cal_bw(1, 0, record, g)
  #print(record)
  if record:
    print(record.count(0)*record.count(1) - M)
  else:
    print(N*(N-1)//2 - M)
    
if __name__ == '__main__':
    run()

Submission status: Accepted

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, None

    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: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
edges = [set() for _ in range(N)]
for _ in range(M):
    a, b = inpl()
    a -= 1
    b -= 1
    edges[a].add(b)
    edges[b].add(a)

L = [0] * 2
signs = [None] * N
pool = [(0,0)]
while pool:
    n, s = pool.pop()
    if signs[n] is None:
        signs[n] = s
        L[s] += 1
        for c in edges[n]:
            edges[c].remove(n)
            pool.append((c,1-s))
    elif signs[n] == s:
        continue
    else:
        ans = N*(N-1)//2 - M
        break
else:
    ans = L[0]*L[1] - M

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
Chk=[0]*n
Odd=False
T=[0]
Chk[0]=1
while T:
  t=T.pop()
  for g in edge[t]:
    if not Chk[g]:
      Chk[g]=Chk[t]*(-1)
      T.append(g)
    elif Chk[g]*Chk[t]==1:
      Odd=True
if Odd:
  print(n*(n-1)//2-m)
else:
  c=Chk.count(1)
  print(c*(n-c)-m)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N, M = rl()
graph = [[] for _ in range(N+1)] # 0は使わない、直接行ける頂点
for _ in range(M):
    a, b = rl()
    graph[a].append(b)
    graph[b].append(a)

# 二部グラフのチェック、各頂点に0か1の色を塗る、1の頂点に0の色
color = [None] * (N+1) # 0は使わない
color[1] = 0
stack = [1]
bool = True
while stack:
    node = stack.pop()
    for n in graph[node]:
        if color[n] == None:
            color[n] = 1 - color[node]
            stack.append(n)
        elif color[n] == color[node]:
            bool = False
        else:
            continue

if bool:
    # 二部グラフ
    print((color.count(1) * color.count(0)) - M)
else:
    print(N*(N-1)//2 - M)
#29

Submission status: Accepted

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

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

for a, b in AB:
    PATH[a].append(b)
    PATH[b].append(a)

color = [None] * (N+1)
color[1] = 0
q = deque([1])

while q:
    x = q.popleft()
    for y in PATH[x]:
        if color[y] is None:
            color[y] = 1 - color[x]
            q.append(y)

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys


sys.setrecursionlimit(10 ** 6)


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: Accepted

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

adj = [list() for _ in range(N)]

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


res = 0

color = [None]*N

for x in range(N):
    if color[x] is not None:
        continue
    
    cnt = [0,1]
    stack = [x]
    color[x] = True
    flag = True
    while stack:
        v = stack.pop()
        c = not color[v]
        for u in adj[v]:
            if color[u] is None:
                stack.append(u)
                color[u] = c
                cnt[c] += 1
            elif flag:
                flag = c == color[u]

    if flag:
        res += cnt[0]*cnt[1]
    else:
        cnt = sum(cnt)
        res += cnt*(cnt-1)//2

print(res-M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10, 7))

n, m = map(int, input().split())
G = [[] for _ in range(n)]
color = [-1]*n

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

def dfs(v, c):
	color[v] = c
	ans = True
	for u in G[v]:
		if color[u] == c:
			return False
		if color[u] != -1:
			continue
		ans &= dfs(u, 1-c)
	return ans

if dfs(v=0, c=0):
	k = sum(color)
	print(k*(n-k) - m)
else:
	print(n*(n-1)//2 - m)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10, 7)) 


# 頂点vをcolor(1 or -1)で塗り、矛盾がないか調べる
def dfs(v, color):
    colors[v] = color
    for to in edges[v]:
        # 同じ色が隣接するならFalse
        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())
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
if dfs(0, 1):
    print(len([i for i in colors if i == -1])*len([j for j in colors if j == 1]) - M)
else:
    print(N * (N-1) // 2 - M)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
G = {}
for _ in range(M):
    A,B = map(int,input().split())
    if A not in G:
        G[A] = []
    G[A].append(B)
    if B not in G:
        G[B] = []
    G[B].append(A)
color = [-1 for _ in range(N+1)]
que = deque([1])
color[1] = 0
flag = 0
while que:
    cur = que.popleft()
    for x in G[cur]:
        if color[x]<0:
            color[x] = (color[cur]+1)%2
            que.append(x)
        else:
            if color[x]==(color[cur]+1)%2:continue
            else:
                flag=1
                break
    if flag==1:break
if flag==0:
    n = color.count(0)
    m = color.count(1)
    cnt = n*m-M
else:
    cnt = (N*(N-1))//2-M
print(cnt)

Submission status: Accepted

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

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

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

colors = [0 for i in range(N + 1)]
def dfs(v, color):
    colors[v] = color
    for t in edge[v]:
        if colors[t] == color:
            return False
        if colors[t] == 0 and not dfs(t, -color):
            return False
    return True

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

if is_bipartite():
    # print(colors)
    cB, cW = 0, 0
    for c in colors[1:]:
        if c == 1:
            cB += 1
        else:
            cW += 1
    print(cB * cW - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for i in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    # bipartite check
    col=[-1]*n
    col[0]=0
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv in E[v]:
            if(col[v]==col[nv]): # 二部グラフではない -> 全部繋げられる
                print(n*(n-1)//2-m)
                return
            elif(col[nv]!=-1 and col[nv]^col[v]): continue
            col[nv]=1-col[v]
            Q.append(nv)

    # 二部グラフ -> 偶数と奇数とが繋げられる
    even=col.count(0)
    odd=col.count(1)
    print(even*odd-m)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for i in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    # bipartite check
    col=[-1]*n
    col[0]=0
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv in E[v]:
            if(col[v]==col[nv]): # 二部グラフではない
                print(n*(n-1)//2-m)
                return
            elif(col[nv]!=-1 and col[nv]^col[v]): continue
            col[nv]=1-col[v]
            Q.append(nv)

    depth=[-1]*n
    depth[0]=0
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv in E[v]:
            if(depth[nv]!=-1): continue
            depth[nv]=depth[v]+1
            Q.append(nv)

    odd=sum(1 for i in range(n) if(depth[i]&1))
    even=n-odd
    ans=odd*even-m
    print(ans)
resolve()

Submission status: Accepted

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)
                    return 0
    print(ans.count(0)*ans.count(1)-m)
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
bin_or_not = True
ans = (N-1)*N//2 - M
w_or_b = [-1]*N
stack = [0]
w_or_b[0] = 0
while stack:
    x = stack.pop()
    for i in e_list[x]:
        if w_or_b[i] >= 0:
            bin_or_not = w_or_b[x]^w_or_b[i]
        else:
            w_or_b[i] = (w_or_b[x] + 1)%2
            stack.append(i)
        if not bin_or_not:
            break
    if not bin_or_not:
        break
if bin_or_not:
    w =  w_or_b.count(0)
    b = w_or_b.count(1)
    ans = w*b - M
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([random.randint(0,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

n,m=LI()
g,c=GI(n,m)

v=[-1 for i in range(n)]

def IsBipartite():
    q=[0]
    v[0]=0
    while q:
        c=q.pop()
        for n in g[c]:
            if v[n]==-1:
                q.append(n)
                v[n]=1-v[c]
            elif v[n]==v[c]:
                return False
    return True

if IsBipartite():
    ans=sum(v)*(n-sum(v))-m
else:
    ans=n*(n-1)//2-m
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([random.randint(0,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

n,m=LI()
g,c=GI(n,m)

v=[-1 for i in range(n)]

def bfs(x):
    q=[x]
    v[x]=0
    while q:
        c=q.pop()
        for n in g[c]:
            if v[n]==-1:
                q.append(n)
                v[n]=1-v[c]

bfs(0)

flg=True
for i in range(n):
    MM=max([v[nb] for nb in g[i]])
    mm=min([v[nb] for nb in g[i]])
    if MM==mm and MM!=v[i]:
        continue
    else:
        flg=False
        break

#show(v,flg)
if flg:
    ans=sum(v)*(n-sum(v))-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())

d = [None] * N

dic = {}

for i in range(M):

    a,b = map(int,input().split())
    a-=1
    b-=1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

q = deque([0])
d[0] = 0
flag = False

while len(q) > 0:

    now = q.popleft()

    for i in dic[now]:

        if d[i] == None:
            d[i] = (d[now] + 1) % 2
            q.append(i)


        elif d[i] != (d[now] + 1) % 2:
            flag = True
            break

if flag:
    print (N * (N-1) // 2 - M)

else:
    odd = 0
    even = 0

    for i in d:
        if i == 0:
            even += 1
        else:
            odd += 1

    #print (d)
    print (odd * even - M)

Submission status: Accepted

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

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

# 二部グラフ判定(単純グラフ:連結,　自己ループ無, 多重辺無　を想定)
# -1:未訪問, 0:黒, 1:白
visited = [-1] * N

# 0を黒塗りでスタート
def is_bipartite(v=0, color=0):
    flag = True
    visited[v] = color
    for nv in to[v]:
        ncolor = (color + 1) % 2
        if visited[nv] == -1:
            flag &= is_bipartite(nv, ncolor)
        elif visited[nv] != ncolor:
            return False
    return flag

if is_bipartite():
    a = sum(visited)
    b = N - a
    ans = a*b - M
else:
    ans = N*(N-1)//2 - M

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)
from collections import defaultdict

G = defaultdict(list)


N, M = map(int, input().split())
visited = [[False for i in range(N)] for j in range(5)]
for i in range(M):
    v,u = map(int, input().split())
    G[v-1].append(u-1)
    G[u-1].append(v-1)

# 頂点間に奇数長のパスがあるかどうか確認するために 2部グラフ 判定をする
COLOR = [0 for i in range(N)]

def dfs(pos, color):
    global COLOR
    COLOR[pos] = color
    ans = True
    for to in G[pos]:
        if COLOR[to] == color:
            return False
        elif COLOR[to] == 0:
            ans &= dfs(to, -color)
    return ans

if dfs(0, 1):
    count = 0
    for i in COLOR:
        if i == -1:
            count += 1
    another = N-count
    print(count*another-M)
else:
    # 2 部グラフではなかったので、完全グラフから M を引いた値を出力する
    print(N*(N-1)//2-M)