Buggy python submission (verdict: Runtime Error):
def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for next_v in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v]:
                return False
            continue
        seen[next_v] = 1-current_color
        # 再帰的に探索
        if not dfs(g, next_v, seen, 1 - current_color):
            return False
    return True


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, [])
        dic_a.append(b-1)
        dic_b = g.setdefault(b-1, [])
        dic_b.append(a-1)
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True
    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, 0, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        for i in range(n):
            st = "white" if seen[i] == 0 else "black"
            print(str(i) + ":" + st)
    else:
        print("is not bipartite")

main()


Fixed submission:
import sys

sys.setrecursionlimit(100000000)


def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for next_v in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v]:
                return False
            continue
        seen[next_v] = 1-current_color
        # 再帰的に探索
        if not dfs(g, next_v, seen, 1 - current_color):
            return False
    return True


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, [])
        dic_a.append(b-1)
        dic_b = g.setdefault(b-1, [])
        dic_b.append(a-1)
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True
    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, 0, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        white = len([x for x in seen if x == 0])
        black = n - white

        print(black*white - m)
    else:
        print(int((n-1)*n / 2) - m)

main()

Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(1000000)

def triangle(m, g):
    for i in range(m):
        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(m, 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()


Fixed submission:
import sys

sys.setrecursionlimit(100000000)


def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for next_v in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v]:
                return False
            continue
        seen[next_v] = 1-current_color
        # 再帰的に探索
        if not dfs(g, next_v, seen, 1 - current_color):
            return False
    return True


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, [])
        dic_a.append(b-1)
        dic_b = g.setdefault(b-1, [])
        dic_b.append(a-1)
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True
    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, 0, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        white = len([x for x in seen if x == 0])
        black = n - white

        print(black*white - m)
    else:
        print(int((n-1)*n / 2) - m)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(1000000)


def dfs(g: {}, v: int, path_list: [], added: {}):
    path_list.append(v)
    for next_v in g[v]:
        # # next_v が探索済だったらスルー
        if next_v in path_list:
            continue
        # 距離３なら追加可能か確認して次へ
        if len(path_list) == 3:
            if path_list[0] not in g[next_v]:
                dic_a = added.setdefault(path_list[0], set())
                dic_a.add(next_v)
                dic_b = added.setdefault(next_v, set())
                dic_b.add(path_list[0])
        # 距離1なら複製して次へ
        elif len(path_list) == 1:
            copied = [v]
            dfs(g, next_v, copied, added)
        # 距離2なら複製して次へ
        elif len(path_list) == 2:
            copied = path_list.copy()
            dfs(g, next_v, copied, added)


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)
    count = 0
    while True:
        added = {}
        for i in range(n):
            dfs(g, i, [], added)
        added_cnt = 0
        for _set in added.values():
            added_cnt += len(_set)
        if added_cnt == 0:
            break
        count += added_cnt
        for k, v in added.items():
            dic_a = g.setdefault(k, set())
            for v_item in v:
                dic_a.add(v_item)
    print(int(count/2))



main()


Fixed submission:
import sys

sys.setrecursionlimit(100000000)


def dfs(g: {}, v: int, seen: [], current_color: int):
    seen[v] = current_color
    for next_v in g[v]:
        # next_v が探索済だったらスルー
        if seen[next_v] != -1:
            if current_color == seen[next_v]:
                return False
            continue
        seen[next_v] = 1-current_color
        # 再帰的に探索
        if not dfs(g, next_v, seen, 1 - current_color):
            return False
    return True


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, [])
        dic_a.append(b-1)
        dic_b = g.setdefault(b-1, [])
        dic_b.append(a-1)
    # -1:not clear, 0:white, 1:black
    seen = [-1] * n

    is_bipartite = True
    for i in range(n):
        if seen[i] != -1:
            continue
        if not dfs(g, 0, seen, 0):
            is_bipartite = False
            break

    if is_bipartite:
        white = len([x for x in seen if x == 0])
        black = n - white

        print(black*white - m)
    else:
        print(int((n-1)*n / 2) - m)

main()