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

sys.setrecursionlimit(1000000)


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


def main():
    n, m = map(int, input().split())

    g = {}
    for i in range(m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a-1, set())
        dic_a.add(b-1)
        dic_b = g.setdefault(b-1, set())
        dic_b.add(a-1)

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


main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
s=[[]for i in range(n+1)]
c=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
def dfs(v,t):
    c[v]=t
    # print('start :'+str(c))
    for i in s[v]:
        if c[i]==t:
            return False
        if c[i]==0:
            dfs(i,-t)
            # return False
    else:
        return True
if dfs(1,1):
    q=c.count(1)
    print((n-q)*q-m)
else:
    print((n*(n-1)//2)-m)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
s=[[]for i in range(n+1)]
c=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
def dfs(v,t):
    c[v]=t
    print('start :'+str(c))
    for i in s[v]:
        if c[i]==t:
            return False
        if c[i]==0:
            dfs(i,-t)
            # return False
    else:
        return True
if dfs(1,1):
    q=c.count(1)
    print((n-q)*q-m)
else:
    print((n*(n-1)//2)-m)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
import sys
sys.setrecursionlimit(10**6)
dep=[-1 for i in range(n+1)]
color=[0 for i in range(n+1)]
def dfs(s,d,c):
    dep[s]=d
    color[s]=c
    for i in edge[s]:
        if dep[i]==-1:
            dfs(i,d+1,-c)
        else:
            if color[i]==c:
                return False
if dfs(1,0,1)==False:
    print(n*(n-1)//2-m)
else:
    print(color.count(1)*color.count(-1)-m)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
edg = [[] for i in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  edg[a].append(b)
  edg[b].append(a)
  
check1 = [0] * n
check0 = [0] * n

from collections import deque

q = deque()
q.append((0,1))
check0[0] = 1

while q:
  p,t = q.pop()
  for e in edg[p]:
    if t:
      if check1[e]:continue
      check1[e] = 1
      q.appendleft((e,0))
    else:
      if check0[e]:continue
      check0[e] = 1
      q.appendleft((e,1))
ans = 0
sc0 = sum(check0)
sc1 = sum(check1)
for i in range(n):
  if check0[i]:
    if check1[i]:
      ans += n - 1
    else:
      ans += sc0
  else:
      ans += sc1
print(ans//2 - m)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
edg = [[] for i in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  edg[a].append(b)
  edg[b].append(a)
  
check1 = [0] * n
check0 = [0] * n

from collections import deque

q = deque()
q.append((0,1))
check0[0] = 1

while q:
  p,t = q.pop()
  for e in edg[p]:
    if t:
      if check1[e]:continue
      check1[e] = 1
      q.appendleft((e,0))
    else:
      if check0[e]:continue
      check0[e] = 1
      q.appendleft((e,1))
ans = 0
sc0 = sum(check0)
sc1 = sum(check1)
for i in range(n):
  if check0[i]:
    if check1[i]:
      ans += n - 1 - len(edg[i])
    else:
      ans += sc0 - len(edg[i])
  else:
      ans += sc1 - len(edg[i])
print(ans//2)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
edg = [[] for i in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  edg[a].append(b)
  edg[b].append(a)
  
check1 = [0] * n
check0 = [0] * n

from collections import deque

q = deque()
q.append((0,1))
check0[0] = 1

while q:
  p,t = q.pop()
  for e in edg[p]:
    if t:
      if check1[e]:continue
      check1[e] = 1
      q.appendleft((e,0))
    else:
      if check0[e]:continue
      check0[e] = 1
      q.appendleft((e,1))
ans = 0
sc0 = sum(check0)
sc1 = sum(check1)
for i in range(n):
  if check0[e]:
    if check1[e]:
      ans += n - 1 - len(edg[e])
    else:
      ans += sc0 - len(edg[e])
  else:
      ans += sc1 - len(edg[e])
print(ans//2)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
edg = [[] for i in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  edg[a].append(b)
  edg[b].append(a)
  
check1 = [0] * n
check0 = [0] * n

from collections import deque

q = deque()
q.append((0,1))
check0[0] = 1

while q:
  p,t = q.pop()
  for e in edg[p]:
    if t:
      if check1[e]:continue
      check1[e] = 1
      q.appendleft((e,0))
    else:
      if check0[e]:continue
      check0[e] = 1
      q.appendleft((e,1))
ans = 0
sc0 = sum(check0)
sc1 = sum(check1)
for i in range(n):
  if check0[e]:
    if check1[e]:
      ans += n - 1
    else:
      ans += sc0
  else:
      ans += sc1
print(ans//2-m)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
edg = [[] for i in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  edg[a].append(b)
  edg[b].append(a)
  
check1 = [0] * n
check0 = [0] * n

from collections import deque

q = deque()
q.append((0,1))
check0[0] = 1

while q:
  p,t = q.pop()
  for e in edg[p]:
    if t:
      if check1[e]:continue
      check1[e] = 1
      q.appendleft((e,0))
    else:
      if check0[e]:continue
      check0[e] = 1
      q.appendleft((e,1))
ans = 0
sc0 = sum(check0)
sc1 = sum(check1)
for i in range(n):
  if check0[e]:
    if check1[e]:
      ans += n - 1
    else:
      ans += sc0
  else:
    if check1[e]:
      ans += n - 1
    else:
      ans += sc1
print(ans//2-m)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
edg = [[] for i in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  edg[a].append(b)
  edg[b].append(a)
  
check1 = [0] * n
check0 = [0] * n

from collections import deque

q = deque()
q.append((0,1))
check0[0] = 1

while q:
  p,t = q.pop()
  for e in edg[p]:
    if t:
      if check1[e]:continue
      check1[e] = 1
      q.appendleft((e,0))
    else:
      if check0[e]:continue
      check0[e] = 1
      q.appendleft((e,1))

print(sum(check1)*sum(check0)-m)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from sys import stdin
def main():
    N,M = map(int,stdin.readline().split())
    edge = defaultdict(list)
    ans = set()
    for _ in range(M):
        a,b = map(int,stdin.readline().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    for u in range(N):
        for v in edge[u]:
            if v == u:continue
            for w in edge[v]:
                if w in edge[u] or w == u:continue
                for e in edge[w]:
                    if e == w:continue
                    if (e,u) in ans or (u,e) in ans:continue
                    if e in edge[u]:continue
                    if e == u:continue
                    ans.add((e,u))
                    edge[u].append(e)
    print(len(ans))
    #print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def dfs(v, color):
    colors[v] = color
    for to in g[v]:
        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())

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

colors = [0]*n

ans = -m
if dfs(0,1):
  b = sum(colors)//2
  w = n-b
  ans += b*w
else:
  ans += n*(n-1)//2
print(ans)

Submission status: Wrong Answer

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
bl = 0
for x in range(1, N + 1):
  for y in e[x]:
    dy = d[y] % 2
    c[x][dy] = 1
  wh += c[x][0]
  bl += c[x][1]
res = 0
for x in range(1, N + 1):
  res += (wh - c[x][0]) * c[x][1]
  res += (bl - c[x][1]) * c[x][0]
print(res // 2 - M)

Submission status: Wrong Answer

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

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

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


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

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

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

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

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

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

        self.colors[u] = self.BLACK

        return True


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

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

print(ans)

Submission status: Wrong Answer

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

def dfs(v, r, d):
    b = 0
    w = 0
    if d % 2 == 0:
        b += 1
    else:
        w += 1
    for u in E[v]:
        if u == r:
            continue
        tmp_b, tmp_w = dfs(u, v, (d + 1) % 2)
        b += tmp_b
        w += tmp_w
    return b, w

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

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

if M != N - 1:
    print(N * (N - 1) // 2 - M)
else:
    b, w = dfs(0, -1, 0)
    print(b * w - M)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(n-1):
  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(max(0,c*(n-c)-m))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(n-1):
  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: Wrong Answer

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((N//2)**2 - M)
else:
    print(N*(N-1)//2 - M)
#29

Submission status: Wrong Answer

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
	for u in G[v]:
		if color[u] == c:
			return False
		if color[u] != -1:
			continue
		dfs(u, 1-c)
	return True

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

Submission status: Wrong Answer

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
	for u in G[v]:
		if color[u] != -1:
			if color[u] == c:
				return True
			continue
		return dfs(u, 1-c)

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

Submission status: Wrong Answer

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
	for u in G[v]:
		if color[u] != -1:
			if color[u] == c:
				return False
			continue
		dfs(u, 1-c)
	return True

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 bin_or_not:
    w =  w_or_b.count(0)
    b = w_or_b.count(1)
    ans = w*b - M
print(ans)

Submission status: Wrong Answer

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 = 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 bin_or_not:
    w =  w_or_b.count(0)
    b = w_or_b.count(1)
    ans = w*b - M
print(ans)

Submission status: Wrong Answer

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 = not(w_or_b[x] and 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 bin_or_not:
    ans = w_or_b.count(0)*w_or_b.count(1) - M
print(ans)

Submission status: Wrong Answer

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):
    M=max([v[nb] for nb in g[i]])
    mm=max([v[nb] for nb in g[i]])
    if M!=mm or M==v[i]:
        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: Wrong Answer

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):
    M=max([v[nb] for nb in g[i]])
    mm=max([v[nb] for nb in g[i]])
    if M!=mm:
        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: Wrong Answer

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)

#show(v)
flg=True
for i in range(n):
    M=max([v[nb] for nb in g[i]])
    mm=max([v[nb] for nb in g[i]])
    if M!=mm:
        flg=False
        break

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

Submission status: Wrong Answer

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)

#show(v)
flg=True
for i in range(n):
    M=max([v[nb] for nb in g[i]])
    m=max([v[nb] for nb in g[i]])
    if M!=m:
        flg=False
        break

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    bfs = [0]*n
    bfs[0] = 1
    q = deque([0])
    while q:
        x = q.popleft()
        if bfs[x] == 1:
            nb = 2
        elif bfs[x] == 2:
            nb = 1
        else:
            nb = 3
        for y in v[x]:
            if not bfs[y]:
                q.append(y)
            bfs[y] |= nb
    ans = 0
    f = [0]*3
    for b in bfs:
        if b == 1:
            ans += f[0]
            f[1] += 1
            f[2] += 1
        elif b == 2:
            ans += f[1]
            f[0] += 1
            f[2] += 1
        else:
            ans += f[2]
            f[0] += 1
            f[1] += 1
            f[2] += 1
    print(ans-m)
    return


#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

def Dfs(G, s, v, b_v, cnt = 0):
    if cnt == 3:
        if s != v and not (v in G[s]):
            seen[v] = 1
        return
    for next_v in G[v]:
        if next_v == b_v:
            continue
        Dfs(G, s, next_v, v, cnt+1)

input = sys.stdin.readline
n, m = map(int, input().split())
ab = [[0, 0]] + [list(map(int, input().split())) for i in range(m)]
g = [set() for i in range(n+1)]

for i in range(1, m+1):
    g[ab[i][0]].add(ab[i][1])
    g[ab[i][1]].add(ab[i][0])
ans = 0
seen = [-1 for i in range(n+1)]
for v in range(1, n+1):
    Dfs(g, v, v, v)
    for i in range(1, n+1):
        if seen[i] == 1: 
            g[v].add(i)
            g[i].add(v)
            ans += 1
            seen[i] = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

def Dfs(G, s, v, b_v, cnt = 0):
    if cnt == 3:
        if s != v and not (v in G[s]):
            seen[v] = 1
        return
    for next_v in G[v]:
        if next_v == v:
            continue
        Dfs(G, s, next_v, v, cnt+1)

input = sys.stdin.readline
n, m = map(int, input().split())
ab = [[0, 0]] + [list(map(int, input().split())) for i in range(m)]
g = [set() for i in range(n+1)]

for i in range(1, m+1):
    g[ab[i][0]].add(ab[i][1])
    g[ab[i][1]].add(ab[i][0])
ans = 0
seen = [-1 for i in range(n+1)]
for v in range(1, n+1):
    Dfs(g, v, v, v)
    for i in range(1, n+1):
        if seen[i] == 1: 
            g[v].add(i)
            g[i].add(v)
            ans += 1
            seen[i] = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)
def main():
    def Dfs(G, s, v, cnt = 0):
        if cnt == 3:
            if v != s and not (v in G[s]):
                seen[v] = 1
            return
        for next_v in G[v]:
            Dfs(G, s, next_v, cnt+1)

    input = sys.stdin.readline
    n, m = map(int, input().split())
    ab = [[0, 0]] + [list(map(int, input().split())) for i in range(m)]
    g = [set() for i in range(n+1)]

    for i in range(1, m+1):
       g[ab[i][0]].add(ab[i][1])
       g[ab[i][1]].add(ab[i][0])
    ans = 0
    limit = ((n*(n-1))/2) - m
    seen = [-1 for i in range(n+1)]
    for v in range(1, n+1):
        Dfs(g, v, v)
        for i in range(1, n+1):
            if seen[i] == 1: 
                g[v].add(i)
                g[i].add(v)
                ans += 1
                seen[i] = -1
        if ans >= limit:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

def Dfs(G, s, v, cnt = 0):
    if cnt == 3:
        if v != s and not (v in G[s]):
            seen[v] = 1
        return
    for next_v in G[v]:
        Dfs(G, s, next_v, cnt+1)

input = sys.stdin.readline
n, m = map(int, input().split())
ab = [[0, 0]] + [list(map(int, input().split())) for i in range(m)]
g = [set() for i in range(n+1)]

for i in range(1, m+1):
    g[ab[i][0]].add(ab[i][1])
    g[ab[i][1]].add(ab[i][0])
ans = 0

seen = [-1 for i in range(n+1)]
for v in range(1, n+1):
    Dfs(g, v, v)
    for i in range(1, n+1):
        if seen[i] == 1: 
            g[v].add(i)
            g[i].add(v)
            ans += 1
            seen[i] = -1
print(ans)