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 .

Solution (Python):
from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))

def is_biparate(links):
    '''
    0=white,1=blackとする
    2部グラフなら黒に塗られている頂点の数を返す
    2部グラフでないなら-1を返す。
    '''
    
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]  
    visited = set()
    while q:
        v, c = q.pop()
        if v in visited:
            if colors[v] != c: 
                return -1
            continue
        visited.add(v)
        colors[v] = c
        for u in links[v]:
            q.append((u, c ^ 1))  
    return sum(colors)  
 




n, m = readLine_int_list()
g = [set() for _ in range(n)]

def main():
    for _ in range(m):
        a, b = readLine_int_list()
        a -= 1
        b -= 1
        g[a].add(b)
        g[b].add(a)
    
    
    
    bp1 = is_biparate(g)
    if bp1 == -1:
        '''
        2部グラフではない場合
            結論：完全グラフになるまで辺を追加できる
            →why
                奇サイクル上のある点をvとする
                s → v → tが偶数長でも、 奇サイクルの他の頂点を余計に経由することで奇数長になる
                s → tが奇数長になれば線が引ける
                つまり、任意の頂点間において奇数長が存在することになる
            完全グラフの辺の数は、n * (n - 1) // 2
            これには元あった辺の数まで含まれているので、 -m する
        '''
        max_m = n * (n - 1) // 2
    else:
        '''
        2部グラフの場合
            結論:(blackの数*whiteの数)本、線ができる
            why
                奇数閉路が存在しない => 異なる色間は必ず奇数長、同色間は必ず偶数長 
                1. whiteとblackの間は奇数長のパスが存在する ->線が引ける
                2. 同じ色どうしには奇数長のパスは存在しない -> 線は引かれない
                black=3, white=2の時の線の引き方 = b*w
            b*wにはパスの長さが1つまりもともとのパスが含まれてるので、-m　する
        '''
        max_m = bp1 * (n - bp1)
        
    print(max_m - m)
    

if __name__ == "__main__":
    main()

Solution (Python):
def is_biparate(links):
    '''
    0=white,1=blackとする
    2部グラフなら黒に塗られている頂点の数を返す
    2部グラフでないなら-1を返す。
    '''
    
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]  
    visited = set()
    while q:
        v, c = q.pop()
        if v in visited:
            if colors[v] != c: 
                return -1
            continue
        visited.add(v)
        colors[v] = c
        for u in links[v]:
            q.append((u, c ^ 1))  
    return sum(colors)  
 
 
n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
 
bp1 = is_biparate(links)

if bp1 == -1:
    '''
    2部グラフではない場合
        結論：完全グラフになるまで辺を追加できる
        →why
            奇サイクル上のある点をvとする
            s → v → tが偶数長でも、 奇サイクルの他の頂点を余計に経由することで奇数長になる
            s → tが奇数長になれば線が引ける
            つまり、任意の頂点間において奇数長が存在することになる
        完全グラフの辺の数は、n * (n - 1) // 2
        これには元あった辺の数まで含まれているので、 -m する
    '''
    max_m = n * (n - 1) // 2
else:
    '''
    2部グラフの場合
        結論:(blackの数*whiteの数)本、線ができる
        why
            奇数閉路が存在しない => 異なる色間は必ず奇数長、同色間は必ず偶数長 
            1. whiteとblackの間は奇数長のパスが存在する ->線が引ける
            2. 同じ色どうしには奇数長のパスは存在しない -> 線は引かれない
            black=3, white=2の時の線の引き方 = b*w
        b*wにはパスの長さが1つまりもともとのパスが含まれてるので、-m　する
    '''
    max_m = bp1 * (n - bp1)
    
print(max_m - m)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
G = dict()
for i in range(N):
    G[i+1] = []
color_list = [0] * N

close = False

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


color_list[0] = 1
for q in G[1]:
    color_list[q-1] = -1

que = deque(G[1])

while len(que) > 0:
    p = que.popleft()
    for q in G[p]:
        if color_list[q-1] == 0:
            color_list[q-1] = - color_list[p-1]
            que.append(q)
        elif color_list[q-1] == color_list[p-1]:
            close = True
            break

if close == True:
    print(N*(N-1) // 2 - M)
else:
    print(color_list.count(1)*color_list.count(-1) - M)

Solution (Python):
import sys
sys.setrecursionlimit(10**5 + 1)

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

valid = [True for i in range(n)]

def dfs(x):
    ret = 1
    valid[x] = False
    for y in sus[x]:
        if valid[y]:
            valid[y] = False
            ret += dfs(y)
    return ret

color = [-1 for i in range(n)]
sol = 0
cnt = [0, 0]

def boji(x):
    global cnt
    cnt[color[x]] += 1
    for y in sus[x]:
        if color[y] == -1:
            color[y] = 1 - color[x]
            if boji(y):
                return True
        elif color[y] == color[x]:
            return True
    return 0

for i in range(n):
    if color[i] == -1 and valid[i]:
        cnt = [0, 0]
        color[i] = 0
        if boji(i) == 0:
            sol += cnt[0] * cnt[1]
        else:
            d = dfs(i)
            sol += d * (d - 1) // 2
print(sol - m)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
color = [-1] * N
def dfs(v, c):
    if color[v] != -1:
        return color[v] == c
    else:
        color[v] = c
        ret = True
        for w in edge[v]:
            ret &= dfs(w, c ^ 1)
        return ret

if dfs(0, 0) == False:
    print(N * (N - 1) // 2 - M)
else:
    c1 = color.count(0)
    c2 = color.count(1)
    assert(c1 + c2 == N)
    print(c1 * c2 - M)

Solution (Python):
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    la = [None] * (n + 1)
    xt = [None] * (2 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 1
    st = [1]
    pu = st.append
    po = st.pop
    col = [None] * (n + 1)
    col[1] = 1
    while st:
        x = po()
        y = la[x]
        nc = 3 - col[x]
        while y is not None:
            t = dat[y]
            if col[t] is None:
                col[t] = nc
                pu(t)
            else:
                col[t] |= nc
            y = xt[y]
    ans = 0
    p = [0] * 3
    for i in xrange(1, n + 1):
        if col[i] == 3:
            ans = 0
            break
        ans += p[col[i]]
        p[col[i]] += 1
    print n * (n - 1) / 2 - m - ans
main()

Solution (Python):
def is_biparate(links):
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]
    visited = set()
    cnt = 0
    while q:
        v, c = q.pop()
        if v in visited:
            if colors[v] != c:
                return False
            continue
        visited.add(v)
        colors[v] = c
        cnt += c
        for u in links[v]:
            q.append((u, c ^ 1))
    return cnt


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

bp1 = is_biparate(links)
if is_biparate(links):
    max_m = bp1 * (n - bp1)
else:
    max_m = n * (n - 1) // 2
print(max_m - m)

Solution (Python):
n, m = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
from collections import deque
que = deque()
col = [-1]*n
que.append(0)
col[0] = 0
g = [0]*2
g[0] = 1
yes = 1
while que:
    v = que.popleft()
    for t in G[v]:
        if col[t] == -1:
            col[t] = col[v]^1
            g[col[t]] += 1
            que.append(t)
        else:
            if col[t] == col[v]:
                yes = 0
if yes:
    ans = g[0]*g[1]
    for v in range(n):
        for t in G[v]:
            if v < t and col[v] != col[t]:
                ans -= 1
    print(ans)
else:
    print(n*(n-1)//2 - m)