Problem p02991 (python)

Fixed submission:
from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

S, T = map(int, input().split())

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

dq = deque()
dq.append((S, 0))

while dq:
    v = dq.popleft()
    if v == (T, 0):
        break
    for u in edge[v]:
        if dist[u] < inf: continue
        dq.append(u)
        dist[u] = dist[v] + 1

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

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

N, M = map(int, input().split())
e = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    e[(a, 0)].append((b, 1))
    e[(a, 1)].append((b, 2))
    e[(a, 2)].append((b, 0))

S, T = map(int, input().split())

d = deque()
d.appendleft((S, 0))

inf = float('inf')
dist = defaultdict(lambda: inf)
dist[(S, 0)] = 0

def BFS(now):
    for v in e[now]:
        if(dist[v] > dist[now] + 1):
            dist[v] = dist[now] + 1
            if(v == (T, 0)):
                return
            BFS(v)
    return

BFS((S, 0))

ans = dist[(T, 0)]
if(ans == inf):
    print(-1)
else:
    print(ans//3)

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

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

S, T = map(int, input().split())

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, deq, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] < inf): continue
        dist[node] = dist[now] + 1
        deq.append(node)
    if(len(deq) > 0):
        next_node = deq.popleft()
        BST(next_node, deq, dist)
    return

deq = deque()
BST((S, 0), deq, dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

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

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

S, T = map(int, input().split())

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, deq, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] < inf): continue
        dist[node] = dist[now] + 1
        deq.append(node)
    if(len(deq) > 0):
        next_node = deq.pop()
        BST(next_node, deq, dist)
    return

deq = deque()
BST((S, 0), deq, dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

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

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

S, T = map(int, input().split())

inf = 10 ** 10
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, deq, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] > dist[now] + 1):
            dist[node] = dist[now] + 1
            deq.append(node)
    if(len(deq) > 0):
        next_node = deq.pop()
        BST(next_node, deq, dist)
    else:
        return

deq = deque()
BST((S, 0), deq, dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

Buggy submission (verdict: Runtime Error):
from collections import deque, defaultdict
from heapq import heappop, heappush

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

S, T = map(int, input().split())

inf = 10 ** 10
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, heap, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] > dist[now] + 1):
            dist[node] = dist[now] + 1
            heappush(heap, node)
    if(heap):
        next_node = heappop(heap)
        BST(next_node, heap, dist)
    else:
        return

heap = []
BST((S, 0), [], dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

Buggy submission (verdict: Runtime Error):
from collections import deque, defaultdict
from heapq import heappop, heappush

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

S, T = map(int, input().split())

inf = 10 ** 10
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, heap, dist):
    for node in edge[now]:
        if(dist[node] > dist[now] + 1):
            dist[node] = dist[now] + 1
            heappush(heap, node)
    if(heap):
        next_node = heappop(heap)
        BST(next_node, heap, dist)
    else:
        return

heap = []
BST((S, 0), [], dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

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

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

S, T = map(int, input().split())

def BST(now, goal, visited):
    count = 0
    for node in edge[now]:
        if(node == goal):
            return 1
        elif(not node in visited):
            visited.appendleft(node)
            temp = BST(node, goal, visited)
            if(temp == False):
                continue
            temp += 1
            visited.pop()
            if(count == 0):
                count = temp
            elif(temp < count):
                count = temp
    if(count == 0):
        return False
    else:
        return count

visited = deque()
ret = BST((S, 0), (T, 0), visited)
if(ret == False):
    print(-1)
else:
    print(ret//3)