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: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
DIS = [[-1] * N for _ in range(N)]
for _ in range(M):
  a, b = map(int, input().split())
  DIS[a-1][b-1]=DIS[b-1][a-1]=1

stack = []
co = 0

def se(li, stn):
  global stack
  global DIS
  global co
  for n in range(N):
    if n == stack:
      continue
    if DIS[li][n] == 1 and n not in stack:
      stack.append(n)
      if len(stack) == 4 and DIS[stack[0]][n] != 1:
        DIS[stack[0]][n] = 1
        DIS[n][stack[0]] = 1
        stack.pop()
        co += 1
      else:
        se(n, len(stack))
        stack.pop()

for outer in range(N):
  stack.append(outer)
  for inner in range(N):
    stack.append(inner)
    if DIS[outer][inner] == 1:
      se(inner, 2)
    stack.pop()
  stack.pop()

print(co)

Submission status: Time Limit Exceeded

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

edge = {}
for i in xrange(N):
  edge[`i+1`] = {}

answers = set()
pre = set()

def add_edge(a, b):
  edge[a][b] = edge[b][a] = 1
  answers.add((min(a,b), max(a,b)))
  adds = []
  for n1 in edge[a].iterkeys():
    for n2 in edge[n1].iterkeys():
      if n2 != b and b not in edge[n2]:
        adds.append((n2, b))
    for n2 in edge[b].iterkeys():
      if n1 != n2 and n2 not in edge[n1]:
        adds.append((n1, n2))
  for n1 in edge[b].iterkeys():
    for n2 in edge[n1].iterkeys():
      if a != n2 and n2 not in edge[a]:
        adds.append((n2, a))
  for e in adds:
    add_edge(e[0], e[1])

for i in xrange(M):
  a, b = raw_input().split()
  pre.add((min(a,b), max(a,b)))
  if b not in edge[a]:
    add_edge(a, b)

print len(answers - pre)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
DIS = [[-1] * N for _ in range(N)]
ORGDIS = [[-1] * N for _ in range(N)]
for _ in range(M):
  a, b = map(int, input().split())
  DIS[a-1][b-1]=DIS[b-1][a-1]=ORGDIS[b-1][a-1]=ORGDIS[a-1][b-1]=1

stack = []

def se(li, stn):
  global stack
  global DIS
  for n in range(N):
    if DIS[li][n] == 1 and n not in stack:
      stack.append(n)
      if len(stack) == 4:
        DIS[stack[0]][n] = 1
        DIS[n][stack[0]] = 1
        stack.pop()
      else:
        se(n, len(stack))
        stack.pop()

for outer in range(N):
  stack.append(outer)
  for inner in range(N):
    stack.append(inner)
    if DIS[outer][inner] == 1:
      se(inner, 2)
    stack.pop()
  stack.pop()

co = 0

for o in range(N):
  for i in range(o + 1, N):
    if DIS[o][i] != ORGDIS[o][i]:
      co += 1

print(co)

Submission status: Time Limit Exceeded

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

edge = {}
for i in xrange(N):
  edge[`i+1`] = {}

answers = set()
pre = set()

def add_edge(a, b):
  if a == b or b in edge[a]:
    return
  edge[a][b] = edge[b][a] = 1
  answers.add((min(a,b), max(a,b)))
  adds = []
  for n1 in edge[a].iterkeys():
    for n2 in edge[n1].iterkeys():
      adds.append((n2, b))
    for n2 in edge[b].iterkeys():
      adds.append((n1, n2))
  for n1 in edge[b].iterkeys():
    for n2 in edge[n1].iterkeys():
      adds.append((n2, a))
  for e in adds:
    add_edge(e[0], e[1])

for i in xrange(M):
  a, b = raw_input().split()
  pre.add((min(a,b), max(a,b)))
  add_edge(a, b)

print len(answers - pre)

Submission status: Time Limit Exceeded

Solution code:
inputs = input().split()

N = int(inputs[0])
M = int(inputs[1])

p = [[] for x in range(N)]

for i in range(M):
    inputs = input().split()
    s = int(inputs[0]) - 1
    g = int(inputs[1]) - 1
    if g not in p[s]:
        p[s].append(g)
    if s not in p[g]:
        p[g].append(s)

ans = 0

for i in range(N):
    for v1 in p[i]:
        for v2 in p[v1]:
            for v3 in p[v2]:
                if v3 not in p[i] and v3 != i:
                    p[i].append(v3)
                    p[v3].append(i)
                    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def main():
    N, M = map(int, input().split())
    g = [set() for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        g[a-1].add(b-1)
        g[b-1].add(a-1)
    g2 = [set() for _ in range(N)]
    for a in range(N):
        for b in g[a]:
            for c in g[b]:
                if c != a:
                    g2[a].add(c)
                    g2[c].add(a)
    s = 0
    while True:
        ss = add_edge(N, g, g2)
        s += ss
        if not ss:
            print(s)
            break


def add_edge(N, g, g2):
    s = 0
    for a in range(N):
        ga = g[a]
        for c in list(g2[a]):
            for d in g[c]:
                if d != a and d not in ga:
                    s += 1
                    g2[a] |= g[d]
                    g2[d] |= g[a]
                    g[a].add(d)
                    g[d].add(a)
    return s

main()

Submission status: Memory Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,M = MI()
Graph = [[] for _ in range(N+1)]
for i in range(M):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)

# 二部グラフであれば、(色1で塗る頂点の個数)*(色-1で塗る頂点の個数)-M
# 二部グラフでなければ、N*(N-1)//2-M

colors = [0]*(N+1)


def dfs(v,color):  # 二部グラフ判定
    colors[v] = color
    for w in Graph[v]:
        if colors[w] == color:
            return False
        if colors[w] == 0 and not dfs(w,-color):
            return False
    return True


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

Submission status: Memory Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,M = MI()
Graph = [[] for _ in range(N+1)]
for i in range(M):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)

# 二部グラフであれば、(色1で塗る頂点の個数)*(色-1で塗る頂点の個数)-M
# 二部グラフでなければ、N*(N-1)//2-M

colors = [0]*(N+1)


def dfs(v,color):  # 二部グラフ判定
    colors[v] = color
    for w in Graph[v]:
        if colors[w] == color:
            return False
        if colors[w] == 0 and not dfs(w,-color):
            return False
    return True


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

Submission status: Memory Limit Exceeded

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n,m=map(int,input().split())
G=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
C=[-1]*n
C[0]=0
def dfs(x):
    for v in G[x]:
        if C[v]==C[x]:
            print(n*(n-1)//2-m)
            exit()
        if C[v]==-1:
            C[v]=1-C[x]
            dfs(v)
dfs(0)
q=C.count(0)
#print(C)
print(q*(n-q)-m)

Submission status: Memory Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10**6)

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: Memory Limit Exceeded

Solution code:
"""
奇数本で構成される閉路が存在している場合、全ての頂点同士を結ぶことができる
そうでない場合、、、
奇数本でつながっている辺同士は直接結ぶことができる＝グラフっは二部グラフとなっていて、
AグループとBグループのノード同士を結ぶことができる。
"""

import sys
sys.setrecursionlimit(200000)

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)

steps = [None]*(N+1)

def dfs(node,step):
    if steps[node] != None:
        if (step - steps[node])%2 == 1:
            return True
        else:
            return False
    else:
        steps[node] = step
        res = False
        for nx in edges[node]:
            res = res or dfs(nx,step+1)
        return res

res = dfs(1,0)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
if res:
    print(choose(N,2)-M)
else:
    for i in range(1,N+1):
        steps[i] %= 2
    odd = steps.count(1)
    even = N - odd
    print(odd*even-M)

Submission status: Memory Limit Exceeded

Solution code:
import sys
import copy
sys.setrecursionlimit(10**6)
def dfs(graph,v,col):
    color[v] = col
    for next_v in graph[v]:
        if color[next_v] != 0:
            if color[next_v] == col:
                return False
            continue
        if not dfs(graph,next_v,-col):
            return False
    return True
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
g = [[] for _ in range(n)]
color = [0]*n
for i in range(m):
    g[ab[i][0]-1].append(ab[i][1]-1)
    g[ab[i][1]-1].append(ab[i][0]-1)
if not dfs(g,0,1):
    print(n*(n-1)//2-m)
else:
    b = color.count(1)
    w = n-b
    print(b*w-m)

Submission status: Memory Limit Exceeded

Solution code:
import sys
import copy
sys.setrecursionlimit(10**7)
def dfs(graph,v,col):
    color[v] = col
    for next_v in graph[v]:
        if color[next_v] != 0:
            if color[next_v] == col:
                return False
            continue
        if not dfs(graph,next_v,-col):
            return False
    return True
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
g = [[] for _ in range(n)]
color = [0]*n
for i in range(m):
    g[ab[i][0]-1].append(ab[i][1]-1)
    g[ab[i][1]-1].append(ab[i][0]-1)
if not dfs(g,0,1):
    print(n*(n-1)//2-m)
else:
    b = color.count(1)
    w = n-b
    print(b*w-m)

Submission status: Memory Limit Exceeded

Solution code:
import sys
from collections import Counter, defaultdict
sys.setrecursionlimit(10**7)

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

for _ in range(M):
    a, b = list(map(int, input().split()))
    edge[a].add(b)
    edge[b].add(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 = len([c for c in colors if c == 1])
    cW = N - cB
    print(cB * cW - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Memory Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

[n,m]=i2()
e=[[] for i in range(n+1)]
for i in range(m):
 [x,y]=i2()
 e[x].append(y)
 e[y].append(x)

import sys
sys.setrecursionlimit(10**6)

d=[-1 for i in range(n+1)]
d[1]=0
s=0
def dfs(v):
   global s
   for i in range(len(e[v])):
      if d[e[v][i]]==-1:
         
         d[e[v][i]]=(d[v]+1)%2
         dfs(e[v][i])
      elif d[e[v][i]]!=(d[v]+1)%2:
          s=1
dfs(1)
if s==0:
  t=sum(d[1:])
  print(t*(n-t)-m)
else:
  print(int(n*(n-1)/2-m))

Submission status: Accepted

Solution code:
import sys,os,io
input = sys.stdin.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
N, M = map(int, input().split())
edge = [[] for _ 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)
from collections import deque
cnts = [-1]*N
cnts[0] = 0
d = deque([(0,1)])
while len(d)>0:
  v,cnt = d.popleft()
  for w in edge[v]:
    if cnts[w]==-1:
      cnts[w] = cnt
    elif (cnt-cnts[w])%2==1:
      print(N*(N-1)//2-M)
      break
    elif w==0 or cnts[w]%2==1:
      continue
    d.append((w,cnt+1))
  else:
    continue
  break
else:
  n = sum(map(lambda x:x%2==1, cnts))
  ans = n*(N-n)-M
  print(ans)

Submission status: Accepted

Solution code:
from collections import deque


class Graph:
    def __init__(self, n):
        self.n = n
        self.edge = [[] for _ in range(n)]
        self.color = [-1] * n

    def add_edge(self, node1, node2):
        self.edge[node1].append(node2)
        self.edge[node2].append(node1)

    def is_bipartite_graph(self):
        self.color = [-1] * self.n

        for i in range(self.n):
            if self.color[i] == -1:
                self.color[i] = 0
                d = deque([(i, 0)])

                while d:
                    node, c = d.pop()
                    for j in self.edge[node]:
                        if self.color[j] == -1:
                            self.color[j] = c ^ 1
                            d.append((j, self.color[j]))
                        elif self.color[j] == c:
                            return False

        return True


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

g = Graph(N)

for i in range(M):
    A, B = map(int, input().split())
    g.add_edge(A-1, B-1)

if g.is_bipartite_graph():
    zero = g.color.count(0)
    print(zero * (N - zero) - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
e=[[]for _ in range(n)]
for _ in range(m):
    ai,bi=map(int, input().split())
    ai-=1;bi-=1
    e[ai].append(bi);e[bi].append(ai)

nibu=[-1]*n
nibu[0]=0
from collections import deque,Counter
q=deque([0])
al=False
while q:
    u=q.popleft()
    for v in e[u]:
        if nibu[v]>=0:
            if nibu[u]==nibu[v]:
                al=True
                break
        else:
            nibu[v]=nibu[u]^1
            q.append(v)
        
    if al:
        break
if not al:
    c=Counter(nibu)
    ans=c[0]*c[1]
    ans-=m
else:
    ans=n*(n-1)//2-m
print(ans)

Submission status: Accepted

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

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

graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(graph, queue, color):
    is_bigraph = True
    while queue:
        current = queue.pop()

        for _next in graph[current]:
            if color[_next] != -1:
                if color[_next] == color[current]:
                    is_bigraph = False
            else:
                color[_next] = 1 - color[current]
                queue.append(_next)
    return is_bigraph

queue = [1]
color = [-1] + [-1] * n
color[1] = 0

if dfs(graph, queue, color):
    print(color.count(0) * color.count(1) - m)
else:
    print((n * (n - 1)) // 2 - m)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c
from collections import deque
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)
visit=[False]*N
color=[-1]*N
que=deque()

def nibu():
	que.append(0)
	color[0]=1

	while que:
		p=que.pop()
		visit[p]=True
		for q in G[p]:
			if visit[q] and color[q]==color[p]:
				return False
			elif not visit[q]:
				que.append(q)
				color[q]=(color[p]+1)%2
	return True

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

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c
from collections import deque
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)
visit=[False]*N
color=[-1]*N
que=deque()

def nibu():
	que.append(0)
	color[0]=True

	while que:
		p=que.pop()
		visit[p]=True
		for q in G[p]:
			if visit[q] and color[q]==color[p]:
				return False
			elif not visit[q]:
				que.append(q)
				color[q]=(color[p]+1)%2
	return True

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
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
next = deque([0])
Yes = True
while next:
    now = next.popleft()
    C = (color[now]+1)%2
    for a in connect[now]:
        if color[a] != -1:
            if color[a] != C:
                Yes = False
            continue
        color[a] = C
        next.append(a)
if Yes:
    s=sum(color)
    print(s*(n-s)-m)
else:
    print(n*(n-1)//2-m)

Submission status: Accepted

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
next = deque([0])
Yes = True
while next:
    now = next.popleft()
    for a in connect[now]:
        if color[a] != -1:
            if color[a] != (color[now]+1)%2:
                Yes = False
            continue
        color[a] = (color[now]+1)%2
        next.append(a)
if Yes:
    s=sum(color)
    print(s*(n-s)-m)
else:
    print(n*(n-1)//2-m)

Submission status: Accepted

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([0])
exploring =deque()
Yes = True
 
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 Yes:
    s=sum(color)
    print(s*(n-s)-m)
else:
    print(n*(n-1)//2-m)

Submission status: Accepted

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([0])
exploring =deque()
Yes = True
explored.add(0)
while next:
    now = next.popleft()
    for a in connect[now]:
        if color[a] != -1:
            if color[a] != (color[now]+1)%2:
                Yes = False
            continue
        color[a] = (color[now]+1)%2
        next.append(a)
        
        
    '''
    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 Yes:
    s=sum(color)
    print(s*(n-s)-m)
else:
    print(n*(n-1)//2-m)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from collections import deque
stack = deque([0])
colors = [-1]*N
colors[0] = 0

while stack:
    v = stack.pop()
    for nx in graph[v]:
        if colors[nx]==-1:
            colors[nx] = colors[v]^1
            stack.append(nx)
        else:
            if colors[nx]==colors[v]:
                print(N*(N-1)//2-M)
                exit()

ones = sum(colors)
zeros = N-ones
print(ones*zeros-M)

Submission status: Accepted

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

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

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=0
colors=[0]*(n+1)
is_bipartite=dfs(1,1)
if is_bipartite==True:
  ans=colors.count(1)*colors.count(-1)-m
else:
  ans=(n*(n-1))//2-m
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
graph=[[] for _ in range(N)]
color=[-1]*N
for _ in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

def steps(v,col=0):
    color[v]=col
    for nv in graph[v]:
        if color[nv]!=-1:
            if color[nv]==col: return False
            continue
        if not steps(nv,1-col): return False
    return True

flag=True
for v in range(N):
    if color[v]!=-1: continue
    if not steps(v): flag=False

if flag:
    tmp=color.count(0)
    print(tmp*(N-tmp)-M)
else:
    print(N*(N-1)//2-M)

Submission status: Accepted

Solution code:
# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)

N, M = map(int,input().split())
# 入力のつもり。esはよくある隣接リストで辺を表したもの。
#N = 5
#es = [[1,2,3],[0,2],[0,1],[0,4],[3]] # False
#es = [[1,3],[0,2],[1,3],[0,2,4],[3]] # True
es = [[] for i in range(N)]
for i in range(M):
  a, b = map(int,input().split())
  a, b = a-1, b-1
  es[a].append(b)
  es[b].append(a)
  
#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)] 

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int,readline().split())
data = list(map(int,read().split()))

links = [[] for _ in range(n+1)]
it = iter(data)
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

color = [-1] * (n+1)
color[1] = 0
stack = [1]
while(stack):
    i = stack.pop()
    ci = color[i]
    for j in links[i]:
        if(color[j] == -1):
            color[j] = 1-ci
            stack.append(j)
        else:
            if(color[j]==ci):
                ans = (n*(n-1))//2 - m
                print(ans)
                exit()

n0 = color.count(0)
n1 = color.count(1)
ans = n0*n1 - m
print(ans)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
import sys

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

Solution code:
# CODE FESTIVAL 2017 qualB C 3 Steps　
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]
for i in range(M):
    a,b=f()
    if not i:
        fa,fb=a,b
    G[a].append(b)
    G[b].append(a)
    
res=0
INF=10**9

def bfs(a):
    q=deque()
    q.append(a)
    d=[0]*(N+1)
    d[a]=1
    res=0
    while q:
        r=q.popleft()
        for nr in G[r]:
            if d[nr]==0:
                q.append(nr)
                d[nr]=-d[r]
            else:
                if d[nr]==d[r]:
                    return (False,[])
    return (True,d)
check=bfs(1)
if not check[0]:
    print((N*(N-1))//2-M)
else:
    print(check[1].count(1)*check[1].count(-1)-M)

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    
    tree = [[] for _ in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    judge = True
    dist = [0]*n
    already = [False]*n
    not_yet = deque([0])
    already[0] = True
    while not_yet:
        key = not_yet.popleft()
        for v in tree[key]:
            if already[v]:
                if dist[v] != (dist[key] + 1) % 2:
                    judge = False
                continue
            already[v] = True
            dist[v] = (dist[key] + 1) % 2
            not_yet.append(v)
    
    if judge:
        sub = sum(dist)
        ans = sub * (n - sub) - m
    else:
        ans = n * (n - 1) // 2 - m
    
    print(ans)
    
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
sys.setrecursionlimit(10**6)
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: Accepted

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        C = [0]*2
        C[0] = 1
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            color = 1^W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = color
                    que.append(ne)
                    C[color] += 1
                else:
                    if color!=W[ne]:
                        return n*(n-1)//2
        rep = C[0]*C[1]
        return rep
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    ans = bfs(N,0,V) - M
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
# 解説AC
# 二部グラフでないグラフの性質や，パスの長さを考察する

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

    def dfs(s):
        """
        二部グラフか判定
        """
        stack = [s]
        color = [-1]*N
        color[s] = 0
        while stack:
            v = stack.pop()
            for u in G[v]:
                if color[u] != -1:
                    if color[u] == color[v]:
                        # 二部グラフでない
                        return False, color
                    continue
                color[u] = color[v] ^ 1
                stack.append(u)
        return True, color

    is_bipartite, color = dfs(0)
    if is_bipartite:
        # 二部グラフである
        b = sum(color)
        w = N - b
        print(b*w - M)
    else:
        # 二部グラフでない
        # 完全グラフになるので，{}_N C_2 - (既に張られている辺の数)
        print(N*(N-1)//2 - M)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def bfs():
    q = deque([0])
    color = [0]*N
    color[0] = 1
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if color[nv]==0:
                color[nv] = -color[v]
                q.append(nv)
            else:
                if color[nv]==color[v]:
                    return [0]*N
        
    return color

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

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

color = bfs()

if color==[0]*N:
    print(N*(N-1)//2-M)
else:
    b = color.count(1)
    w = N-b
    print(b*w-M)