Buggy python submission (verdict: Time Limit Exceeded):


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

N, M = list(map(int, input().split()))
uv = []
for i in range(M):
	uv.append(list(map(int, input().split())))
S, T = list(map(int, input().split()))
G = [dict() for i in range(N+1)]
for i in range(N + 1):
	G[i]["eda"] = []
	G[i]["second"] = set()
	G[i]["third"] = set()
	G[i]["num"] = -1
for i in range(M):
	G[uv[i][0]]["eda"].append(uv[i][1])
for i in range(N + 1):
	for node in G[i]["eda"]:
		G[i]["second"] = G[i]["second"] | set(G[node]["eda"])
for i in range(N + 1):
	for node in G[i]["eda"]:
		G[i]["third"] = G[i]["third"] | G[node]["second"]

node_set = [S]
G[S]["num"] = 0
times = 1
while True:
	node_set2 = []
	for node in node_set:
		if T in G[node]["third"]:
			print(times)
			exit()
		for node2 in G[node]["third"]:
			if G[node2]["num"] == -1:
				G[node2]["num"] = times
				node_set2.append(node2)

	if len(node_set2) == 0:
		print(-1)
		exit()
	node_set = copy.deepcopy(node_set2)
	times += 1

Fixed submission:


import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))

graph = [[] for _ in range(3*N)]

for i in range(M):
	u, v = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u%(3*N)].append((v + N)%(3*N))
	graph[(u + N) % (3 * N)].append((v+2*N)%(3*N))
	graph[(u + 2*N) % (3 * N)].append(v % (3 * N))
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print(dist[T]//3)
else:
	print(-1)

Buggy python submission (verdict: Runtime Error):
NM=list(map(int,input().split()))
N=NM[0]
M=NM[1]
graph=[[] for j in range(N)]
 
for i in range(M):
  edge=list(map(int,input().split()))
  graph[edge[0]-1].append(edge[1]-1)
  
ST=list(map(int,input().split()))
S=ST[0]-1
T=ST[1]-1
 
 
 
first=[]
second=[]
third=[]
able=set([S])
 
step=0
 
while True:
  first=[]
  second=[]
  third=[]
  judge = 0
  for i in range(len(able)):
    for j in range(len(graph[able[i]])):
      if not (graph[able[i]][j] in first):
        first.append(graph[able[i]][j])
  for i in range(len(first)):
    for j in range(len(graph[first[i]])):
      if not (graph[first[i]][j] in second):
        second.append(graph[first[i]][j])
  for i in range(len(second)):
    for j in range(len(graph[second[i]])):
      if not (graph[second[i]][j] in third):
        third.append(graph[second[i]][j])
  able=able&set(third)
  if judge == 0:
    print(-1)
    break
  step+=1
  if T in able:
    print(step)
    break

Fixed submission:


import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))

graph = [[] for _ in range(3*N)]

for i in range(M):
	u, v = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u%(3*N)].append((v + N)%(3*N))
	graph[(u + N) % (3 * N)].append((v+2*N)%(3*N))
	graph[(u + 2*N) % (3 * N)].append(v % (3 * N))
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print(dist[T]//3)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

N, M = list(map(int, input().split()))
uv = []
for i in range(M):
	uv.append(list(map(int, input().split())))
S, T = list(map(int, input().split()))
G = [dict() for i in range(N+1)]
for i in range(N + 1):
	G[i]["eda"] = []
	G[i]["num"] = -1
for i in range(M):
	G[uv[i][0]]["eda"].append(uv[i][1])
node_set = [S]
G[S]["num"] = 0
time = 1
while True:
	judge = 0
	first = []
	second = []
	for node in node_set:
		first.extend(G[node]["eda"])
	for node in first:
		second.extend(G[node]["eda"])
	node_set = []
	for node in second:
		if len(G[node]["eda"]) > 0:
			for eda in G[node]["eda"]:
				if eda == T:
					print(time)
					exit()
				if G[eda]["num"] == -1:
					node_set.append(eda)
					G[eda]["num"] == time
					judge = 1
	if judge == 0:
		print(-1)
		exit()
	time += 1

Fixed submission:


import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))

graph = [[] for _ in range(3*N)]

for i in range(M):
	u, v = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u%(3*N)].append((v + N)%(3*N))
	graph[(u + N) % (3 * N)].append((v+2*N)%(3*N))
	graph[(u + 2*N) % (3 * N)].append(v % (3 * N))
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print(dist[T]//3)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
NM=list(map(int,input().split()))
N=NM[0]
M=NM[1]
graph=[[] for j in range(N)]

for i in range(M):
  edge=list(map(int,input().split()))
  graph[edge[0]-1].append(edge[1]-1)
  
ST=list(map(int,input().split()))
S=ST[0]-1
T=ST[1]-1



first=[]
second=[]
third=[]
able=[S]

step=0

while True:
  first=[]
  second=[]
  third=[]
  judge = 0
  for i in range(len(able)):
    for j in range(len(graph[able[i]])):
      if not (graph[able[i]][j] in first):
        first.append(graph[able[i]][j])
  for i in range(len(first)):
    for j in range(len(graph[first[i]])):
      if not (graph[first[i]][j] in second):
        second.append(graph[first[i]][j])
  for i in range(len(second)):
    for j in range(len(graph[second[i]])):
      if not (graph[second[i]][j] in third):
        third.append(graph[second[i]][j])
  for i in range(len(third)):
      if not third[i] in able:
        able.append(third[i])
        judge = 1
  if judge == 0:
    print(-1)
    break
  step+=1
  if T in able:
    print(step)
    break
    
  

      




Fixed submission:


import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))

graph = [[] for _ in range(3*N)]

for i in range(M):
	u, v = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u%(3*N)].append((v + N)%(3*N))
	graph[(u + N) % (3 * N)].append((v+2*N)%(3*N))
	graph[(u + 2*N) % (3 * N)].append(v % (3 * N))
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print(dist[T]//3)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
NM=list(map(int,input().split()))
N=NM[0]
M=NM[1]
graph=[[] for j in range(N)]

for i in range(M):
  edge=list(map(int,input().split()))
  graph[edge[0]-1].append(edge[1]-1)
  
ST=list(map(int,input().split()))
S=ST[0]-1
T=ST[1]-1



first=[]
second=[]
third=[]
able=[S]

step=0

while True:
  first=[]
  second=[]
  third=[]
  judge = 0
  for i in range(len(able)):
    for j in range(len(graph[able[i]])):
      if not (graph[able[i]][j] in first):
        first.append(graph[able[i]][j])
  for i in range(len(first)):
    for j in range(len(graph[first[i]])):
      if not (graph[first[i]][j] in second):
        second.append(graph[first[i]][j])
  for i in range(len(second)):
    for j in range(len(graph[second[i]])):
      if not (graph[second[i]][j] in third):
        third.append(graph[second[i]][j])
  for i in range(len(third)):
      if not third[i] in able:
        able.append(third[i])
        judge = 1
  if judge == 0:
    print(-1)
    break
  step+=1
  if T in able:
    print(step)
    break
    
  

      




Fixed submission:


import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))

graph = [[] for _ in range(3*N)]

for i in range(M):
	u, v = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u%(3*N)].append((v + N)%(3*N))
	graph[(u + N) % (3 * N)].append((v+2*N)%(3*N))
	graph[(u + 2*N) % (3 * N)].append(v % (3 * N))
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print(dist[T]//3)
else:
	print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
NM=list(map(int,input().split()))
N=NM[0]
M=NM[1]
graph=[[0 for i in range(N)] for j in range(N)]

for i in range(M):
  edge=list(map(int,input().split()))
  graph[edge[0]-1][edge[1]-1]=1
  
ST=list(map(int,input().split()))
S=ST[0]-1
T=ST[1]-1



first=[]
second=[]
third=[]
able=[S]

step=0

while True:
  first=[]
  second=[]
  third=[]
  judge = 0
  for i in range(len(able)):
    for j in range(N):
      if (graph[able[i]][j] == 1) and not (j in first):
        first.append(j)
  for i in range(len(first)):
    for j in range(N):
      if (graph[first[i]][j] == 1) and not (j in second):
        second.append(j)
  for i in range(len(second)):
    for j in range(N):
      if (graph[second[i]][j] == 1) and not (j in third):
        third.append(j)
  for i in range(len(third)):
      if not third[i] in able:
        able.append(third[i])
        judge = 1
  if judge == 0:
    print(-1)
    break
  step+=1
  if T in able:
    print(step)
    break
    
  

      




Fixed submission:


import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))

graph = [[] for _ in range(3*N)]

for i in range(M):
	u, v = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u%(3*N)].append((v + N)%(3*N))
	graph[(u + N) % (3 * N)].append((v+2*N)%(3*N))
	graph[(u + 2*N) % (3 * N)].append(v % (3 * N))
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print(dist[T]//3)
else:
	print(-1)