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:
from collections import Counter
import sys
sys.setrecursionlimit(1000000)

global color 
global adlist

def make_adlist(N, AB):
  global adlist
  for a, b in AB:
    adlist[a] += [b]
    adlist[b] += [a]

def dfs(v, c):
  color[v] = c
  for u in adlist[v]:
    if color[u] == c:
      return False
    if color[u] == 0:
      return dfs(u, -c)
  return True

def main():
  global color 
  global adlist
  N, M = map(int, input().split())
  AB = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
  color = [0 for _ in range(N)]
  adlist = [[] for _ in range(N)]
  make_adlist(N, AB)
  if dfs(0, 1):
    B = color.count(-1)
    W = color.count(1)
    print(B*W-M)
  else:
    print(N*(N-1)//2-M)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

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

seen = [0] * (N+1)
que = deque()
que.append(1)
seen[1] = 1
finish = 0
flag = 0
while que:
    if finish == 1:
        flag = 1
        break
    v = que.pop()
    for u in adj[v]:
        if seen[u] == 0:
            que.append(u)
            seen[u] = seen[v] * -1
        else:
            if seen[u] == seen[v]:
                finish = 1
                break

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,c):
    color[v] = c

    for i in a[v]:
        if color[i] != -1:
            if color[i] == c:return False
            continue
        if dfs(i,1-c) == False:return False

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

for i in range(m):
    x,y= map(int,input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)
if dfs(0,0) == False:
    print(n*(n-1)//2-m)
else:print((n-n//2)*(n//2) - m)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(v,c):
    color[v] = c

    for i in a[v]:
        if color[i] != -1:
            if color[i] == c:return False
            continue
        if dfs(i,1-c) == False:return False

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

for i in range(m):
    x,y= map(int,input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)
print(a)
if dfs(0,0) == False:
    print(n*(n-1)//2-m)
else:print((n-n//2)*(n//2) - m)

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()

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

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

que = deque([])
que.append(0)
graph2[0] = 0
nibu = 1

num01 = dict()
num01[0] = 1
num01[1] = 0

while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if graph2[edge] == -1:
			graph2[edge] = (graph2[node] + 1) % 2
			que.append(edge)
			num01[graph2[edge]] += 1
		elif graph2[node] == graph2[edge]:
			nibu = 0

if nibu == 0:
	print(N*(N-1)//2 - M)
else:
	print(num01[0]*num01[1] - 1)

Submission status: Wrong Answer

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

n, m = map(int, (input().split()))
dic = defaultdict(list)
seen = [-1] * (n+1)

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


def dfs(v, todo, color):
    if seen[v] == color:  # 同じ色で戻ってくる = 偶サイクル
        return
    elif seen[v] == 1-color:  # 異なる色で戻ってくる = 奇サイクル
        return False

    seen[v] = color
    for new_v in todo:
        new_todo = dic[new_v]
        dfs(new_v, new_todo, 1-color)


if dfs(1, dic[1], 0) is False:
    ans = 0.5 * n * (n-1) - m

else:
    black = seen.count(0)
    white = seen.count(1)
    ans = black * white - m

print(int(ans))

Submission status: Wrong Answer

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

n, m = map(int, (input().split()))
dic = defaultdict(list)
seen = [-1] * (n+1)

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


def dfs(v, todo, color):
    if seen[v] == color:  # 同じ色で戻ってくる = 偶サイクル
        return
    elif seen[v] == 1-color:  # 異なる色で戻ってくる = 奇サイクル
        return False

    seen[v] = color
    for new_v in todo:
        new_todo = []
        new_todo += dic[new_v]
        new_todo.remove(v)
        new_color = 1 - color
        return dfs(new_v, new_todo, new_color)


if dfs(1, dic[1], 0) is False:
    ans = 0.5 * n * (n-1) - m

else:
    black = seen.count(0)
    white = seen.count(1)
    ans = black * white - m

print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from operator import mul
from functools import reduce

def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


def dfs(v, cur):
    color[v] = cur
    
    for next_v in Graph[v]:
        if color[next_v] != -1:
            if color[next_v] != cur:
                continue
            else:
                return False
        elif not dfs(next_v, 1-cur):
            return False
    return True
        


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

for i in AB:
    Graph[i[0]-1].append(i[1]-1)
    Graph[i[1]-1].append(i[0]-1)

if dfs(0, 0):
    print(max(0, (N//2)*(N-N//2)-M))
else:
    print(max(0, comb(N, 2)-M))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from operator import mul
from functools import reduce

def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


def dfs(v, cur):
    color[v] = cur
    
    for next_v in Graph[v]:
        if color[next_v] != -1:
            if color[next_v] != cur:
                continue
            else:
                return False
        elif not dfs(next_v, 1-cur):
            return False
    return True
        


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

for i in AB:
    Graph[i[0]-1].append(i[1]-1)
    Graph[i[1]-1].append(i[0]-1)

if dfs(0, 0):
    print((N//2)*(N-N//2)-M)
else:
    print(comb(N, 2)-M)

Submission status: Wrong Answer

Solution code:
def bipartite():
    color = {v: None for v in V}
    stack = [(V[0], 0)]
    parts = {0: [], 1:[]}
    while stack:
        v, c = stack.pop()
        color[v] = c
        parts[c].append(v)
        for u in E[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    return (parts[0], parts[1])
            
N, M = map(int, input().split())
V = range(1, N+1)
E = {v: [] for v in V}
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
p1, p2 = bipartite()
if p1 is None:
    print(N * (N-1) // 2 - M)
else:
    print(len(p1) * len(p2) - M)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if n % 2 ==1:
    print(((n*(n-1))//2)-m)
else:
    print((n+n//2)-m)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = map(int, input().split())
 
# 隣接リスト
l = [[] for i in range(N+1)] 
for i in range(M):
    ab = list(map(int, input().split()))
    a = min(ab)
    b = max(ab)
    l[a].append(b)

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}

def func(v,c):
    if nodes_color[v] == c:
        return True
    if nodes_color[v] == -c:
        return False
    
    if nodes_color[v] == 0:
        nodes_color[v] = c
    for node in l[v]:
        if not func(node, -c):
            return False
    
    return True

# 連結なので下記は不用。
def bipartite_graph_check():
    for i in range(1,N+1):
        if nodes_color[i] == 0:
            if not func(i,1):
                return False
    return True

if bipartite_graph_check():
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = map(int, input().split())
 
# 隣接リスト
l = [[] for i in range(N+1)] 
for i in range(M):
    ab = list(map(int, input().split()))
    a = min(ab)
    b = max(ab)
    l[a].append(b)

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}

def func(v,c):
    print(v,c)
    if nodes_color[v] == c:
        return True
    if nodes_color[v] == -c:
        return False
    
    if nodes_color[v] == 0:
        nodes_color[v] = c
    for node in l[v]:
        if not func(node, -c):
            return False
    
    return True

# 連結なので下記は不用。
def bipartite_graph_check():
    for i in range(1,N+1):
        if nodes_color[i] == 0:
            if not func(i,1):
                return False
    return True

if bipartite_graph_check():
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))

Submission status: Wrong Answer

Solution code:
# 二部グラフ > 完全二部グラフになるまで線を追加
# 二部グラフでない > 全ての頂点の間に線を追加

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

# 隣接リスト
l = [[] for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a-=1
    b-=1
    l[a].append(b)

# 二部グラフ判定
nibu = True
stack = [0]
col = [-1 for i in range(n)]
col[0]=0
visited = [0 for i in range(n)]
visited[0]=1
flag = False
while stack:
    p = stack.pop()
    for x in l[p]:
        if visited[x]==0:
            stack.append(x)
            visited[x]=1
            if col[p]==0:
                col[x]=1
            else:
                col[x]=0
        else:
            if col[x]==col[p]:
                nibu = False
                flag = True
                break
    if flag:
        break

if nibu:
    print(col.count(1)*col.count(0)-m)
else:
    print(n*(n-1)//2-m)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())

# 隣接リスト
l = [[] for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a-=1
    b-=1
    l[a].append(b)

# 二部グラフ判定
nibu = True
stack = [0]
col = [-1 for i in range(n)]
col[0]=0
visited = [0 for i in range(n)]
visited[0]=0
flag = False
while stack:
    p = stack.pop()
    for x in l[p]:
        if visited[x]==0:
            stack.append(x)
            visited[x]=1
            if col[p]==0:
                col[x]=1
            else:
                col[x]=0
        else:
            if col[x]==col[p]:
                nibu = False
                flag = True
                break
    if flag:
        break

if nibu:
    print(col.count(1)*col.count(0)-m)
else:
    print(n*(n-1)//2-m)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [[] for i in range(N)]
for m in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

color = [-1 for i in range(N)]
visits = [False for i in range(N)]
paths = deque()


def Bipartial():
    paths.append(0)
    color[0] = 0
    while paths:
        x = paths.pop()
        visits[x] = True
        for g in G[x]:
            if visits[g] and color[g] == color[x]:
                return False
            elif not visits[g]:
                paths.append(g)
                color[g] = (color[x]+1) % 2
        print(paths)
    return True


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

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [[] for i in range(N)]
for m in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

color = [-1 for i in range(N)]
visits = [False for i in range(N)]
paths = deque()


def Bipartial():
    paths.append(0)
    color[0] = 0
    while paths:
        x = paths.pop()
        visits[x] = True
        for g in G[x]:
            if visits[g] and color[g] == color[x]:
                return False
            elif not visits[g]:
                paths.append(g)
                color[g] = (color[x]+1) % 2
        return True


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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    a,b=MAP()
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)

visited=[False]*N
team=['']*N

def rec(u):
    if visited[u]:
        return True
    visited[u]=True
    for v in nodes[u]:
        if team[u]==team[v]:
            return False
        if team[u]=='a':
            team[v]='b'
        elif team[u]=='b':
            team[v]='a'
        if not rec(v):
            return False
    return True

# 1からnまでの等差数列の和
def get_sum(n):
    return (1+n)*n//2

team[0]='a'
if rec(0):
    ans=(N//2)*ceil(N, 2)-M
else:
    ans=get_sum(N-1)-M
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
fin = sys.stdin.readline

N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(elem) - 1 for elem in fin().split()]
    adj[a].append(b)
    adj[b].append(a)


def judge_bipartite(adj, v, color, colors):
    colors[v] = color
    for neighbor in adj[v]:
        if colors[neighbor] is None:
            if not judge_bipartite(adj, neighbor, 1 - color, colors):
                return False
        else:
            if colors[neighbor] == color:
                return False
    else:
        return True

colors = [None] * N
bipartite = judge_bipartite(adj, 0, 0, colors)
print(bipartite, colors)
if not bipartite:
    print(N * (N - 1) // 2 - M)
else:
    num_b = sum([v == 0 for v in colors])
    num_w = N - num_b
    print(num_b * num_w - M)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
fin = sys.stdin.readline

N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(elem) - 1 for elem in fin().split()]
    adj[a].append(b)
    adj[b].append(a)


def judge_bipartite(adj, v, color, colors):
    for neighbor in adj[v]:
        if colors[neighbor] is None:
            colors[neighbor] = 1 - color
            judge_bipartite(adj, neighbor, 1 - color, colors)
        else:
            if colors[neighbor] == color:
                return False, None
    else:
        return True, colors

colors = [None] * N
colors[0] = 0
bipartite, colors = judge_bipartite(adj, 0, 0, colors)
if not bipartite:
    print(N * (N - 1) // 2 - M)
else:
    num_b = sum([v == 0 for v in colors])
    num_w = N - num_b
    print(num_b * num_w - M)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = [sorted(list(map(int, input().split()))) for i in range(M)]
E.sort()
L = [-1]*(N+1)
L[1] = 0
al = False
for e in E:
    a, b = e
    if L[b] == -1:
        L[b] = 1-L[a]
    elif L[a] + L[b] != 1:
        al = True
        break
if al:
    print(N*(N-1)//2-M)
else:
    c = L.count(1)
    print(c*(N-c)-M)

Submission status: Wrong Answer

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

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

# 0は未着色を表す
color = [0] * N


# 二部グラフ判定dfs
def dfs(v, c):
    color[v] = c
    for to in G[v]:
        if color[to] == c:
            return False

        if color[to] == 0:
            dfs(to, -c)

    return True


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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())

graph = [[0 for i in range(n)] for j in range(n)]

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

memo = [0 for i in range(n)]
color = [-1 for i in range(n)]
black = 0
white = 0
flag = 0


def search(v):
    for i in range(n):
        if graph[v][i] == 1:
            if memo[i] == 0:
                memo[i] = 1
                color[i] = (color[v]+1) % 2
                if color[i] == 0:
                    global black
                    black += 1
                else:
                    global white
                    white += 1
                search(i)
            else:
                if color[v] == color[i]:
                    global flag
                    flag = 1

memo[0] = 1
color[0] = 0
black += 1
search(0)

if flag == 1:
    print(n*(n+1)/2 - m)
else:
    print(black * white - m)

Submission status: Wrong Answer

Solution code:
class BipartiteGraph():
    '''
    2部グラフ
    self.vertexesが1の集合と2の集合に分割
    完全ソート済の入力にしか対応してない
    '''
    def __init__(self, n):
        self.vertexes = [0 for _ in range(n)]

    # 2部グラフじゃなかったらfalseを返す
    def add(self, edge):  # edge = (2, 3)
        if self.vertexes[edge[0]] == 0:
            if self.vertexes[edge[1]] == 1:
                self.vertexes[edge[0]] = 2
            elif self.vertexes[edge[1]] == 2:
                self.vertexes[edge[0]] = 1
            else:
                self.vertexes[edge[0]] = 1
                self.vertexes[edge[1]] = 2
        elif self.vertexes[edge[0]] == 1:
            if self.vertexes[edge[1]] == 1:
                return False
            else:
                self.vertexes[edge[1]] = 2
        elif self.vertexes[edge[0]] == 2:
            if self.vertexes[edge[1]] == 2:
                return False
            else:
                self.vertexes[edge[1]] = 1
        return True

    def length(self):
        cnt = [0, 0]
        for i in self.vertexes:
            cnt[i-1] += 1
        return cnt

    def __str__(self):
        A = []
        B = []
        for i, v in enumerate(self.vertexes):
            if v == 1:
                A.append(str(i))
            elif v == 2:
                B.append(str(i))
        return 'A:[' + ','.join(A) + "]B:[" + ','.join(B) + "]"

n, m = (int(i) for i in input().split())

inp = sorted([[int(i) for i in sorted(input().split())] for i in range(m)], key=lambda x: x[0])
graph = BipartiteGraph(n)

for i in inp:
    i = list(map(lambda x: x-1, i))
    if not graph.add(i):
        print(int(n*(n-1) / 2) - m)
        exit(0)

ln = graph.length()
print(ln[0]*ln[1]-m)

Submission status: Wrong Answer

Solution code:
class BipartiteGraph():
    '''
    2部グラフ
    self.vertexesが1の集合と2の集合に分割
    '''
    def __init__(self, n):
        self.vertexes = [0 for _ in range(n)]

    # 2部グラフじゃなかったらfalseを返す
    def add(self, edge):  # edge = (2, 3)
        if self.vertexes[edge[0]] == 0:
            if self.vertexes[edge[1]] == 1:
                self.vertexes[edge[0]] = 2
            elif self.vertexes[edge[1]] == 2:
                self.vertexes[edge[0]] = 1
            else:
                self.vertexes[edge[0]] = 1
                self.vertexes[edge[1]] = 2
        elif self.vertexes[edge[0]] == 1:
            if self.vertexes[edge[1]] == 1:
                return False
            else:
                self.vertexes[edge[1]] = 2
        elif self.vertexes[edge[0]] == 2:
            if self.vertexes[edge[1]] == 2:
                return False
            else:
                self.vertexes[edge[1]] = 1
        return True

    def length(self):
        cnt = [0, 0]
        for i in self.vertexes:
            cnt[i-1] += 1
        return cnt

    def __str__(self):
        A = []
        B = []
        for i, v in enumerate(self.vertexes):
            if v == 1:
                A.append(str(i))
            elif v == 2:
                B.append(str(i))
        return 'A:[' + ','.join(A) + "]B:[" + ','.join(B) + "]"

n, m = (int(i) for i in input().split())

inp = sorted([[int(i) for i in input().split()] for i in range(m)], key=lambda x: x[0])

graph = BipartiteGraph(n)

for i in inp:
    i = list(map(lambda x: x-1, i))
    if not graph.add(i):
        print(int(n*(n-1) / 2) - m)
        exit(0)

ln = graph.length()
print(ln[0]*ln[1]-m)

Submission status: Wrong Answer

Solution code:
class BipartiteGraph():
    '''
    2部グラフ
    self.vertexesが1の集合と2の集合に分割
    '''
    def __init__(self, n):
        self.vertexes = [0 for _ in range(n)]

    # 2部グラフじゃなかったらfalseを返す
    def add(self, edge): # edge = (2, 3)
        edge.sort()
        if self.vertexes[edge[0]] == 0:
            if self.vertexes[edge[1]] == 1:
                self.vertexes[edge[0]] = 2
            elif self.vertexes[edge[1]] == 1:
                self.vertexes[edge[0]] = 1
            else:
                self.vertexes[edge[0]] = 1
                self.vertexes[edge[1]] = 2
        elif self.vertexes[edge[0]] == 1:
            if self.vertexes[edge[1]] == 1:
                return False
            else:
                self.vertexes[edge[1]] = 2
        elif self.vertexes[edge[0]] == 2:
            if self.vertexes[edge[1]] == 2:
                return False
            else:
                self.vertexes[edge[1]] = 1
        return True

    def length(self):
        cnt = [0,0]
        for i in self.vertexes:
            cnt[i-1] += 1
        return cnt

    def __str__(self):
        A = []
        B = []
        for i, v in enumerate(self.vertexes):
            if v == 1:
                A.append(str(i))
            elif v == 2:
                B.append(str(i))
        return 'A:[' + ','.join(A) + "]B:[" + ','.join(B) + "]"

n, m = (int(i) for i in input().split())

inp = sorted([[int(i) for i in input().split()] for i in range(m)] , key = lambda x:x[0])

graph = BipartiteGraph(n)

for i in inp:
    i = list(map(lambda x: x-1, i))
    if not graph.add(i):
        print(int(n*(n-1) / 2) - m)
        exit(0)

ln = graph.length()
print(ln[0]*ln[1]-m)

Submission status: Wrong Answer

Solution code:
class BipartiteGraph():
    '''
    2部グラフ
    self.vertexesが1の集合と2の集合に分割
    '''
    def __init__(self, n):
        self.vertexes = [0 for _ in range(n)]

    # 2部グラフじゃなかったらfalseを返す
    def add(self, edge): # edge = (2, 3)
        edge.sort()
        if self.vertexes[edge[0]] == 0:
            if self.vertexes[edge[1]] == 1:
                self.vertexes[edge[0]] = 2
            elif self.vertexes[edge[1]] == 1:
                self.vertexes[edge[0]] = 1
            else:
                self.vertexes[edge[0]] = 1
                self.vertexes[edge[1]] = 2
        elif self.vertexes[edge[0]] == 1:
            if self.vertexes[edge[1]] == 1:
                return False
            else:
                self.vertexes[edge[1]] = 2
        elif self.vertexes[edge[0]] == 2:
            if self.vertexes[edge[1]] == 2:
                return False
            else:
                self.vertexes[edge[1]] = 1
        return True

    def length(self):
        cnt = [0,0]
        for i in self.vertexes:
            cnt[i-1] += 1
        return cnt

    def __str__(self):
        A = []
        B = []
        for i, v in enumerate(self.vertexes):
            if v == 1:
                A.append(str(i))
            elif v == 2:
                B.append(str(i))
        return 'A:[' + ','.join(A) + "]B:[" + ','.join(B) + "]"

n, m = (int(i) for i in input().split())

inp = [[int(i) for i in input().split()] for i in range(m)]

graph = BipartiteGraph(n)

for i in inp:
    i = list(map(lambda x: x-1, i))
    if not graph.add(i):
        print(int(n*(n-1) / 2) - m)
        exit(0)

ln = graph.length()
print(ln[0]*ln[1]-m)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,m = map(int,raw_input().split(" "))

line = [[0 for i in range(n)] for j in range(n)]

for a in range(m):
  q,r = map(int,raw_input().split(" "))
  line[q-1][r-1] = 1
  line[r-1][q-1] = 1

mat = np.matrix(line)
buf = np.count_nonzero(mat)

buf2 = 0

while True:
  mat2 = mat*mat*mat
  print mat2
  for a in range(n):
    mat2[a,a] = False

  mat = np.logical_or(mat2,mat)
  print mat

  q = np.count_nonzero(mat)
  if q > buf2:
    buf2 = q
  else:
    break

print (buf2-buf)/2

Submission status: Wrong Answer

Solution code:
node1 = {}
node2 = {}


def expl(u,memo,count,t):
  if count == 3:
    return 0
  else:
    for i in node2[u]:
      if i in memo:
        continue
      else:
        print count ,memo , u , i
        if count == 2 and (t,i) not in node1:
          node1[(t,i)] =1
          node1[(i,t)] =1
          print node1
          return 1
        else:
          return expl(i,memo+[i],count+1,t)
  return 0

n,m = map(int,raw_input().split())
temp = 0
for i in range(0,m):
  a,b = map(int,raw_input().split())
  node1[(a,b)] = 1
  node1[(b,a)] = 1
  if a in node2:
    node2[a].append(b)
  else:
    node2[a] = [b]
  if b in node2:
    node2[b].append(a)
  else:
    node2[b] = [a]
print node1
temo = 0
for i in range(1,n+1):
  temo += expl(i,[i],0,i)
print node1

temp = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    if (i,j) in node1:
      temp += 1
print temp /2 -m+1

Submission status: Wrong Answer

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

nm = raw_input()
nm = nm.split()
n,m = map(int,nm)

tree = []
flag = []
for i in range(n):
    tree.append([])
    flag.append(1)

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

status = 0
x = []
y = []

x.append(0)
for j in tree[0]:
    y.append(j)
flag[0] = 0

while 1:
    for i in range(n):
        if flag[i] == 1:
            if i in x:
                for b in tree[i]:
                    if b in x:
                        status = 1
                        break
                    elif b in y:
                        pass
                    else:
                        y.append(b)
            elif i in y:
                for b in tree[i]:
                    if b in y:
                        status = 1
                        break
                    elif b in x:
                        pass
                    else:
                        x.append(b)
            flag[i] = 0
    if sum(flag) == 0:
        break

#print x
#print y
#print status,flag

p = len(x) * len(y)
q = n*(n-1)/2

if status == 0:
    print p - m
else:
    print q - m

Submission status: Wrong Answer

Solution code:
a = input().split()
N = int(a[0])
M = int(a[1])
B = {str(i):set() for i in range(1,N+1)}
D = {str(i):-1 for i in range(1,N+1)}

for i in range(M):
    b = input().split()
    B[b[0]].add(b[1])
    B[b[1]].add(b[0])
    
complete = False
D['1'] = 0
check = {str(i) for i in range(1,N+1)}
check.remove('1')
cnt = 1
Bs = B['1']
while len(check) > 0 and complete == False and cnt <= M:
    nextBs = set()
    for j in Bs:
        if D[j] >= 0 and D[j] != cnt % 2:
            complete = True
            break
        else:
            D[j] = cnt % 2
            if j in check:
                nextBs = nextBs|B[j]
                check.remove(j)
    if len(nextBs) == 0:
        break
    cnt += 1
    Bs = nextBs
if complete:
    ma = N * (N - 1 )/2
else:
    ma = 3 * N - 9
print(int(ma-M))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
print(n*(n-1)//2-m)

Submission status: Wrong Answer

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

d =defaultdict(list)

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



def check(i):
    dists = [-1 for _  in range(N)]
    dists[i]=0
    #q = deque([ (1,val)for val in d[i]])
    visited = [False for _ in range(N)]
    visited[i]=True
    q= deque([(0,i)])
    while q:
        #print(dists,q)
        dist,now = q.popleft()
        #visited[now]=True
        if dists[now]==-1:
            dists[now]= dist
        for val in d[now]:
            if not visited[val]:
                q.append((dist+1,val))
                visited[val]=True
            else:
                #check loop
                if dists[val] %2 != (dist+1)%2:
                    return True
    #print(dists)
    odds = []
    evens = []
    for i,_d in enumerate(dists):
        if _d%2 ==0:
            odds.append(i)
        else:
            evens.append(i)
    return odds,evens

res = check(0)
if res is True:
    print(N*(N-1)//2 -M)
else:
    odds,evens = res
    ans =0
    print( len(odds)*(len(evens)) -M
           )

    """
    for i in odds:
        ans += len(odds) -sum(  val in evens for val in d[i])
    for i in evens:
        ans += len(evens) - sum(val in odds for val in d[i])
    print(ans//2)
    """