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: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    n,m = map(int,input().split())

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

    s,t = map(int,input().split())

    fi = [True]*(n+1)
    se = [True]*(n+1)
    th = [True]*(n+1)
    th[s] = False

    now = [s]
    tank = []
    cnt = 0

    while len(now) != 0:
        cnt += 1
        tank = []
        tank2 = []
        tank3 = []
        for e in now:
            for a in edge[e]:
                if fi[a]:
                    fi[a] = False
                    tank2.append(a)

        for e in tank2:

            for a in edge[e]:
                if se[a]:
                    se[a] = False
                    tank3.append(a)
        
        for e in tank3:
            for a in edge[e]:
                if th[a]:
                    th[a] = False
                    tank.append(a)
                if a == t:
                    print(cnt)
                    exit()

        now = tank
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    E[u].append(v)
Closed = [[False]*(N+1) for _ in range(3)]
S, T = map(int, input().split())
st = [(S, 0)]
Closed[0][S] = True
ans = 0
while len(st):
    st_new = []
    for v, n in st:
        if v==T and n==0:
            print(ans // 3)
            exit()
        n1 = (n+1)%3
        Cl = Closed[n1]
        for u in E[v]:
            if not Cl[u]:
                st_new.append((u, n1))
                Cl[u] = True
    st = st_new
    ans += 1

print(-1)

Submission status: Accepted

Solution code:

n, m = map(int, input().split())
A = [list(map(int, input().split())) for i in range(m)]
s, t = map(int, input().split())

saki = [[] for i in range(n+1)]
for i in range(m):
    saki[A[i][0]].append(A[i][1])

F = [[-1,-1,-1] for i in range(n+1)]

# print(saki)

def idou(x, y):
    # print(F)
    if F[x][y%3] == -1:
        F[x][y%3] = y
        #print(F)
        for item in saki[x]:
            #print(item)
            if F[item][(y+1)%3] == -1:
                #print("m")
                mada[(y+1)%3].append([item,y+1])
    # print(mada)

mada = [[] for i in range(3)]
a=0
b=0
c=0

idou(s,0)
# print("while")
while a<len(mada[0]) or b<len(mada[1]) or c<len(mada[2]):
    while a<len(mada[0]):
        # print("a")
        idou(mada[0][a][0], mada[0][a][1])
        a += 1
    while b<len(mada[1]):
        # print("b")
        idou(mada[1][b][0], mada[1][b][1])
        b += 1
    while c<len(mada[2]):
        # print("c")
        idou(mada[2][c][0], mada[2][c][1])
        c += 1
# print(F)
print(F[t][0]//3)

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline
N, M = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, readline().split())
    G[u-1].append(v-1)
S, T = map(int, readline().split())
S -= 1; T -= 1

INF = 10**9
U = [[INF]*N for i in range(3)]
U[0][S] = 0
que = deque([(S, 0)])
while que:
    v, t = que.popleft()
    u = (t+1) % 3
    d = U[t][v]
    if t == 2:
        d += 1
    Uu = U[u]
    for w in G[v]:
        if Uu[w] != INF:
            continue
        que.append((w, u))
        Uu[w] = d
print(U[0][T] if U[0][T] < INF else -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))


def dijkstra(g, src, dst):
    import heapq

    min_cost = [[float('inf')] * 3 for _ in range(len(g))]

    node_heap = []
    heapq.heappush(node_heap, (0, 0, src))
    while node_heap:
        cost, hop, node = heapq.heappop(node_heap)
        if min_cost[node][hop] <= cost:
            continue
        min_cost[node][hop] = cost

        for _, d, c in g.edges(node):
            dc = min_cost[node][hop] + c
            dh = (hop + 1) % 3
            heapq.heappush(node_heap, (dc, dh, d))
    ret = min_cost[dst][0] // 3
    if isnan(ret):
        return -1
    return ret



def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    es = [(cu - 1, cv - 1, 1) for cu, cv in zip(u, v)]
    g = DGraph(N, es)

    S = S - 1
    T = T - 1
    cost = dijkstra(g, S, T)
    return cost


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]" 
    v = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    result = solve(N, M, u, v, S, T)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m =  map(int,input().split())
l = [list() for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    l[a].append(b)
s,t = map(int,input().split())

reach = [[-1,-1,-1] for _ in range(n+1)]
reach[s][0] = 0
bfs = deque()
bfs.append((s,0))
while bfs:
    cur,dis = bfs.popleft()
    for x in l[cur]:
        if reach[x][(dis+1)%3] < 0:
            bfs.append((x,dis+1))
            reach[x][(dis+1)%3] = dis+1
ans = reach[t][0]
if ans > 2:
  ans //= 3
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
lines = sys.stdin.readlines()
for line in lines[:-1]:
    u, v = list(map(int, line.split()))
    u -= 1
    v -= 1
    links[u].add(v)
s, t = list(map(int, lines[-1].split()))
s -= 1
t -= 1

q = [(0, s)]
visited = set()
ans = -1
while q:
    c, v = heappop(q)
    key = (c % 3, v)
    if key in visited:
        continue
    visited.add(key)
    if v == t and c % 3 == 0:
        ans = c // 3
        break
    c += 1
    d = c % 3
    for u in links[v]:
        new_key = (d, u)
        if new_key in visited:
            continue
        heappush(q, (c, u))

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
o=inputs()
s,T=map(int,o.pop().split())
for i in o:
    _,__=map(int,input().split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=[0]*(3*n+3)
seen[3*s]=1
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if seen[t]==0:
            dq.append((t,c+1))
            seen[t]=1
print("-1")

Submission status: Runtime Error

Solution code:
def dfs(u,c):
  nc=(c+1)%3
  for v in to[u]:
    if d[v][nc]<d[u][c]+1: continue;
    d[v][nc]=d[u][c]+1
    dfs(v,nc)


def main():
  for i in range(m):
    u,v=map(lambda x:int(x)-1,input().split())
    to[u].append(v)
  s,t=map(lambda x:int(x)-1,input().split())

  d[s][0]=0
  dfs(s,0)
  
  #print(d)
  ans=d[t][0]
  print(ans//3 if ans!=INF else -1)

  
if __name__=='__main__':
  n,m=map(int,input().split())
  INF=10**9
  d=[[INF]*3 for i in range(n)]
  to=[[] for i in range(n)]
  s=t=0
  main()

Submission status: Runtime Error

Solution code:
import sys

from queue import Queue
import numpy as np
from numba import njit


@njit("i8[:, :](i8[:, :])")
def pow3(path):
    return np.dot(np.dot(path, path), path)


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    path = np.zeros((n + 1, n + 1), dtype="i8")
    for _ in range(m):
        u, v = map(int, input().split())
        path[u, v] = 1
    path = pow3(path)
    s, t = map(int, input().split())
    visited = [False] * 110000
    q = Queue()
    q.put((s, 0))
    visited[s] = True
    while not q.empty():
        now, num_move = q.get()
        for nxt in range(1, n + 1):
            if path[now, nxt] == 0:
                continue
            if nxt == t:
                print(num_move + 1)
                sys.exit()
            if not visited[nxt]:
                q.put((nxt, num_move + 1))
                visited[nxt] = True
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

from queue import Queue
import numpy as np


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    path = np.matrix(np.zeros((n + 1, n + 1), dtype="i8"))
    for _ in range(m):
        u, v = map(int, input().split())
        path[u, v] = 1
    path **= 3
    s, t = map(int, input().split())
    visited = [False] * 110000
    q = Queue()
    q.put((s, 0))
    while not q.empty():
        now, num_move = q.get()
        if visited[now]:
            continue
        for nxt in range(1, n + 1):
            if path[now, nxt] == 0:
                continue
            if nxt == t:
                print(num_move + 1)
                sys.exit()
            if not visited[nxt]:
                q.put((nxt, num_move + 1))
        visited[now] = True
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
graph = defaultdict(list)

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)


s, t = map(int, input().split())

q = [s]

pattern = []
cnt = 0

while True:
    for _ in range(3):
        tmp = []
        for x in q:
            tmp = list(set(tmp + graph[x]))
        q = tmp
    cnt += 1
    if t in q:
        print(cnt)
        sys.exit()
    if set(q) in pattern:
        print(-1)
        sys.exit()
    pattern.append(set(q))

Submission status: Runtime Error

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


def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra
    N = N + 1
    u = np.array(u, dtype=np.int16)
    v = np.array(v, dtype=np.int16)
    u = np.concatenate([u, u+N, u+2*N])
    v = np.concatenate([v+N, v+2*N, v])
    mat = dijkstra(csr_matrix((np.ones(3*M), (u, v)), shape=(3*N, 3*N), dtype=np.int16),
                   indices=S, directed=True)
    return -1 if np.isinf(mat[T]) else int(mat[T]) // 3

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]"
    v = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    print(solve(N, M, u, v, S, T))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def dfs(G,u,dist):
    for v in G[u]:
        if dist[v] == 10**9:
            dist[v] = dist[u] + 1
            dfs(G,v,dist)

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

G = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int,input().split())
    u, v = u-1, v-1

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

s, t = map(int,input().split())
s, t = s-1, t-1

dist = [10**9] * (3*N)
dist[s] = 0

dfs(G,s,dist)

if dist[t] == 10**9:
    print(-1)
else: 
    print(dist[t] // 3)

Submission status: Runtime Error

Solution code:
def dfs(u):
    for v in G[u]:
        if dist[v] > dist[u] + 1:
            dist[v] = dist[u] + 1
            dfs(v)

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

G = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int,input().split())
    u, v = u-1, v-1

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

s, t = map(int,input().split())
s, t = s-1, t-1

dist = [10**9] * (3*N)
dist[s] = 0

dfs(s)

if dist[t] == 10**9:
    print(-1)
else: 
    print(dist[t] // 3)

Submission status: Runtime Error

Solution code:
def dfs(G, s, dist):
    for v in G[s]:
        if dist[v] > dist[s] + 1:
            dist[v] = dist[s] + 1
            dfs(G, v, dist)

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

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

for _ in range(M):
    u, v = map(int,input().split())
    u, v = u-1, v-1

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

s, t = map(int,input().split())
s, t = s-1, t-1

dist = [10**9] * (3*N)
dist[s] = 0

dfs(G, s, dist)

if dist[t] == 10**9:
    print(-1)
else: 
    print(dist[t] // 3)

Submission status: Runtime Error

Solution code:
def dfs(G2, s, dist):
    for v in G2[s]:
        if dist[v] > dist[s] + 1:
            dist[v] = dist[s] + 1
            dfs(G2, v, dist)

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

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

G2 = [[] for _ in range(N)]

for u in range(N):
    for v1 in G[u]:
        for v2 in G[v1]:
            for v3 in G[v2]:
                if u != v3 and v3 not in G2[u]:
                    G2[u].append(v3)

s, t = map(int,input().split())

dist = [10**9] * len(G2)
dist[s-1] = 0

dfs(G2, s-1, dist)

if dist[t-1] == 10**9:
    print(-1)
else: 
    print(dist[t-1])

Submission status: Runtime Error

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

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

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = set(e[i])
        for _ in range(2):
            nxt = set()
            for __ in items:
                nxt |= set(e[__])
            items = nxt
        items -= {i}
        e3[i] = list(items)

    visited = {s}

    ans = -1
    crnt = set(e3[s])
    visited |= crnt
    if t in crnt:
        print(1)
        exit()

    cnt = 1
    while crnt:
        cnt += 1
        nxt = set()
        for ci in crnt:
            for ti in e3[ci]:
                if visited[ti]:
                    visited[ti] = False
                    nxt.add(ti)
        visited |= nxt
        crnt = nxt
        if t in crnt:
            print(cnt)
            exit()
        crnt -= visited


    print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

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

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = set(e[i])
        for _ in range(2):
            nxt = set()
            for __ in items:
                nxt |= e[__]
            items = nxt
        items -= {i}
        e3[i] = list(items)

    visited = [True for _ in range(n)]

    ans = -1
    crnt = set(e3[s])
    if t in crnt:
        print(1)
        exit()

    cnt = 1
    while crnt:
        cnt += 1
        nxt = set()
        for ci in crnt:
            for ti in e3[ci]:
                if visited[ti]:
                    visited[ti] = False
                    nxt.add(ti)
        crnt = nxt
        if t in crnt:
            print(cnt)
            exit()

    print(-1)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    for i in range(10):
    #while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    for i in range(M):
    #while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys

f = open("/Users/naoki/Documents/Atcoder/input.txt")

N, M = map(int, f.readline().split())
uvs = [list(map(lambda x:int(x)-1, f.readline().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, f.readline().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

while len(todo)>0:
    checking = todo.pop()
    next_targets = deque([checking])
    for i in range(3):
        purposes = []
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.append(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] == -10000:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

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

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    vis[now][step] = cnt
    if now == T and step  == 0:  
        print(cnt//3)
        exit()
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            q.append((x,cnt+1))
print(-1)
exit()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

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

q = collections.deque()
vis = [10**10 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        now = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = min(vis[now],cnt)
        if now == T: 
            return cnt
        for x in path[now]:
            if vis[x] == 10**10:
                q.append((x,cnt+1))
vis[S] = 1
q.append([S,0])
ans = bfs()
if vis[T] == 10**10: print(-1)
else: print(ans//3)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc132/tasks/abc132_e
# ぱっと思いつくのはダイクストラで3回で到達できる点を探索していくとかかなぁ
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret

    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため
from heapq import heapify, heappop, heappush, heappushpop


def bfs(graph, s, N):
    '''
    graph...隣接リスト形式 リスト内要素はノード
    s...始点ノード
    N...頂点数

    return
    ----------
    D ... 各点までの最短距離
    '''
    # pq = PriorityQueue([])
    cnt = 0
    pq = deque([])
    D = [2**31] * N
    D[s] = 0
    is_visited = [False] * N
    is_visited[s] = True
    pq.append((D[s], s))  # (最短距離, 次のノード)
    while pq:
        d, v = pq.popleft()
        # 探索するのはgraph[v]じゃなくてケンケンパしてたどり着くことのできるノード
        for to in next_node(v, graph):
            cnt += 1
            assert cnt < 10**7
            if is_visited[to]:
                continue
            cost = 1
            D[to] = d + cost
            is_visited[to] = True
            pq.append((D[to], to))
    return D


def next_node(v, graph):
    # 距離3のノードの集合を集めてくる
    ret = set()
    q = deque([(0, v)])
    while q:
        d, u = q.popleft()
        if d == 3:
            ret.add(u)
            continue
        for to in graph[u]:
            q.append((d + 1, to))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, M = read_ints()
graph = defaultdict(lambda: [])
for _ in range(M):
    u, v = mina(*read_ints())
    graph[u].append(v)
S, T = mina(*read_ints())
D = bfs(graph, S, N)
print(D[T] if D[T] != INF else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = deque()
d.appendleft([0,s-1])
#check[s-1][0] = 1

while len(d) > 0:
    for i in range(len(d)):
        num,ver = d.popleft()
        check[ver][num%3] = 1
        num = num+1
        #cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num%3 == 0:
                print(num//3)
                exit()
            if check[uv[ver][j]][num] == 0:
                #check[uv[ver][j]][num] = 1
                d.append([num,uv[ver][j]])
                
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = deque()
d.appendleft([0,s-1])
#check[s-1][0] = 1

while len(d) > 0:
    for i in range(len(d)):
        num,ver = d.popleft()
        check[ver][num] = 1
        num = num+1
        #cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num%3 == 0:
                print(num//3)
                exit()
            if check[uv[ver][j]][num] == 0:
                #check[uv[ver][j]][num] = 1
                d.append([num,uv[ver][j]])
                
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
import queue
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = queue.Queue()
d.put([0,0,s-1])
#check[s-1][0] = 1

while len(d) > 0:
    for i in range(len(d)):
        num,cnt,ver = d.get()
        check[ver][num] = 1
        num = (num+1)%3
        cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num == 0:
                print(cnt//3)
                exit()
            if check[uv[ver][j]][num] == 0:
                #check[uv[ver][j]][num] = 1
                d.put([num,cnt,uv[ver][j]])
                
print(-1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

import heapq
from collections import defaultdict, deque
g1 = defaultdict(set)
for u, v in uv:
    g1[u-1].add(v-1)

s -= 1
t -= 1

dist = [[float('inf')] * 3 for _ in range(n)]
dist[s][0] = 0

q = [(0, s, 0)] # (dist, pos, kenken)
heapq.heapify(q)

while q:
    du, u, c = heapq.heappop(q)
    if dist[u][c] < du:
        continue
    c2 = (c + 1) % 3
    for v in g1[u]:
        if du + 1 < dist[v][c2]:
            dist[v][c2] = du + 1
            heapq.heappush(q, (dist[v][c2], v, c2))

if dist[t][0] != float('inf'):
    print(d)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import collections
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
S,T=map(int,input().split())
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=collections.deque()
q.append([s,0])
while q:
    v,c=q.pop(0)
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]==1
print(ans)