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: Wrong Answer

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)
    print(color.count(0) * color.count(1) - m)
else:
    print((n * (n - 1)) // 2 - m)

Submission status: Wrong Answer

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

color = [-1]*n
color[0] = 0
explored = {0}
next = deque(connect[0])
exploring =deque()
Yes = True
explored.add(0)
while next:
    now = next.popleft()
    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: Wrong Answer

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

color = [-1]*n
color[0] = 0
explored = {0}
next = deque(connect[0])
exploring =deque()
Yes = True
explored.add(0)
while next:
    now = next.popleft()
    exploring.extend(connect[now])
    explored.add(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)

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

Submission status: Wrong Answer

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

color = [-1]*n
color[0] = 0
explored = {0}
next = deque(connect[0])
exploring =deque()
Yes = True

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: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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)
#print(connect)
color= [-1]*n
color[0]=0
explored= {0}
next = deque(connect[0])
exploring =deque()
Yes = True
explored.add(0)
while next:
    now = next.popleft()
    exploring.extend(connect[now])
    while exploring:
        a=exploring.popleft()
        if color[a]==-1 or color[a]==(color[now]+1)%2:
            color[a]=(color[now]+1)%2
        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(int(n*(n-1)/2-m))

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
if n==2 or n==3:
    print(0)
    exit()

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)
#print(connect)
color= [-1]*n
color[0]=0
explored= {0}
next = deque(connect[0])
exploring =deque()
Yes = True
explored.add(0)
while next:
    now = next.popleft()
    exploring.extend(connect[now])
    while exploring:
        a=exploring.popleft()
        if color[a]==-1 or color[a]==(color[now]+1)%2:
            color[a]=(color[now]+1)%2
        else:
            Yes = False
        if a not in explored:
            next.append(a)
        explored.add(a)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
if n==2 or n==3:
    print(0)
    exit()

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)
#print(connect)
color= [-1]*n
color[0]=0
explored= {0}
next = deque(connect[0])
exploring =deque()
Yes = True
explored.add(0)
while next:
    now = next.popleft()
    exploring.extend(connect[now])
    while exploring:
        a=exploring.popleft()
        if color[a]==-1 or color[a]==(color[now]+1)%2:
            color[a]=(color[now]+1)%2
        else:
            Yes = False
        if a not in explored:
            next.append(a)
        explored.add(a)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
if n==2 or n==3:
    print(0)
    exit()

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)
#print(connect)
color= [-1]*n
color[0]=0
explored= {0}
next = deque(connect[0])
exploring =deque()
Yes = True
explored.add(0)
while next:
    now = next.popleft()
    exploring.extend(connect[now])
    while exploring:
        a=exploring.popleft()
        if color[a]==-1 or color[a]==(color[now]+1)%2:
            color[a]=(color[now]+1)%2
        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(int(n*(n-1)/2-m))

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
if n==2 or n==3:
    print(0)
    exit()

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)
#print(connect)
color= [-1]*n
color[0]=0
explored= {0}
next = deque(connect[0])
exploring =deque()
Yes = True
while next:
    now = next.popleft()
    explored.add(now)
    exploring.extend(connect[now])
    while exploring:
        a=exploring.popleft()
        if color[a]==-1 or color[a]==(color[now]+1)%2:
            color[a]=(color[now]+1)%2
        else:
            Yes = False
        if a not in explored:
            next.append(a)
            

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import collections

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=[-1]*(n+1)
for i in range(1,n+1):
  if colors[i]!=-1:
    continue
  is_bipartite=True
  nodes=0
  black=0
  white=0
  q=collections.deque()
  q.append((i,0))
  while len(q)!=0:
    v,color=q.popleft()
    if colors[v]!=-1 and colors[v]!=color:
      is_bipartite=False
      continue
    colors[v]=color
    nodes+=1
    if color==0:
      black+=1
    elif color==1:
      white+=1
    for u in g[v]:
      if colors[u]==-1:
        q.append((u,color^1))
  if is_bipartite==True:
    ans+=black*white
  else:
    ans+=(nodes*(nodes-1))//2
print(ans-m)

Submission status: Wrong Answer

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(0)
ans = n0*n1 - m
print(ans)

Submission status: Wrong Answer

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: Wrong Answer

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

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


count = 0
for i in range(N):
    queue = deque()
    queue.append(i)
    visited = [False for _ in range(N)]
    dist = [0 for _ in range(N)]
    dist[i] = 0
    start = i
    candidate = []

    while queue:
        now = queue.popleft()

        if dist[now] == 3:
            if start not in graph[now]:
                candidate.append(now)
                count += 1
            continue

        for adj in graph[now]:
            if visited[adj]:
                continue

            dist[adj] = dist[now] + 1
            visited[adj] = True
            queue.append(adj)

    for v in candidate:
        graph[v].append(start)
        graph[start].append(v)

print(count)

Submission status: Wrong Answer

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

isPer=not bfs(1)
if isPer:
    print((N*(N-1))//2-M)
else:
    print(((N//2)**2)//1-M)

Submission status: Wrong Answer

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=[INF]*(N+1)
    d[a]=0
    res=0
    while q:
        r=q.popleft()
        for nr in G[r]:
            if d[nr]==INF:
                q.append(nr)
                d[nr]=(d[r]+1)%2
                res+=1
    return d

d=bfs(1)
isPer=False
for i in G[1]:
    if d[i]==0:
        isPer=True
        break
if isPer:
    print(N*N-M)
else:
    print(((N//2)**2)//1-M)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
d=[-1]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([(1,0)])
d[1]=0
a=0
while q:
  now,par=q.popleft()
  for to in e[now]:
    if to==par:continue
    if d[to]==-1:
      d[to]=(d[now]+1)%2
      a+=1
      q.append((to,now))
    elif d[to]!=d[now]%2:a+=1
    else:
      print(n*(n-1)//2-m)
      exit()
p=sum(d)+1
print(p*(n-p)-a)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
d=[-1]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([1])
d[1]=0
a=0
while q:
  now=q.popleft()
  for to in e[now]:
    if d[to]==-1:
      d[to]=(d[now]+1)%2
      b+=1
      q.append(to)
    elif d[to]!=d[now]%2:a+=1
p=sum(d)+1
print(p**2-a)

Submission status: Wrong Answer

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

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)
#print(edge)
colors = [0 for i in range(N)]

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

#print(dfs(0,1),colors)
if dfs(0,1) == 1: #もし二部グラフなら
  one = 0; zero = 0
  for x in colors:
    if x == 1:
      one += 1
    else:
      zero += 1
  ans = one*zero-M
else:
  ans = N*(N-1)//2-M
print(ans)

Submission status: Wrong Answer

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

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)
#print(edge)
colors = [0 for i in range(N)]

def dfs(v,color):
  colors[v] = color
  for u in edge[v]:
    if colors[u] == color:
      return -1
    elif colors[u] == 0:
      dfs(u,-1*color)
  return 1

#print(dfs(0,1))
if dfs(0,1) == 1: #もし二部グラフなら
  one = 0; zero = 0
  for x in colors:
    if x == 1:
      one += 1
    else:
      zero += 1
  ans = one*zero-M
else:
  ans = N*(N-1)//2-M
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
from copy import deepcopy
def main():
    def dfs(node, dis, base):
        # baseとなる辺から２つめの頂点にきたら、隣接頂点ごとにbaseとの辺があるかチェック。ないならtmpに+1。
        if dis == 2:
            tmp = 0
            for adjnode in edges[node]:
                if adjnode not in seen:
                    seen.add(adjnode)
                    if base not in edges[adjnode]:
                        tmp += 1
                        edges[base].append(adjnode)
            return tmp
        else:
            tmp = 0
            for adjnode in edges[node]:
                if adjnode not in seen:
                    seen.add(adjnode)
                    tmp += dfs(adjnode, dis + 1, base)
            return tmp

    # input
    n, m = map(int, input().split())
    edges = {e: [] for e in range(n)}
    m = map(int, read().split())
    for a, b in zip(m, m):
        a -= 1
        b -= 1
        edges[a].append(b)
        edges[b].append(a)
    edges_o = deepcopy(edges)
    # process
    r = 0
    for i0 in range(n):
        rt = 0
        edges = deepcopy(edges_o)
        for i1 in range(n):
            t = (i0 + i1) % n
            seen = set()
            seen.add(t)
            rt += dfs(t, 0, t)
        r = max(r, rt)

    # output
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n,m=MI()

	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	#print(G)

	D=[-1]*(n+1)


	Q=deque()
	Q.append([1,0])

	#print(Q)

	f=0

	while Q:
		#print(Q)
		now,d=Q.pop()
		D[now]=d
		for nx in G[now]:
			if D[nx]==-1:
				Q.append([nx,d+1])
			elif D[nx]%2!=d%2:
				continue
			else:
				f=1
				break


	if f==1:
		ans=(n*(n-1))//2
	else:
		ans=(n//2)**2+(n//2)*(n%2)

	ans-=m

	print(ans)

















if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n,m=MI()

	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	#print(G)

	D=[-1]*(n+1)


	Q=deque()
	Q.append([1,0])

	#print(Q)

	f=0

	while Q:
		#print(Q)
		now,d=Q.popleft()
		D[now]=d
		for nx in G[now]:
			if D[nx]==-1:
				Q.append([nx,d+1])
			elif D[nx]%2!=d%2:
				continue
			else:
				f=1
				break


	if f==1:
		ans=(n*(n-1))//2
	else:
		ans=(n//2+n%2)*(n//2)+5

	ans-=m

	print(ans)

















if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n,m=MI()

	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	#print(G)

	D=[-1]*(n+1)


	Q=deque()
	Q.append([1,0])

	#print(Q)

	f=0

	while Q:
		#print(Q)
		now,d=Q.popleft()
		D[now]=d
		for nx in G[now]:
			if D[nx]==-1:
				Q.append([nx,d+1])
			elif D[nx]%2!=d%2:
				continue
			else:
				f=1
				break


	if f==1:
		ans=(n*(n-1))//2+5
	else:
		ans=(n//2+n%2)*(n//2)

	ans-=m

	print(ans)

















if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n,m=MI()

	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	#print(G)

	D=[-1]*(n+1)


	Q=deque()
	Q.append([1,0])

	#print(Q)

	f=0

	while Q:
		#print(Q)
		now,d=Q.popleft()
		D[now]=d
		for nx in G[now]:
			if D[nx]==-1:
				Q.append([nx,d+1])
			elif D[nx]%2!=d%2:
				continue
			else:
				f=1
				break


	if f==1:
		ans=(n*(n-1))//2
	else:
		ans=(n//2+n%2)*(n//2)

	ans-=m

	print(ans)

















if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n,m=MI()

	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	#print(G)

	D=[-1]*(n+1)


	Q=deque()
	Q.append([1,0])

	#print(Q)

	f=0

	while Q:
		#print(Q)
		now,d=Q.popleft()
		D[now]=d
		for nx in G[now]:
			if D[nx]==-1:
				Q.append([nx,d+1])
			elif D[nx]%2!=d%2:
				continue
			else:
				f=1
				break


	if f==1:
		ans=n*(n-1)//2
	else:
		ans=(n//2+n%2)*(n//2)

	ans-=m

	print(ans)

















if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n,m=MI()

	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	#print(G)

	D=[-1]*(n+1)


	Q=deque()
	Q.append([1,0])

	#print(Q)

	f=0

	while Q:
		#print(Q)
		now,d=Q.popleft()
		D[now]=d
		for nx in G[now]:
			if D[nx]==-1:
				Q.append([nx,d+1])
			elif D[nx]%2!=d%2:
				continue
			else:
				f=1
				break


	if f==1:
		ans=n*(n-1)//2
	else:
		ans=(n//2+n%2)*n//2

	ans-=m

	print(ans)

















if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
"""
奇数本の辺で成り立つ閉路があれば、全ての頂点同士を1本の辺で結ぶことができる。
そうでない場合は、奇数本の辺をたどってたどり着ける頂点同士は全て1本の辺で結ぶことができる。
奇数本の閉路があるかどうかを、どうやって判定するか？
二部グラフ判定を行う。
二部グラフ判定ってどうやるんだっけ？→となりのノードに違う色をつけていって、矛盾がなければ二部グラフ。矛盾があれば二部グラフじゃない。
"""
import sys
sys.setrecursionlimit(200000)
def judgeBiGragh(edges):
    n = len(edges)
    colors = [-1]*(n+1)
    def paint(v,c):
        if colors[v] == -1:
            colors[v] = c
            nxC = (c+1)%2
            for nxV in edges[v]:
                result = paint(nxV,nxC)
                if result == False:
                    return result
        else:
            if colors[v] != c:
                return False
        return True
    return paint(1,0)

N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
if judgeBiGragh(edges):
    ans = (N//2)*(N-N//2) - M
else:
    ans = choose(N,2)-M

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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: Wrong Answer

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)
is_bipartite = True
colors = [None] * (N+1)
colors[0] = 1

cur_c = 0
q = [1]
while q:
  l = len(q)
  for _ in range(l):
    cur_node = q.pop(0)
    if visited[cur_node]: continue
    visited[cur_node] = True

    for nei in adj_list[cur_node]:
      if visited[nei]: continue
      if nei in q:
        is_bipartite = False
        break
      else:
        colors[nei-1] = cur_c
        q.append(nei)

  if not is_bipartite:
    break
  else:
    cur_c = 1 if cur_c==0 else 0

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

Submission status: Wrong Answer

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):
        if colors[n]!=-1 and colors[n]!=c:
            print(choose(N,2)-M)
            exit()
        else:
            colors[n] = c
            for nx in edges[n]:
                if nx != p:
                    paint(nx,n,(c+1)%2)

    def choose(n,k):
        import math
        return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
    
    ans = colors.count(0)*(N-colors.count(0))-M

    print(ans)

main()

Submission status: Wrong Answer

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

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: Wrong Answer

Solution code:
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)


def judgeBiGragh(edges):
    n = len(edges)
    colors = [-1]*(n+1)
    def paint(v,c):
        if colors[v] == -1:
            colors[v] = c
            nxC = (c+1)%2
            for nxV in edges[v]:
                result = paint(nxV,nxC)
                if result == False:
                    return result
        else:
            if colors[v] != c:
                return False
        return True
    return paint(1,0)

def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))

if judgeBiGragh(edges):
    print(N//2 * (N-N//2) - M)
else:
    print(choose(N,2)-M)