Problem p03579 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**8)
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)
depth=[-1 for i in range(n)]
def check(i,h):
    depth[i]=h
    for j in edge[i]:
        if depth[j]==-1:
            check(j,(h+1)%2)
        elif depth[j]==depth[i]:
            return False
    return True
if check(0,0):
    blk=0
    whi=0
    for i in range(n):
        if depth[i]==0:
            blk+=1
        else:
            whi+=1
    print(b*w-m)
else:
    print(n*(n-1)//2-m)

Buggy submission (verdict: Runtime Error):
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)
depth=[-1 for i in range(n)]
def check(i,h):
    depth[i]=h
    for j in edge[i]:
        if depth[j]==-1:
            check(j,h+1)
        elif depth[j]%2==depth[i]%2:
            return False
    return True
if check(0,0):
    blk=0
    whi=0
    for i in range(n):
        if depth[i]%2==0:
            blk+=1
        else:
            whi+=1
    ret=0
    for i in range(n):
        if depth[i]%2==0:
            ret+=whi-len(edge[i])
        else:
            ret+=blk-len(edge[i])
    print(ret//2)
else:
    print(n*(n-1)//2-m)

Buggy submission (verdict: Runtime Error):
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)
depth=[-1 for i in range(n)]
def check(i,h):
    depth[i]=h
    for j in edge[i]:
        if depth[j]==-1:
            check(j,h+1)
        elif depth[j]%2==depth[i]%2:
            return False
    return True
if check(0,0):
    blk=0
    whi=0
    for i in range(n):
        if depth[i]%2==0:
            blk+=1
        else:
            whi+=1
    ret=0
    for i in range(n):
        if depth[i]%2==0:
            ret+=blk-len(edge[i])
        else:
            ret+=whi-len(edge[i])
    print(ret//2)
else:
    print(n*(n-1)//2-m)