Problem:


Score : 500 points

Problem Statement

Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G.
G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.

First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.

Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq \min(10^5, N (N-1))

1 \leq u_i, v_i \leq N(1 \leq i \leq M)

u_i \neq v_i (1 \leq i \leq M)

If i \neq j, (u_i, v_i) \neq (u_j, v_j).

1 \leq S, T \leq N

S \neq T

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
:
u_M v_M
S T

Output

If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1.
If he can, print the minimum number of ken-ken-pa needed to reach vertex T.

Sample Input 1

4 4
1 2
2 3
3 4
4 1
1 3

Sample Output 1

2

Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.

Sample Input 2

3 3
1 2
2 3
3 1
1 2

Sample Output 2

-1

Any number of ken-ken-pa will bring Ken back to Vertex 1, so he cannot reach Vertex 2, though he can pass through it in the middle of a ken-ken-pa.

Sample Input 3

2 0
1 2

Sample Output 3

-1

Vertex S and Vertex T may be disconnected.

Sample Input 4

6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6

Sample Output 4

2



Sample input:
4 4
1 2
2 3
3 4
4 1
1 3


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    inv_adj = [set() for _ in range(n)]
    inv_dist_2 = [set() for _ in range(n)]
    inv_hopstepjump = [set() for _ in range(n)]

    for _ in range(m):
        u, v = mi_0()
        inv_adj[v].add(u)
    
    for i in range(n):
        for s in inv_adj[i]:
            inv_dist_2[i] |= inv_adj[s]
        
    for i in range(n):
        for s in inv_dist_2[i]:
            inv_hopstepjump[i] |= inv_adj[s]

    start, goal = mi_0()

    appeared_vertice_set = set([goal])
    q = deque([(goal, 0)])
    while q:
        # print(q)
        u, turn = q.popleft()
        if turn >= n:
            break
        if u == start:
            print(turn)
            exit()
        for v in inv_hopstepjump[u]:
            if v not in appeared_vertice_set:
                appeared_vertice_set.add(v)
                q.append((v, turn + 1))
    print(-1)
        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    adj = [[] for _ in range(n)]
    inv_adj = [[] for _ in range(n)]
    for _ in range(m):
        u, v = mi_0()
        adj[u].append(v)
        inv_adj[v].append(u)
    
    inv_dist_2 = [set() for _ in range(n)]
    for i in range(n):
        for s in inv_adj[i]:
            for t in inv_adj[s]:
                inv_dist_2[i].add(t)
    inv_dist_3 = [set() for _ in range(n)]
    for i in range(n):
        for s in list(inv_dist_2[i]):
            for t in inv_adj[s]:
                inv_dist_3[i].add(t)

    start, goal = mi_0()
    # print(inv_adj)
    # print(inv_dist_2)
    # print(inv_dist_3)

    appeared_vertice_set = set([goal])
    q = deque([(goal, 0)])
    while q:
        # print(q)
        u, turn = q.popleft()
        if turn >= n:
            break
        if u == start:
            print(turn)
            exit()
        next_pebble = list(inv_dist_3[u])
        for v in next_pebble:
            if v not in appeared_vertice_set:
                appeared_vertice_set.add(v)
                q.append((v, turn + 1))
    print(-1)
        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

Ken = [[] for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    Ken[u - 1].append(v - 1)

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


Ken2 = [[] for i in range(n)]
for s, kens in enumerate(Ken):
    for ken in kens:
        for ken2 in Ken[ken]:
            Ken2[s].append(ken2)

Pa = [[] for i in range(n)]
for s, ken2s in enumerate(Ken2):
    for ken2 in ken2s:
        for pa in Ken[ken2]:
            Pa[s].append(pa)

D = [10 ** 100] * n
D[S] = 0

from collections import deque
V = deque([(S, 0)])
while V:
    s, d = V.popleft()
    for pa in Pa[s]:
        if d + 1 < D[pa]:
            V.append((pa, d + 1))
            D[pa] = d + 1

print(D[T] if D[T] != 10**100 else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
path = [[set() for _ in range(n)] for _ in range(3)]
for _ in range(m):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    path[0][u].add(v)

s,t = map(int,input().split())
for i in range(2):
    for j in range(n):
        for k in path[i][j]:
            path[i+1][j] = path[i+1][j] | path[0][k]
que = deque([s-1])
d = [float('inf')]*n
d[s-1] = 0
while que:
    p = que.popleft()
    for to in path[2][p]:
        if d[to] == float('inf'):
            d[to] = d[p] + 1
            que.append(to)
if d[t-1] == float('inf'):
    d[t-1] = -1
print(d[t-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v + N)
        g[u + N].add(v + N * 2)
        g[u + N * 2].add(v)

    S, T = (int(x) - 1 for x in input().split())

    dist = [-1] * (N * 3)
    dist[S] = 0

    dq = deque()
    dq.append(S)

    while dq:
        v = dq.popleft()
        d = dist[v]
        for u in g[v]:
            if (~dist[u]) and (dist[u] < d): continue
            dist[u] = d + 1
            dq.append(u)

    ans = dist[T] // 3

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
UV = [[] for _ in range(n)]
for _ in range(m):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    UV[u].append(v)
s, t = list(map(lambda x: int(x)-1, input().split()))

edges = [set()for _ in range(n)]

for v in range(n):
    for v2 in UV[v]:
        for v3 in UV[v2]:
            for v4 in UV[v3]:
                edges[v].add(v4)

INF = 10**18
dist = [INF]*n
dist[s] = 0
next_v = deque([s])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)
print(dist[t]if dist[t] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
UV = [[] for _ in range(n)]
for _ in range(m):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    UV[u].append(v)
s, t = list(map(lambda x: int(x)-1, input().split()))

edges = [[]for _ in range(n)]

for v in range(n):
    for v2 in UV[v]:
        for v3 in UV[v2]:
            for v4 in UV[v3]:
                edges[v].append(v4)

INF = 10**18
dist = [INF]*n
dist[s] = 0
next_v = deque([s])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)
print(dist[t]if dist[t] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[u].append(v)

S, T = map(int, input().split())
S -= 1; T -= 1

memo = {}
def search(node, k):
  global memo
  s = set()
  if k == 0:
    return set([node])
  if (node, k) in memo:
    return memo[(node, k)]
  children = graph[node]
  for child in children:
    s |= search(child, k-1)
  memo[(node, k)] = s
  return s


# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  g[i] = search(i, 3)

dist = [-1] * N
dist[S] = 0
d = deque([[S, -1]])
while d:
  node, par = d.popleft()
  children = g[node]
  for child in children:
    if dist[child] < 0:
      dist[child] = dist[node] + 1
      d.append([child, node])

if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[u].append(v)

S, T = map(int, input().split())
S -= 1; T -= 1
  
def search(node, k):
  s = set()
  if k == 0:
    return set([node])
  children = graph[node]
  for child in children:
    s |= search(child, k-1)
  return s


# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  g[i] = search(i, 3)

dist = [-1] * N
dist[S] = 0
d = deque([[S, -1]])
while d:
  node, par = d.popleft()
  children = g[node]
  for child in children:
    if dist[child] < 0:
      dist[child] = dist[node] + 1
      d.append([child, node])

if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[u].append(v)

# 距離が3のノード間にだけ辺を張り直す
row = []
col = []
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    s = set()
    for j in range(n):
      node = d.popleft()
      if node in s:
        continue
      s.add(node)
      children = graph[node]
      d.extend(children)
  _g = list(set(d))
  row.extend([i] * len(_g))
  col.extend(_g)

d = [1] * len(row)
graph = csr_matrix((d, (row, col)), shape=(N, N))
S, T = map(int, input().split())
S -= 1; T -= 1
dist = dijkstra(graph, indices=S).astype(int)
if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[u].append(v)

# 距離が3のノード間にだけ辺を張り直す
row = []
col = []
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    for j in range(n):
      node = d.popleft()
      children = graph[node]
      d.extend(children)
  _g = list(set(d))
  row.extend([i] * len(_g))
  col.extend(_g)

d = [1] * len(row)
graph = csr_matrix((d, (row, col)), shape=(N, N))
S, T = map(int, input().split())
S -= 1; T -= 1
dist = dijkstra(graph, indices=S).astype(int)
if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
row = []
col = []
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  row.extend([3*u, 3*u+1, 3*u+2])
  col.extend([3*v+1, 3*v+2, 3*v])

d = [1] * (3*M)

graph = csr_matrix((d, (row, col)), shape=(3*N, 3*N))

S, T = map(int, input().split())
S -= 1; T -= 1
dist = dijkstra(graph, indices=3*S).astype(int)

if dist[3*T] > 0:
  print(dist[3*T] // 3)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
row = []
col = []
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  row.extend([3*u, 3*u+1, 3*u+2])
  col.extend([3*v+1, 3*v+2, 3*v])

d = [1] * (3*M)

graph = csr_matrix((d, (row, col)), shape=(3*N, 3*N))

S, T = map(int, input().split())
S -= 1; T -= 1
dist = dijkstra(graph, indices=3*S).astype(int)

if dist[3*T] > 0:
  print(dist[3*T] // 3)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[u].append(v)

# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    for j in range(n):
      node = d.popleft()
      children = graph[node]
      d.extend(children)
  g[i] = list(set(d))

S, T = map(int, input().split())
S -= 1; T -= 1
d = deque([[S, -1]])
dist = [float('inf')] * N
dist[S] = 0
# 幅優先探索
while d:
  n = len(d)
  for i in range(n):
    node, par = d.popleft()
    children = g[node]
    for child in children:
      if child == par:
        continue
      if dist[child] > dist[node] + 1:
        dist[child] = dist[node] + 1
        d.append([child, node])
      if child == T:
        print(dist[child])
        quit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[u].append(v)

# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    for j in range(n):
      node = d.popleft()
      children = graph[node]
      d.extend(children)
  g[i] = d

S, T = map(int, input().split())
S -= 1; T -= 1
d = deque([[S, -1]])
dist = [float('inf')] * N
dist[S] = 0
# 幅優先探索
while d:
  n = len(d)
  for i in range(n):
    node, par = d.popleft()
    children = g[node]
    for child in children:
      if child == par:
        continue
      dist[child] = min(dist[child], dist[node] + 1)
      if child == T:
        print(dist[child])
        quit()
      d.append([child, node])

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
N, M = map(int, input().split())
INF = -1
dist = [[INF]*3 for _ in range(N)]
vector = [[] for _ in range(N)]

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1].append(graf2-1)
S, T = map(int, input().split())
S, T = S-1, T-1

# BFS
dist[S][0] = 0
q = Queue(3*N+1)
q.put((S, 0))
while not q.empty():
    v, l = q.get()
    for i in vector[v]:
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        q.put((i, new_l))

ans = dist[T][0]
if ans == INF:
    print("-1")
else:
    print(int(ans/3))

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
N, M = map(int, input().split())
INF = -1
dist = [[INF]*3 for _ in range(N)]
vector = [[0]*N for _ in range(N)]

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1][graf2-1] = 1
S, T = map(int, input().split())
S, T = S-1, T-1

# BFS
dist[S][0] = 0
q = Queue(3*N+1)
q.put((S, 0))
while not q.empty():
    v, l = q.get()
    for i in range(N):
        if vector[v][i] != 1:
            continue
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        q.put((i, new_l))

ans = dist[T][0]
if ans == INF:
    print("-1")
else:
    print(int(ans/3))

Submission status: Time Limit Exceeded

Solution code:
import sys #追加
sys.setrecursionlimit(500*500) #追加
n,m=map(int,input().split())
edge = [[] for i in range(n*3)]
#edge[i] : iから出る道の[行先]の配列
for i in range(m):
    x,y = map(int,input().split())
    x-=1;y-=1
    x*=3;y*=3
    edge[x  ].append(y+1)
    edge[x+1].append(y+2)
    edge[x+2].append(y  )
    
def dfs(s,g,res):
  if s==g or s==g+1 or s==g+2:
    if res%3==0:
      return res//3
  
  if res>m*3:
    return float("inf")
  
  l=float("inf")
  for i in edge[s]:
    l=min(l,dfs(i,g,res+1))
  return l
s,t=map(int,input().split())
s-=1;t-=1
ans=dfs(s*3,t*3,0)
if ans==float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys; input = sys.stdin.readline
from collections import deque

def main():
    n, m = map(int, input().split())
    dest = [[] for i in range(n)]
    for i in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        dest[u].append(v)
    s, t = map(int, input().split())
    s -= 1; t -= 1
    q = deque()
    queued = [[False for j in range(3)] for i in range(n)]
    q.append((s, 0, 0)); queued[s][0] = True
    while q:
        i, k, d = q.popleft()
        if (i, k) == (t, 0):
            print(d // 3)
            return
        k2 = (k + 1) % 3
        for j in dest[i]:
            if queued[j][k2]:
                continue
            q.append((j, k2, d + 1))
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import deque

def main():
    n, m = map(int, input().split())
    dest = [[] for i in range(n)]
    for i in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        dest[u].append(v)
    s, t = map(int, input().split())
    s -= 1; t -= 1
    q = deque()
    queued = [[False for j in range(3)] for i in range(n)]
    q.append((s, 0, 0)); queued[s][0] = True
    while q:
        i, k, d = q.popleft()
        if (i, k) == (t, 0):
            print(d // 3)
            return
        k2 = (k + 1) % 3
        for j in dest[i]:
            if queued[j][k2]:
                continue
            q.append((j, k2, d + 1))
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
graph = [[[] for i in range(3)] for j in range(n+1)]
for i in range(m):
  u,v = map(int,input().split())
  graph[u][0].append(v)
s,t = map(int,input().split())
for i in range(1,3):
  for j in range(1,n+1):
    l = set([])
    for k in graph[j][0]:
      l = l | set(graph[k][i-1])
    graph[j][i] = list(l)
for i in range(n+1):
  graph[i] = graph[i][2]
cnt = 0
done = [0]*(n+1)
done[s] = 1
wait = deque([s])
while wait:
  cnt += 1
  q = wait
  wait = deque([])
  for i in q:
    for j in graph[i]:
      if not done[j]:
        wait.append(j)
        done[j] = 1
      if j == t:
        print(cnt)
        quit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
n,m = map(int,input().split())
graph = [[[] for i in range(3)] for j in range(n+1)]
for i in range(m):
  u,v = map(int,input().split())
  graph[u][0].append(v)
s,t = map(int,input().split())
for i in range(1,3):
  for j in range(1,n+1):
    l = set([])
    for k in graph[j][0]:
      l = l | set(graph[k][i-1])
    graph[j][i] = list(l)
for i in range(n+1):
  graph[i] = graph[i][2]
cnt = 0
done = [0]*(n+1)
done[s] = 1
wait = deque([s])
while wait:
  cnt += 1
  q = copy.copy(wait)
  wait = deque([])
  for i in q:
    for j in graph[i]:
      if not done[j]:
        wait.append(j)
        done[j] = 1
      if j == t:
        print(cnt)
        quit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

def MI():return map(int,input().split())
def LI():return list(MI())

from collections import deque
n,m=MI()
G=[[] for i in range(n)]
# print(G)
for i in range(m):
    u,v=MI()
    G[u-1].append(v-1)

    
s,t=MI()
s=s-1
t=t-1


dq=deque([])

visited=[False]*n
dq.append(s)
depth=0
for i in range(1,10**6+1):
    par_list=[]
    while dq:
        try:
            p=dq.popleft()
            if visited[p]==True:
                continue
            else:
                visited[p]=True
                par_list.append(p)
        except:
            break
    depth+=1
    #print(depth)
    #print(par_list)
    if len(par_list)==0:
      break
    for par in par_list:
        for c1 in G[par]:
            for c2 in G[c1]:
                for c3 in G[c2]:
                    if c3==t:
                        #print(par,c1,c2,c3,"yay")
                        print(depth)
                        exit()
                    if visited[c3]==False:
                        dq.append(c3)
                        visited[c3]==True
    
                    #print(par,c1,c2,c3,end=" ")
                    #print()
    #print(i,len(dq),dq)
    
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush, heapify
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
INF = float("inf")

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(lambda x: int(x)-1, input().split())
    g[u].append(v)
s, t = map(lambda x: int(x)-1, input().split())

g2 = [set() for _ in range(n)]
visited = [False] * n

def dfs(v):
    if visited[v]: return
    visited[v] = True
    for nv1 in g[v]:
        for nv2 in g[nv1]:
            for nv3 in g[nv2]:
                if nv3 not in g2[v]:
                    g2[v].add(nv3)
                    dfs(nv3)

for i in range(n): dfs(i)
for i in range(n):
    g2[i] = list(map(lambda x: (x, 1), list(g2[i])))

def dijkstra(graph, n, s):
    d = [INF] * n
    d[s], q = 0, []
    heappush(q, (0, s))
    while q:
        dist, v = heappop(q)
        if d[v] < dist: continue
        for nv, cost in graph[v]:
            if d[nv] > d[v] + cost:
                d[nv] = d[v] + cost
                heappush(q, (d[nv], nv))
    return d

ans = dijkstra(g2, n, s)[t]
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush, heapify
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
INF = float("inf")

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(lambda x: int(x)-1, input().split())
    g[u].append(v)
s, t = map(lambda x: int(x)-1, input().split())

g2 = [[] for _ in range(n)]
visited = [False] * n

def dfs(v):
    if visited[v]: return
    visited[v] = True
    for nv1 in g[v]:
        for nv2 in g[nv1]:
            for nv3 in g[nv2]:
                g2[v].append((nv3, 1))
                dfs(nv3)

for i in range(n): dfs(i)

def dijkstra(graph, n, s):
    d = [INF] * n
    d[s], q = 0, []
    heappush(q, (0, s))
    while q:
        dist, v = heappop(q)
        if d[v] < dist: continue
        for nv, cost in graph[v]:
            if d[nv] > d[v] + cost:
                d[nv] = d[v] + cost
                heappush(q, (d[nv], nv))
    return d

ans = dijkstra(g2, n, s)[t]
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush, heapify
sys.setrecursionlimit(10**7)
INF = float("inf")

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(lambda x: int(x)-1, input().split())
    g[u].append(v)
s, t = map(lambda x: int(x)-1, input().split())

g2 = [[] for _ in range(n)]
visited = [False] * n

def dfs(v):
    if visited[v]: return
    visited[v] = True
    for nv1 in g[v]:
        for nv2 in g[nv1]:
            for nv3 in g[nv2]:
                g2[v].append((nv3, 1))
                dfs(nv3)

for i in range(n): dfs(i)

def dijkstra(graph, n, s):
    d = [INF] * n
    d[s], q = 0, []
    heappush(q, (0, s))
    while q:
        dist, v = heappop(q)
        if d[v] < dist: continue
        for nv, cost in graph[v]:
            if d[nv] > d[v] + cost:
                d[nv] = d[v] + cost
                heappush(q, (d[nv], nv))
    return d

ans = dijkstra(g2, n, s)[t]
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# 12:55~
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
uv = [list(map(int,input().split())) for _ in range(M)]
S,T = map(int,input().split())

S -= 1
T -= 1
#%%
adj_list = [[[] for _ in range(3)] for _ in range(N)]
for u,v in uv:
    for i in range(3):
        adj_list[u-1][i].append([v-1,(i+1)%3])


INF = 10**9+7
dist = [[INF]*3 for _ in range(N)]
dist[S][0] = 0

stack = [[S,0,0]]
while stack:
    v,c,count = stack.pop()
    nxt_v = adj_list[v][c]
    for nv,nc in nxt_v:
        if dist[nv][nc]>(count+1)//3:
            dist[nv][nc] = (count+1)//3
            stack.append([nv,(c+1)%3,count+1])
            
            
if dist[T][0]==INF:
    ans = -1
else:
    ans = dist[T][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# 12:55~
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
uv = [list(map(int,input().split())) for _ in range(M)]
S,T = map(int,input().split())

S -= 1
T -= 1
#%%
adj_list = [[] for _ in range(N)]
for u,v in uv:
    adj_list[u-1].append(v-1)

INF = 10**9+7
dist = [[INF]*3 for _ in range(N)]
dist[S][2] = 0

stack = [[S,0]]
while stack:
    v,count = stack.pop()
    nxt_v = adj_list[v]
    cnt = count%3
    for nv in nxt_v:
        if dist[nv][cnt]>(count+1)//3:
            dist[nv][cnt] = (count+1)//3
            stack.append([nv,count+1])
            
            
if dist[T][2]==INF:
    ans = -1
else:
    ans = dist[T][2]
print(ans)