Problem: 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.

Submission attempts (in order):
import sys
from collection import deque

def main():
    input = sys.stdin.readline
    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[3*u].append(3*v+1)
        G[3*u+1].append(3*v+2)
        G[3*u+2].append(3*v)

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

    cnt = 0
    q = deque()
    q.append(S)
    visited = [False] * (3*N)
    visited[S] = True
    while len(q) > 0:
        q_ = deque()
        cnt += 1
        while len(q) > 0:
            n = q.pop()
            for m in G[n]:
                if visited[m]:
                    continue

                if m == T:
                    return cnt

                visited[m] = True
                q_.append(m)

        q = q_

    return -1


if __name__ == '__main__':
    print(main())


import sys
from collections import deque
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    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)
    S, T = map(int, input().split())
    S, T = S-1, T-1

    q = deque()
    q.append(S)
    cnt = 0
    cnt_k = 0
    visited = [False] * N
    visited[S] = True
    while len(q) > 0:
        cnt += 1
        if cnt % 3 == 0:
            cnt_k += 1

        while len(q) > 0:
            n0 = q.pop()
            next_ = set()
            for n1 in G[n0]:
                if cnt % 3 == 0:
                    if n1 == T:
                        return cnt_k
                    visited[n1] = True

                if visited[n1]:
                    continue

                next_.add(n1)

        q = deque()
        q.extend(list(next_))

    return -1


if __name__ == '__main__':
    print(main())


import sys
from collections import deque

def main():
    input = sys.stdin.readline
    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[3*u].append(3*v+1)
        G[3*u+1].append(3*v+2)
        G[3*u+2].append(3*v)

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

    cnt = 0
    q = deque()
    q.append(S)
    visited = [False] * (3*N)
    visited[S] = True
    while len(q) > 0:
        q_ = deque()
        cnt += 1
        while len(q) > 0:
            n = q.pop()
            for m in G[n]:
                if visited[m]:
                    continue

                if m == T:
                    return cnt // 3

                visited[m] = True
                q_.append(m)

        q = q_

    return -1


if __name__ == '__main__':
    print(main())


Verdicts: Runtime Error

Wrong Answer

Accepted