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: Runtime Error

Solution code:
from collections import defaultdict

G = defaultdict(list)


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

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

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

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

Submission status: Runtime Error

Solution code:
import math

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

flag = True


def dfs(i, pre, c):
    if color[i] == c:
        return
    elif color[i] == 1-c:
        global flag
        flag = False
        return
    color[i] = c
    for v in edge[i]:
        dfs(v, i, 1-c)


dfs(0, -1, 0)
# print(color)
# print(flag)

if flag:
    print(color.count(1)*color.count(0)-m)
else:
    print(math.floor(n*(n-1)/2-m))

Submission status: Runtime Error

Solution code:
vn,en = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(en)]

e = [[] for _ in range(vn)]
for f,t in ab:
  e[f-1].append(t-1)
  e[t-1].append(f-1)
  
  
def dfs(v, root:list):  
  if v in root:
    return
  else:
    root.append(v)
    
  if len(root)==4:
    if not (root[-1] in e[root[0]]):              
      s.add(tuple(root))
      s.add(tuple(root[::-1]))
      e[root[0]].append(root[-1])
      e[root[-1]].append(root[0])  
  else:    
    for vt in e[root[-1]]:
      if not vt in root:
        dfs(vt,root)
     
    
s = set()
for vi in range(vn):
  for vt in e[vi]:    
    dfs(vt,[vi]) 
    
print(len(s)//2)

Submission status: Runtime Error

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: Runtime Error

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
def is_bipartite(G):
    n = len(G)
    color = [-1]*n
    que = deque([0])
    color[0] = 0
    while que:
        v = que.pop()
        c = color[v]
        for nv in G[v]:
            if color[nv]<0:
                color[nv] = 1-c
                que.append(nv)
            elif color[nv] == c:
                return False
    return color
color = is_bipartite(G)
if color:
    a = color.count(0)
    b = N-a
    print(a*b-M)
else:
    print(N*(N-1)//2-M)

Submission status: Runtime Error

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

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

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

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

# 二部グラフかどうかの判定
color = [None] * N
color[0] = 0
q = [0]
while q:
    x = q.pop()
    for y in graph[x]:
        if color[y] is None:
            color[y] = 1 - color[x]
            q.append(y)

# 二部グラフかどうか
bg = all(color[a] != color[b] for a, b in AB)

if bg:
    # 完全二部グラフにする
    x = sum(color)
    y = N - x
    answer = x*y - M
else:
    # 完全グラフにする(奇数長のパスがある場合は必ず2ずつ減らしていけば長さが3になる)
    answer = N*(N-1)//2 - M

print(answer)

Submission status: Runtime Error

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

g = [[] for _ in range(n)]

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

color = [-1] * n

black = 0
white = 0

def dfs(v, c):
    global black, white
    
    color[v] = c
    if c == 0:
        black += 1
    else:
        white += 1

    for next_v in g[v]:
        if color[next_v] == c: 
            return False

        if color[next_v] == -1:
            if not dfs(next_v, 1 - c):
                return False
    return True

if dfs(0, 0):
    print(black * white - m)
else:
    print(n * (n - 1) // 2 - m)

Submission status: Runtime Error

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

g = [[] for _ in range(n)]

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

color = [-1] * n

black = 0
white = 0

def dfs(v, c):
    global black, white
    
    color[v] = c
    if c == 0:
        black += 1
    else:
        white += 1

    for next_v in g[v]:
        if color[next_v] == c: 
            return False

        if color[next_v] == -1:
            return dfs(next_v, 1 - c)
    return True

if dfs(0, 0):
    print(black * white - m)
else:
    print(n * (n - 1) // 2 - m)

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long int;
int MAX_N = 1e5;
vector<int> is_odd(MAX_N, -1);
vector<vector<int>> edge(MAX_N, vector<int>{});
ll odd_num = 0;
ll even_num = 0;
ll n, m;

int dfs(int d, int v){
    if(is_odd[v] != -1){
        if(is_odd[v] == d % 2){return 0;}
        else{
            cout << n * (n-1) / 2 - m << endl;
            exit(0);
        }
    }
    is_odd[v] = d % 2; 
    if(d%2 == 0){even_num++;}
    else{odd_num++;}
    for(int i=0; i<edge[v].size(); i++){
        dfs(d+1, edge[v][i]);
    }
    return 0;
}

int main() {
    cin >> n >> m;
    int a, b;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        a--; b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    dfs(0, 0);
    cout << odd_num * even_num - m << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N)]
for x, y in edges:
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)

def dfs(v, c):
    # c: color = 1 or -1
    node[v] = c
    for i in graph[v]:
        if node[i] == c:
            return False
        
        if node[i] == 0 and not dfs(i, -c):
            return False
        
    return True

node = [0] * N
if dfs(0, 1):
    x = sum(v + 1 for v in node) // 2
    print(x * (N - x) - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Runtime Error

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):
  	black = color.count(0)
    white = N - black
    print(black*white-M)
else:
    print(comb(N, 2)-M)

Submission status: Runtime Error

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
    for i in s[v]:
        if c[i]==t:
            return false
        if c[i]==0 and not 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: Runtime Error

Solution code:
N,M=[int(a) for a in input().split()]
AB=[[int(a) for a in input().split()] for _ in range(M)]
edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

visited = [False]*N
WH = [None]*N

def dfs(curr, is_white):
    if visited[curr]:
        return WH[curr]^is_white
    WH[curr] = is_white
    visited[curr] = True
    ans = False
    for node in edges[curr]:
        ans |= dfs(node, not is_white)
    return ans

if dfs(0, True):
    print((N*(N-1))//2 - M)
else:
    nw = sum(WH)
    print(nw*(N-nw)-sum([WH[a-1]^WH[b-1] for a, b in AB]))

Submission status: Runtime Error

Solution code:
#s,t間に奇数長のパスが存在したならば必ずs,t間には辺が張られる
#グラフが二部グラフでないならば奇数長のサイクルが存在して任意の(s,t)間に奇数長パスが作れる
#グラフが二部グラフであるならば異なるカラーグループ間の頂点には必ず辺が張られる
n,m = map(int,input().split())
G = defaultdict(set)
color = [0 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    G[a-1].add(b-1)
    G[b-1].add(a-1)
#二部グラフ判定
color[0]=1
que = deque([0])
bipartite = True
while len(que):
    p = que.popleft()
    for q in list(G[p]):
        if color[q] == 0:
            color[q] = -color[p]
            que.append(q)
        elif color[q] == color[p]:
            bipartite = False
            break
if bipartite:
    print(color.count(1)*color.count(-1)-m)
else:
    print(n*(n-1)//2-m)

Submission status: Runtime Error

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

chk = func(1,1)

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

Submission status: Runtime Error

Solution code:
from collections import Counter

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

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

chk = func(1,1)

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

Submission status: Runtime Error

Solution code:
from collections import Counter

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

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

chk = func(1,1)

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

Submission status: Runtime Error

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

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

chk = func(1,1)

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

Submission status: Runtime Error

Solution code:
from collections import Counter

N, M = map(int, input().split())
ab_list = []
for _ in range(M):
    a, b = map(int, input().split())
    ab_list.append([a,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] == 0:
        nodes_color[v] = c
    elif nodes_color[v] == -c:
        return False
    else:
        return True
    
    for ab in ab_list:
        if v in ab:
            for a in ab:
                if a==v:
                    continue
                if not func(a, -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):
#                 print("Not Bipartite graph")
                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: Runtime Error

Solution code:
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  a-=1
  b-=1
  G[a].append(b)
  G[b].append(a)
color=[-1]*N  
def dfs(x):
  for i in G[x]:
    if color[i]==-1:
      color[i]=1^color[x]
      dfs(i)
    elif color[i]==color[x]:
      print((N*(N-1))//2-M)
      exit()
color[0]=0
dfs(0)
b=0
for i in range(N):
  b+=color[i]
print(b*(N-b)-M)

Submission status: Runtime Error

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

colors = [0 for i in range(N)]

def is_bipartite():
    stack = [(0,1)]
    while stack:
        v,color = stack.pop()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.append((to, -color))
    return True

if is_bipartite():
    b = (sum(colors) + N) // 2
    w = N-b
    print(b*w - M)
else:
    all = N*(N-1) // 2
    print(all - M)

Submission status: Runtime Error

Solution code:
import sys
F = sys.stdin
N, M = map(int, F.readline().strip("\n").split())
Edge = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, F.readline().strip("\n").split())
    Edge[A-1].append(B-1)
    Edge[B-1].append(A-1)

Color = [0] * N


def dfs(v, c):
    Color[v] = c
    for next in Edge[v]:
        if Color[next] == c: return False
        if Color[next] == 0:
            if not dfs(next, -c): return False
    return True

Bipartite = dfs(0, 1)
if Bipartite:
    black = Color.count(1)
    print(black * (N-black) - M)
else:
    print(N * (N - 1)//2 - M)

Submission status: Runtime Error

Solution code:
import sys
#sys.setrecursionlimit(200000)
input = sys.stdin.readline
n,m= map(int,input().split())
g = [[]for i in range(n)]
for i in range(m):
        a,b = map(int,input().split())
        a-=1;b-=1
        g[a].append(b)
        g[b].append(a)
kyo = [1<<50]*n
def dfs(x,y,z):
        for i in g[x]:
                if i == y: continue
                if kyo[i] > z+1:
                        kyo[i] = z+1
                        dfs(i,x,z+1)
kyo[0] = 0
dfs(0,0,0)
ki = 0
gu = 0
mita = set()
for i in kyo:
        if i in mita:
                print(n*(n-1)//2-m)
                exit()
        mita.add(i)
        if i %2 == 0:
                gu += 1
        else:
                ki += 1
print(gu*ki-m)

Submission status: Runtime Error

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

path = []
path_from=[[] for i in range(N)]

for i in range(M):
    A,B = map(int,raw_input().split())
    path_from[A-1].append(B-1)
    path_from[B-1].append(A-1)
    
color_list = [0 for i in range(N)]
color_list[0] = 1

def two_part_or_not(start,path_from,color_list):
    for end in path_from[start]:
        if color_list[end]==color_list[start]:
            return False
        elif color_list[end]==0:
            color_list[end]=-color_list[start]
            color_list = two_part_or_not(end,path_from,color_list)
            if color_list==False:
                return False
    return color_list

color_list = two_part_or_not(0,path_from,color_list)

if color_list!=False:
    pos = 0
    for c in color_list:
        if c==1:
            pos+=1
    print(pos*(N-pos) - M)
else:
    print((N*(N-1))/2-M)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
E = [sorted(list(map(int, input().split()))) for i in range(M)]
E.sort()
print(E)
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)
    raise ValueError()

Submission status: Runtime Error

Solution code:
#import sys
#stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def dfs(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    stack = [(0,start)]
    
    while stack:
        cost, cur_node = stack.pop()

        # 未探索のノードをstackに入れる
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                stack.append((dist[nex_node],nex_node))
                
    return dist

def isnibu(graph:list, dist:list) -> bool:
    for i,edges in enumerate(graph):
        for _, j in edges:
            if dist[i]%2 == dist[j]%2:
                return False
    
    return True
    
    

n,m = li()

adj_lst = [set() for _ in range(n)]

for _ in range(m):
    a,b = li_()
    
    adj_lst[a].add((1,b))
    adj_lst[b].add((1,a))
    
dist = dfs(adj_lst, n, 0)

nibu = isnibu(adj_lst, dist)

ans = 0
if isnibu(adj_lst, dist):
    ans = sum([dist[i]%2 == 1 for i in range(n)]) * sum([dist[i]%2 == 0 for i in range(n)]) - m
    
else:
    ans = n*(n-1)//2 - m
    
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.getrecursionlimit(1000000)

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

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

color = [0] * N
def dfs(v, c):
    '''
    頂点vをcで塗る　そこから深さ優先探索で交互に塗っていく
    '''
    color[v] = c
    for i in G[v]:
        if color[i] == c:
            return False
        if color[i] == 0 and not(dfs(i, -c)):
            return False
    return True

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

Submission status: Runtime Error

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

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

color = [0] * N
def dfs(v, c):
    '''
    頂点vをcで塗る　そこから深さ優先探索で交互に塗っていく
    '''
    color[v] = c
    for i in G[v]:
        if color[i] == c:
            return False
        if color[i] == 0 and not(dfs(i, -c)):
            return False
    return True

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict 

N,M = map(int,input().split())
dict = defaultdict(set)

for i in range(M):
	a,b = list(map(int,input().split()))
	dict[a].add(b)
	dict[b].add(a)


color = [0 for i in range(N+1)]
nibu = True

def dfs(v,c):
	u'''
	v : 現在のグラフの頂点
	c : vのグラフのcolor
	queue : 探索済みのグラフの頂点
	res   : 二部グラフの判定 bool
	'''

	global color
	global nibu 

	for i in list(dict[v]):
		if color[i] == c:#隣の頂点が同じ値を与えられている際Falseを返す
			nibu = False
			break
		elif color[i] == 0:	#探索済みでなければ再帰する
			color[i] = c*-1		#0ならcとは異なる値を格納
			dfs(i,-c)		#引数に-cとすることで,cが1=>-1=>1を繰り返す


color[1] = 1  #始点色分けする

dfs(1,1)

if nibu:
	b = color.count(1)
	w = color.count(-1)
	ans = b * w - M
else:
	ans = N * (N-1)//2 - M
	
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adjL = [[] for v in range(N)]
for e in range(M):
    A, B = map(int, input().split())
    adjL[A - 1].append(B - 1)
    adjL[B - 1].append(A - 1)

# 二部グラフかどうかを判定する（頂点を1or-1で塗っていく）
colors = [0] * N

def dfs(vNow, color):
    colors[vNow] = color # 頂点vNowをcolorで塗る
    for v in adjL[vNow]:
        if colors[v] == color:
            # 隣接する頂点vが同じ色で彩色済みならば、二部グラフではない
            return False
        if colors[v] == 0 and not dfs(v, -color):
            # 隣接する頂点vが未彩色ならば、もう１つの色で塗ってみる
            return False

    return True


IsBipartite = dfs(0, 1)

if IsBipartite:
    # 二部グラフである場合
    num = colors.count(1)
    print(num * (N - num) - M)
else:
    # 二部グラフでない場合
    print(N * (N - 1) // 2 - M)

Submission status: Runtime Error

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

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

for i in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b - 1].append(a - 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 graph[v]:
        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: Runtime Error

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][b] = 1
    graph[b][a] = 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
search(0)

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
edge = [[] for i 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)
# -1 → 0,1に塗っていきます
color=[-1 for i in range(n)]
def dfs(pos):
    ret = True
    for i in range(len(edge[pos])):
        to = edge[pos][i]
        if color[to] == -1:
            color[to] = 1 ^ color[pos]
            ret &= dfs(to)
        else:
            ret &= not (color[to]==color[pos])
    return ret

color[0]=0
if dfs(0):
    black, white = 0, 0
    for i in range(n):
        if color[i]==0:
            black += 1
        else:
            white += 1
    print(black*white-m)
else:
    print(n*(n-1)//2-m)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
edge = [[] for i 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)
# -1 → 0,1に塗っていきます
color=[-1 for i in range(n)]
def dfs(pos):
    ret = True
    for i in range(len(edge[pos])):
        to = edge[pos][i]
        if color[to] == -1:
            color[to] = 1 ^ color[pos]
            ret &= dfs(to)
        else:
            ret &= color[to]==color[pos]
    return ret

color[0]=0
if dfs(0):
    print(color)
    black, white = 0, 0
    for i in range(n):
        if color[i]==0:
            black += 1
        else:
            white += 1
    print(black*white-m)
else:
    print(n*(n-1)//2-m)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	
#print nl


def dfs(v):
	F[v]=1
	for i in nl[v]:
		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			#２部グラフではない
			print N*(N-1)/2-M
			sys.exit()
		else:
			continue
		#print v,i,color,F
		
		if F[i]==0:
			dfs(i)


F=[0]*(N+1)
color=[0]*(N+1)
color[1]="w"
dfs(1)

#２部グラフの場合
print color.count("b")*color.count("w")-M

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	
#print nl


def dfs(v):
	F[v]=1
	for i in nl[v]:
		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			#２部グラフではない
			print N*(N-1)/2-M
			sys.exit()
		#print v,i,color,F
		
		if F[i]==0:
			dfs(i)


F=[0]*(N+1)
color=[0]*(N+1)
color[1]="w"
dfs(1)

#２部グラフの場合
print color.count("b")*color.count("w")-M

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	
#print nl


def dfs(v,p):
	F[v]=1
	for i in nl[v]:
		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			#２部グラフではない
			print N*(N-1)/2-M
			sys.exit()
		#print v,i,color,F
		
		if F[i]==0:
			#DFS(次の頂点i, 次に親となる頂点v)
			#print "dfs::"+str(i)
			dfs(i,v)


F=[0]*(N+1)
color=[0]*(N+1)
color[1]="w"
dfs(1,-1)

#２部グラフの場合
print color.count("b")*color.count("w")-M

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	
#print nl


def dfs(v,p):
	F[v]=1
	global bip_graph
	for i in nl[v]:
		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			#二分木ではない
			print N*(N-1)/2-M
			sys.exit()
		#print v,i,color,F
		
		if F[i]==0:
			#DFS(次の頂点i, 次に親となる頂点v, d+ 頂点vと頂点iの間の辺のコスト)
			dfs(i,v)


bip_graph="YES"
F=[0]*(N+1)
color=[0]*(N+1)
color[1]="w"
dfs(1,-1)


print color.count("b")*color.count("w")-M

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	
#print nl


def dfs(v,p):
	F[v]=1
	global bip_graph
	for i in nl[v]:

		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			#二分木ではない
			bip_graph="NO"
		#print v,i,color,F
		
		if bip_graph!="NO" and F[i]==0:
			#DFS(次の頂点i, 次に親となる頂点v, d+ 頂点vと頂点iの間の辺のコスト)
			dfs(i,v)


bip_graph="YES"
F=[0]*(N+1)
color=[0]*(N+1)
color[1]="b"
dfs(1,-1)
#print nl
#print color
#print bip_graph


if bip_graph=="YES":
	print color.count("b")*color.count("w")-M
elif bip_graph=="NO":
	print N*(N-1)/2-M

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	
#print nl


def dfs(v,p):
	F[v]=1
	global bip_graph
	for i in nl[v]:
		#print v,i,color
		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			#二分木ではない
			bip_graph="NO"

		if bip_graph!="NO" and F[i]==0:
			#DFS(次の頂点i, 次に親となる頂点v, d+ 頂点vと頂点iの間の辺のコスト)
			dfs(i,v)


bip_graph="YES"
F=[0]*(N+1)
color=[0]*(N+1)
color[1]="b"
dfs(1,-1)
#print color
#print bip_graph

if bip_graph=="YES":
	print color.count("b")*color.count("w")-M
elif bip_graph=="NO":
	print N*(N-1)/2-M