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:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import random
import collections
import math
import itertools
import bisect

def real_main():
    n, m = read_int_array()
    g = [[] for _ in range(n)]
    for _ in range(m):
        f, t = read_int_array()
        g[f-1].append(t-1)

    vis = [[False]*3 for _ in range(n)]

    s, t = read_int_array()
    if s == t:
        print(0)
        return
    s -= 1
    t -= 1
    q = [(s, 0)]
    vis[s][0] = True
    level = 0
    while q:
        level += 1
        next_q = []
        for n, dmod in q:
            next_dmod = (dmod + 1) % 3
            for c in g[n]:
                if not vis[c][next_dmod]:
                    if c == t and next_dmod == 0:
                        print(level // 3)
                        return
                    vis[c][next_dmod] = True
                    next_q.append((c, next_dmod))
        q = next_q
    print(-1)



def solve():
    pass


def main():
    if False and 'PYCHARM_HOSTED' in os.environ:
        main_pycharm()
    else:
        real_main()


from copy import deepcopy
def main_pycharm():
    solution = solve

    test_inputs = None
    test_outputs = None
    judge = None
    slow_solution = None
    if solution is not None:
        if test_outputs is not None:
            test_with_answers(solution, test_inputs, test_outputs)
        if judge is not None:
            test_with_judge(solution, test_inputs, judge)
        if slow_solution is not None:
            test_with_slow_solution(solution, test_inputs, slow_solution)


def test_with_answers(solution, inputs, answers):
    total, wrong = 0, 0
    for args, test_ans in zip(inputs, answers):
        ans = solution(*deepcopy(args))
        if ans != test_ans:
            print('WRONG! ans=%s, test_ans=%s, args=%s' % (ans, test_ans, args))
            wrong += 1
        else:
            print('GOOD')
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_judge(solution, inputs_gen, judge):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        if not judge(deepcopy(ans), *deepcopy(args)):
            print('WRONG! ans=%s, args=%s' % (ans, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_slow_solution(solution, inputs_gen, solution_slow):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        slow = solution_slow(*deepcopy(args))
        if ans != slow:
            print('WRONG! ans=%s, slow=%s, args=%s' % (ans, slow, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))

def generate_nums(n, min, max, check_if_good=None):
    while True:
        nums = [random.randint(min, max) for _ in range(n)]
        if check_if_good is None or check_if_good(nums):
            return nums

# This mergesort can be like 7 times faster than build in sort
# (for stupid reasons)
def mergesort(A, key=lambda x: x, reverse=False):
    C = A
    A = list(range(len(A)))
    B = list(A)

    n = len(A)
    for i in range(0, n - 1, 2):
        if key(C[A[i]]) > key(C[A[i ^ 1]]):
            A[i], A[i ^ 1] = A[i ^ 1], A[i]

    width = 2
    while width < n:
        for i in range(0, n, 2 * width):
            R1, R2 = min(i + width, n), min(i + 2 * width, n)
            j, k = R1, i
            while i < R1 and j < R2:
                if key(C[A[i]]) > key(C[A[j]]):
                    B[k] = A[j]
                    j += 1
                else:
                    B[k] = A[i]
                    i += 1
                k += 1
            while i < R1:
                B[k] = A[i]
                k += 1
                i += 1
            while k < R2:
                B[k] = A[k]
                k += 1
        A, B = B, A
        width *= 2

    if reverse:
        A.reverse()
    return A

def mergesort_simple(A, reverse=False):
    C = A
    A = list(range(len(A)))
    B = list(A)

    n = len(A)
    for i in range(0, n - 1, 2):
        if C[A[i]] > C[A[i ^ 1]]:
            A[i], A[i ^ 1] = A[i ^ 1], A[i]

    width = 2
    while width < n:
        for i in range(0, n, 2 * width):
            R1, R2 = min(i + width, n), min(i + 2 * width, n)
            j, k = R1, i
            while i < R1 and j < R2:
                if C[A[i]] > C[A[j]]:
                    B[k] = A[j]
                    j += 1
                else:
                    B[k] = A[i]
                    i += 1
                k += 1
            while i < R1:
                B[k] = A[i]
                k += 1
                i += 1
            while k < R2:
                B[k] = A[k]
                k += 1
        A, B = B, A
        width *= 2

    if reverse:
        A.reverse()
    return A


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

def read():
    return input()

def read_int():
    return int(input())

def read_array(sep=None, maxsplit=-1):
    return input().split(sep, maxsplit)

def read_int_array():
    return [int(a) for a in read_array()]

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
visited = [[False,False,False] for _ in range(n)]
ren = [[] for _ in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    ren[u-1].append(v)
s,t = map(int,input().split())

Q = [(s,0)]
visited[s-1][2]=True
ans = -1

while len(Q)>0:
    curs,curcount = Q.pop(0)
    if curs == t:
        ans = curcount
        break
    for i in ren[curs-1]:
        if not visited[i-1][0]:
            visited[i-1][0]=True
            for j in ren[i-1]:
                if not visited[j-1][1]:
                    visited[j-1][1]=True
                    for k in ren[j-1]:
                        if not visited[k-1][2]:
                            visited[k-1][2]=True
                            Q.append((k,curcount+1))

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
u,v=[],[]
path=[[] for i in range(n)]
for i in range(m):
    ui,vi=[int(x)-1 for x in input().split()]
    path[ui].append(vi)
    # path[vi].append(ui)
s,t=[int(x)-1 for x in input().split()]
from collections import deque
q=deque()
q.append((s,0))
# print(path)
check=[[False]*n for x in [0,1,2]]
while q:
    # print(q)
    p,num=q.popleft()
    if check[num%3][p]==True:
        continue
    if num%3!=0:
        for i in path[p]:
            q.append((i,num+1))
        check[num%3][p]=True
        continue
    elif p==t:
        print(num//3)
        import sys
        sys.exit()
    else:
        for i in path[p]:
            q.append((i,num+1))
        check[0][p]=True
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10000000)

readline = sys.stdin.readline

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

S, T = S - 1, T - 1

nodes = [{} for i in range(N)]
for u, v in uv:
    nodes[u - 1][v - 1] = 1

visited = [[False] * N for i in range(3)]

def kenken(u, rem):
    if rem != 3 and visited[rem][u]:
        return deque()
    
    if rem != 3:
        visited[rem][u] = True
    if rem > 0:
        a = deque()
        for v in nodes[u]:
            a.extend(kenken(v, rem - 1))
        return a
    else:
        return deque([u])
    

q = deque()

q.append([S, 0])

_count = -1
while len(q) != 0:
    u, count = q.popleft()

    ret = kenken(u, 3)
    if any(T == r for r in ret):
        _count = count + 1
        break
    q.extend([r, count + 1] for r in ret)


print(_count)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


def main():
    node_num, edge_num = map(int, input().split())
    graph_data = defaultdict(set)

    abcde = [list(map(int, input().split())) for i in range(edge_num)]

    for i in range(edge_num):
        a, b = abcde[i]
        graph_data[a].add(b)

    start, goal = map(int, input().split())
    visit_flg = [0] * (node_num + 1)
    visit_flg2 = [0] * (node_num + 1)
    visit_flg3 = [0] * (node_num + 1)
    visit_flg[start] = 1

    now_set = set()
    now_set.add(start)
    next_set = set()

    ans = 0

    while len(now_set) > 0:
        ans += 1

        if visit_flg[goal]:
            break

        for now_node in now_set:
            search_now_set = set()
            search_now_set.add(now_node)
            search_next_set = set()

            for i in range(3):
                for search_now_node in search_now_set:
                    if i == 1 and visit_flg2[search_now_node]:
                        continue
                    elif i == 1:
                        visit_flg2[search_now_node] = 1
                    if i == 2 and visit_flg3[search_now_node]:
                        continue
                    elif i == 2:
                        visit_flg3[search_now_node] = 1
                    search_next_set |= graph_data[search_now_node]
                search_now_set = search_next_set
                search_next_set = set()

            for ele_check in search_now_set:
                if visit_flg[ele_check]:
                    continue
                else:
                    visit_flg[ele_check] = 1
                    next_set.add(ele_check)

                if visit_flg[goal]:
                    break

        if visit_flg[goal]:
            break

        now_set = next_set
        next_set = set()

    if visit_flg[goal]:
        print(ans)
    else:
        print(-1)












if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

G = dict()

for i in range(1, 3 * N + 1):
    G[i] = dict()

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

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

dist_S = [3 * N + 1] * (3 * N + 1)
dist_S[S] = 0

# BFS
queue = deque([S])
while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if dist_S[p] + 1 < dist_S[q]:
            dist_S[q] = dist_S[p] + 1
            queue.append(q)

if dist_S[T] < 3 * N + 1:
    print(dist_S[T] // 3)
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    u,v=map(int,input().split())
    graph[u-1].append(v-1)
s,t=map(int,input().split())
s=s-1
t=t-1
from collections import deque
que=deque([])
que.append(s)
check0=[-1]*n
check1=[-1]*n
check2=[-1]*n
check0[s]=0
while len(que)>0:
    now=que.popleft()
    for i in graph[now]:
        if check1[i]==-1:
            if check0[now]!=-1:
                check1[i]=check0[now]+1
                que.append(i)
        if check2[i]==-1:
            if check1[now]!=-1:
                check2[i]=check1[now]+1
                que.append(i)
        if check0[i]==-1:
            if check2[now]!=-1:
                check0[i]=check2[now]+1
                que.append(i)
if check0[t]==-1:
    print(-1)
else:
    print(check0[t]//3)

Submission status: Accepted

Solution code:
N, M = map(int, input().strip().split())

vs = [[] for _ in range(N + 1)]
for _ in range(M):
	v, u = map(int, input().strip().split())
	vs[v].append(u)
#	vs[u].append(v)
S, T = map(int, input().strip().split())

def search(vs, S, T):
	queue = [(S, 0)]
	dists = [[-1] * (N + 1) for _ in range(3)]
	while queue:
		n, d = queue.pop(0)
		d += 1
		dr = d % 3
		dists_tmp = dists[dr]
		for n2 in vs[n]:
			if dr == 0 and n2 == T:

#				for dd in dists:
#					print(dd)
#				print(n, d, queue)

				return d // 3
			if dists_tmp[n2] < 0:
				dists_tmp[n2] = d
				queue.append((n2, d))
	return -1

print(search(vs, S, T))

Submission status: Accepted

Solution code:
def step():
    onestep_points = set()
    twostep_points = set()
    threestep_points = set()
    for p in current_points:
        if(routes[p] == 0):
            continue
        for s in routes[p]:
            onestep_points.add(s)
    for p in onestep_points:
        if(routes[p] == 0):
            continue
        for s in routes[p]:
            twostep_points.add(s)
    for p in twostep_points:
        if(routes[p] == 0):
            continue
        for s in routes[p]:
            threestep_points.add(s)
    next_stop = set()
    for p in threestep_points:
        if(p not in stopped_points):
            stopped_points.add(p)
            next_stop.add(p)
    return next_stop
  
import collections
routes = collections.Counter()

N, M = list(map(int, input().split()))
for m in range(M):
    routes[m+1] = []

for m in range(M):
    u, v = list(map(int, input().split()))
    routes[u].append(v)

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

loop = 0
current_points = set()
stopped_points = set()
current_points.add(S)

ans = -1
while(True):
    loop += 1
    current_points = step()
    if(T in current_points):
        ans = loop
        break
    if(len(current_points) == 0):
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
m = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v = map(int, input().split())
    m[u].append(v)
S, T = map(int, input().split())

l = [[-1, -1, -1] for _ in range(N + 1)]

q = deque()
q.append((S, 0, 0))
while len(q):
    i, n, mod = q.popleft()
    for j in m[i]:
        if j == T and mod == 2:
            print((n + 1) // 3)
            exit()
        if l[j][(mod + 1) % 3] != -1:
            continue
        l[j][(mod + 1) % 3] = n + 1
        q.append((j, n + 1, (mod + 1) % 3))

print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
    u,v = inpl()
    u -= 1
    v -= 1
    lines[u].add(v+N)
    lines[u+N].add(v+2*N)
    lines[u+2*N].add(v)

S,T = inpl()
S -= 1
T -= 1

def search (s,w_0): #s->t
	global weight
	global q

	for t in list(lines[s]):
		w = w_0 + 1
		if weight[t] > w:
			heapq.heappush(q, [w,t])
			weight[t] = w

# Start, S
weight = [INF]*(N*3)
weight[S] = 0
q = [[0,S]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)

ans = weight[T]

if ans == INF:
    print(-1)
else:
    print(ans//3)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    G[u-1].add(v-1)
#print(G)
S,T=map(int,input().split())
S-=1;T-=1
#dp[i][j]:i番目の頂点をmod 3=jで行けるかどうか
dist=[[10**10 for i in range(3)] for i in range(N)]
dist[S][0]=0
q=[]
heapq.heappush(q,(dist[S][0],S,0))
while(len(q)>0):
    d,r,j=heapq.heappop(q)
    if dist[r][j]<d:
        continue
    for p in G[r]:
        if dist[p][(j+1)%3]>dist[r][j]+1:
            dist[p][(j+1)%3]=dist[r][j]+1
            heapq.heappush(q,(dist[p][(j+1)%3],p,(j+1)%3))
#print(dist)
if dist[T][0]==10**10:
    print(-1)
else:
    print(dist[T][0]//3)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
A, B = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)
S, T = map(int, input().split())

G = [set() for _ in range(N + 1)]
for x, y in zip(A, B):
    G[x].add(y)

INF = 10**10

dp = [[INF for j in range(3)] for i in range(N + 1)]

q = deque()
q.append((S, 0))
dp[S][0] = 0

while q:
    i, k = q.popleft()
    L = (k + 1) % 3
    for x in G[i]:
        if dp[x][L] == INF:
            dp[x][L] = dp[i][k] + (k + 1) // 3
            q.append((x, L))

ans = (
    -1 if dp[T][0] == INF else
    dp[T][0]
)

print(ans)

Submission status: Accepted

Solution code:
# 最大でも3Nしか頂点には回らない
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())

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

dist = [[False]*3 for i in range(n)]
cnt = [[0]*3 for i in range(n)]
s, t = map(int, input().split())
s -= 1
t -= 1
q = deque()
# now, dist(mod3), cnt
q.append((s, 0, 0))
while q:
    now, d, c = q.popleft()
    if dist[now][d] and cnt[now][d] <= c:
        continue
    dist[now][d] = True
    cnt[now][d] = c
    next_d = (d+1)%3
    next_c = c+1
    for to in edges[now]:
        if not dist[to][next_d] or cnt[to][next_d] > c:
            q.append((to, next_d,next_c))
if dist[t][0]:
    print(cnt[t][0]//3)
else:
    print(-1)

Submission status: Accepted

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

X = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    X[x-1].append(y-1)

S, T = map(int, input().split())
S -= 1
T -= 1
Q0 = deque([S])
Q1 = deque([])
Q2 = deque([])
D0 = [999999] * N
D1 = [999999] * N
D2 = [999999] * N

D0[S] = 0
while Q0 or Q1 or Q2:
    while Q0:
        x = Q0.popleft()
        for c in X[x]:
            if D1[c] == 999999:
                D1[c] = D0[x]+1
                Q1.append(c)
    while Q1:
        x = Q1.popleft()
        for c in X[x]:
            if D2[c] == 999999:
                D2[c] = D1[x]+1
                Q2.append(c)
    while Q2:
        x = Q2.popleft()
        for c in X[x]:
            if D0[c] == 999999:
                D0[c] = D2[x]+1
                Q0.append(c)
print(-1 if D0[T] == 999999 else D0[T]//3)

Submission status: Accepted

Solution code:
import sys
from collections import deque


input = sys.stdin.readline
n, m = map(int, input().split())
info = tuple(map(int, input().split()) for i in range(m))
s, t = map(int, input().split())

graph = [[] for i in range(n)]
for i, j in info:
    graph[i-1].append(j-1)

q = deque()
q.append((s - 1, 0))
INF = 10 ** 10
visited = [10 ** 10] * n
visited_1 = [10 ** 10] * n
visited_2 = [10 ** 10] * n
visited[s - 1] = 0
while q:
    pos, times = q.popleft()
    for i in graph[pos]:
        if (times + 1) % 3 == 1 and times + 1 < visited_1[i]:
            visited_1[i] = times + 1
            q.append((i, times + 1))

        elif (times + 1) % 3 == 2 and times + 1 < visited_2[i]:
            visited_2[i] = times + 1
            q.append((i, times + 1))
            
        elif (times + 1) % 3 == 0 and times + 1 < visited[i]:
            visited[i] = times + 1
            q.append((i, times + 1))

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    g[u - 1].append(v - 1)
s, t = map(int, input().split())
s -= 1
t -= 1
done = [[-1] * n for _ in range(3)]
done[2][s] = 0
que = deque([s])
while que:
    d = que.popleft()
    for node1 in g[d]:
        if done[0][node1] != -1:
            continue
        done[0][node1] = 1
        for node2 in g[node1]:
            if done[1][node2] != -1:
                continue
            done[1][node2] = 1
            for node3 in g[node2]:
                if done[2][node3] != -1:
                    continue
                que.append(node3)
                done[2][node3] = done[2][d] + 1
print(done[2][t])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map( int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map( int, input().split())
        u, v = u-1, v-1
        E[u].append(v)
    s, t = map( int, input().split())
    s, t = s-1, t-1
    d = deque([s])
    V = [10**9]*(N*3)
    V[s] = 0
    while d:
        u = d.popleft()
        r, v = u//N,u%N
        c = V[u]
        if r == 0 and v == t:
            print(c//3)
            return
        r = (r+1)%3
        for z in E[v]:
            if c+1 < V[r*N+z]:
                V[r*N+z] = c+1
                d.append(r*N+z)
    print(-1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, UV, S, T):
    G = defaultdict(list)
    for u, v in UV:
        G[u-1].append(v-1)
    
    S -= 1
    T -= 1
    # print(G)
    d = [defaultdict(lambda: sys.maxsize) for _ in range(N)]
    q = deque([(S, 0, 0)])
    while q:
        u, md, cd = q.popleft()
        if md not in d[u]:
            d[u][md] = min(d[u][md], cd)
            nd = (md+1) % 3
            for v in G[u]:
                q.append((v, nd, cd+1))

    if 0 in d[T]:
        return math.ceil(d[T][0] / 3)
    return -1


def main():
    N, M = read_int_n()
    UV = [read_int_n() for _ in range(M)]
    S, T = read_int_n()
    print(slv(N, M, UV, S, T))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    d = defaultdict(int)
    for i in s:
        d[i] += 1
    for i in d.keys():
        if d[i] != 2:
            print("No")
            quit()
    print("Yes")
    return

#B
def B():
    n = I()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        k = p[i-1:i+2]
        k.sort()
        if k[1] == p[i]:
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    d = LI()
    d.sort()
    print(d[n//2]-d[n//2-1])
    return

#D
def D():
    n,k = LI()
    fact = [1]*100001
    for i in range(1,100001):
        fact[i] = fact[i-1]*i%mod
    inv = [1]*100001
    inv[-1] = pow(fact[-1],mod-2,mod)
    for i in range(1,100001)[::-1]:
        inv[i-1] = inv[i]*i%mod

    for i in range(1,k+1):
        if n-k+1 < i:
            print(0)
        else:
            ans = fact[n-k+1]*inv[i]*inv[n-k+1-i]%mod
            ans *= fact[k-1]*inv[k-i]*inv[i-1]%mod
            ans %= mod
            print(ans)
    return

#E
def E():
    ma = 100000000
    def dijkstra(s):
        d = defaultdict(lambda : ma)
        q = [(0,s,0)]
        d[(s,0)] = 0
        while q:
            dx,x,t = heappop(q)
            t = (t+1)%3
            k = t == 1
            for y in v[x]:
                if dx+k < d[(y,t)]:
                    d[(y,t)] = dx+k
                    heappush(q,(d[(y,t)],y,t))
        res = d[(g,0)]
        if res == ma:
            res = -1
        return res

    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
    s,g = LI()
    s -= 1
    g -= 1
    print(dijkstra(s))
    return

#F
def F():
    n = I()

    return


#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

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

n,m = [int(i) for i in input().split()]
g = [[] for _ in range(n)]

uv = [[int(i)-1 for i in input().split()] for _ in range(m)]
for u,v in uv: g[u].append(v)

s,t = [int(i)-1 for i in input().split()]

#print(g)


from collections import deque

#############################################################################
#   初期設定
#############################################################################
#memo: 負なら未確認、0以上なら最短距離
memo = [[-3]*3 for _ in range(n)] # used[i][mod]
q = deque()
#初期状態をキューに入れる-----------------------------------------------------
#キューに入れる時点で使用したかどうかのmemoを更新-----------------------------
q.append((s,0)) #初期状態をキューに入れる
memo[s][0] = 0 #初期状態を訪問済みにする
#############################################################################
#   BFS
#############################################################################
while q: #キューが空になるまで
    (v,d) = q.popleft() #キューから情報を取り出す
    #foreach (x,y)のお隣さん に対して処理-------------------------------------
    for cv in g[v]:
        #(nx,ny)が確認済みならスキップ----------------------------------------
        if memo[cv][(d+1)%3] >= 0: continue
        #(nx,ny)が未確認のとき、確認済みにしてキューに入れる------------------
        memo[cv][(d+1)%3] = d+1
        q.append((cv,d+1))
        #経路復元が必要なとき-------------------------------------------------
        # prev[nx][ny] = [x,y]    
    
#print(memo)
print(memo[t][0]//3)

Submission status: Accepted

Solution code:
import sys
from queue import Queue

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
g = []
for i in range(n):
    g.append([])
for i in range(m):
    u, v = na()
    g[u-1].append(v-1)

s, t = na()
s -= 1;
t -= 1

ds = [[9999999999] * n for i in range(3)]
ds[0][s] = 0

q = Queue()
q.put((0, s))
while not q.empty():
    r, cur = q.get_nowait()
    nr = (r+1) % 3
    for e in g[cur]:
        # print(nr, e)
        if ds[nr][e] > ds[r][cur] + 1:
            ds[nr][e] = ds[r][cur] + 1
            q.put((nr, e))
if ds[0][t] < 99999999:
    print(ds[0][t]//3)
else:
    print(-1)