Problem p02678 (python)

Fixed submission:
from collections import deque

def bfs(g_list, visited):
    q = deque([1])
    visited[1] = 0
    while q:
        curr_room = q.popleft()
        for next_room in g_list[curr_room]:
            if visited[next_room] >= 0:
                continue
            visited[next_room] = curr_room
            q.append(next_room)


def main():
    n, m = map(int, input().split()) 
    g_list = [ [] for _ in range(n+1)]
    visited = [-1] * (n+1)
    visited[0] = 0
    # print(g_list)
    for i in range(m):
        a, b = map(int, input().split()) 
        g_list[a].append(b)
        g_list[b].append(a)
    bfs(g_list,visited)
    # print(visited)
    ans = visited[2:]
    if -1 in ans:
        print('No')
    else:
        print('Yes')
        for a in ans:
            print(a)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import math
MOD =1000000007


def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        # print(K,x)
        x%=MOD
    return K * x


n = int(input())

a_b_d = {}
# b_a_d = {}

a_zero_cnt = 0
b_zero_cnt = 0
ab_zero_cnt = 0

for i in range(n):
    a, b = map(int, input().split()) 
    if a==0 and b!=0:
        a_zero_cnt += 1
    elif  a!=0 and b==0:
        b_zero_cnt += 1
    elif a == 0 and b == 0:
        ab_zero_cnt += 1
    else:
        gcd_ab = math.gcd(a,b)
        a = a//gcd_ab
        b = b//gcd_ab
        if a > 0 and b < 0:
            a *= -1
            b *= -1
        elif a < 0 and b < 0:
            a *= -1
            b *=-1
        a_b_d.setdefault((a,b),0)
        a_b_d[(a,b)] += 1


done_list = set()
pair_cnt = []
uniq_cnt = 0
for k,v in a_b_d.items():
    comp_pair1 = (-k[1], k[0])
    comp_pair2 = (k[1], -k[0])
    if k in done_list:
        continue
    if comp_pair1 in a_b_d:
        # print(k, comp_pair)
        done_list.add(comp_pair1)
        pair_cnt.append((v,a_b_d[comp_pair1]))
    elif comp_pair2 in a_b_d:
        # print(k, comp_pair)
        done_list.add(comp_pair2)
        pair_cnt.append((v,a_b_d[comp_pair2]))
    else:
        uniq_cnt += 1


ans = pow_k(2,uniq_cnt) % MOD
for pair in pair_cnt:
    ans *= (pow_k(2,pair[0]) + pow_k(2,pair[1]) -1 )
    ans%=MOD

zero_m = max(pow_k(2,a_zero_cnt) + pow_k(2,b_zero_cnt) -1, 1)
# print(ans)
ans *= zero_m
# ans *= (zero_cnt+1)
ans -= 1
print(ans%MOD)

Buggy submission (verdict: Runtime Error):
import math
MOD =1000000007


def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        # print(K,x)
        x%=MOD
    return K * x


n = int(input())

a_b_d = {}
# b_a_d = {}

a_zero_cnt = 0
b_zero_cnt = 0
ab_zero_cnt = 0

for i in range(n):
    a, b = map(int, input().split()) 
    if a==0 and b!=0:
        a_zero_cnt += 1
    elif  a!=0 and b==0:
        b_zero_cnt += 1
    elif a == 0 and b == 0:
        ab_zero_cnt += 1
    else:
        gcd_ab = math.gcd(a,b)
        a = a//gcd_ab
        b = b//gcd_ab
        if a > 0 and b < 0:
            a *= -1
            b *= -1
        elif a < 0 and b < 0:
            a *= -1
            b *=-1
        a_b_d.setdefault((a,b),0)
        a_b_d[(a,b)] += 1


done_list = set()
pair_cnt = []
uniq_cnt = 0
for k,v in a_b_d.items():
    comp_pair1 = (-k[1], k[0])
    comp_pair2 = (k[1], -k[0])
    if k in done_list:
        continue
    if comp_pair1 in a_b_d:
        # print(k, comp_pair)
        done_list.add(comp_pair1)
        pair_cnt.append((v,a_b_d[comp_pair1]))
    elif comp_pair2 in a_b_d:
        # print(k, comp_pair)
        done_list.add(comp_pair2)
        pair_cnt.append((v,a_b_d[comp_pair2]))
    else:
        uniq_cnt += 1


ans = pow_k(2,uniq_cnt) % MOD
for pair in pair_cnt:
    ans *= (pow_k(2,pair[0]) + pow_k(2,pair[1]) -1 )
    ans%=MOD

zero_m = max(pow_k(2,a_zero_cnt) + pow_k(2,b_zero_cnt) -1, 1)
# print(ans)
ans *= zero_m
# ans *= (zero_cnt+1)
ans -= 1
print(ans%MOD)

Buggy submission (verdict: Runtime Error):
from collections import deque

def bfs(g_list, visited):
    q = deque([1])
    visited[1] = 0
    while q:
        curr_room = q.popleft()
        for next_room in g_list[curr_room]:
            if visited[next_room] >= 0:
                continue
            visited[next_room] = curr_room
            q.append(next_room)


def main():
    n, m = map(int, input().split()) 
    g_list = [ [] for _ in range(m+1)]
    visited = [-1] * (n+1)
    visited[0] = 0
    for i in range(m):
        a, b = map(int, input().split()) 
        g_list[a].append(b)
        g_list[b].append(a)
    bfs(g_list,visited)
    # print(visited)
    ans = visited[2:]
    if -1 in ans:
        print('No')
    else:
        print('Yes')
        for a in ans:
            print(a)

if __name__ == "__main__":
    main()