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:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    # TODO: How should I do when n - r is negative?
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# for test
# sys.stdin = open('sample.txt') 

# ----------------------------------
# main
N, M = R()
UV = [R() for _ in range(M)]
S, T = R()
S -= 1
T -= 1
pos = [[] for _ in range(3*N)]
for u, v in UV:
    u -= 1
    v -= 1
    pos[u].append(v+N)
    pos[u+N].append(v+2*N)
    pos[u+2*N].append(v)
    # pos[v].append(u+N)
    # pos[v+N].append(u+2*N)
    # pos[v+2*N].append(u)

task1 = []
task2 = []
task1.extend(pos[S])
arrived = [False] * (3*N)

counter = 0
while task1:
    counter += 1
    if T in task1:
        break
    for i in task1:
        if arrived[i] == True:
            continue
        arrived[i] = True
        task2.extend(pos[i])
    task1 = task2
    task2 = []
else:
    print(-1)
    exit()
counter //= 3
print(counter)

# end of main
# ----------------------------------

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append / extend
Dic[x].append(y)
# for
for k, v in Dic.items():
"""

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

Submission status: Accepted

Solution code:
#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

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

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

    # print(new_edges)

    dones = set()
    que = deque()
    que.append(((s, 0), 0))
    while que:
        node, step = que.popleft()

        next_nodes = edges[node]
        # print(next_nodes)
        for n, l in next_nodes:
            if n == t and l == 0:
                print((step + 1) // 3)
                exit()

            if (n, l) not in dones:
                que.append(((n, l), step + 1))
                dones.add((n, l))
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
e=[[] for i in range(3*10**5+10)]

[n,m]=i2()
for i in range(m):
 [u,v]=i2()
 u-=1
 v-=1
 e[3*u].append(3*v+1)
 e[3*u+1].append(3*v+2)
 e[3*u+2].append(3*v)
 
[s,t]=i2()
s-=1
t-=1
from collections import deque
d=[-1 for i in range(3*10**5+10)]
def bfs(v):
   d[v]=0
   q=deque([v])
   while len(q):
    v=q.popleft()
    for i in e[v]:
      if d[i]<0:
         d[i]=d[v]+1
         q.append(i)
   if d[3*t]>-1:
     return d[3*t]//3
   return d[3*t]  
print(bfs(3*s))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from heapq import heappush, heappop

def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF ] *n
    visited = [False ] *n

    dist[start] = 0
    que = [(0, start)]

    while que:
        cost, cur = heappop(que)

        if visited[cur]:
            continue

        visited[cur] = True

        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))

    return dist


n, m = li()

graph = [[] for _ in range(3*n)]
for _ in range(m):
    u, v = li_()
    for i in range(3):
        graph[i*n + u].append([(i+1)%3 * n + v, 1])

s, t = li_()
INF = 1<<62
dist = dijkstra(graph, s, INF)

print(-1 if dist[t] == INF else dist[t] // 3)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

def bfs(s):
    q = deque()
    q.append(s)
    d = [-1 for _ in range(3*N)]
    d[s] = 0
    
    while q:
        v = q.popleft()
        if v == T:
            return d[v]
    
        for u in connect[v]:
            if d[u] == -1:
                q.append(u)
                d[u] = d[v]+1
                
    return -1

ans =  bfs(S)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq

N, M = map(int, input().split())
MAX = float("inf")

nodes = [[] for i in range(N+1)]

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

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

# init
d = [
    [MAX for i in range(N)],
    [MAX for i in range(N)],
    [MAX for i in range(N)],
]
d[0][S] = 0
queue = []
heapq.heappush(queue, [0, 0, S])

while queue:
    p, m, n = heapq.heappop(queue)
    if m == 0 and n == T:
        print(int(p/3))
        quit()
    for to in nodes[n]:
        if d[(m+1) % 3][to] > d[m][n] + 1:
            d[(m+1) % 3][to] = d[m][n] + 1
            heapq.heappush(queue, [
                d[(m+1) % 3][to],
                (m+1) % 3,
                to
            ])

print(-1)

Submission status: Accepted

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

u={i:[] for i in range(1,n+1)}

for i in range(m):
    ui,vi=map(int,input().split())
    u[ui].append(vi)

s,t = map(int,input().split())
current=[s]
dist={s:0}
for i in range(n):
    for j in range(3):
        next=set()
        for uj in current:
            for vj in u[uj]:
                next.add(vj)
        current=next
    current=[]
    for vj in next:
        if vj not in dist:
            dist[vj]=i+1
            current.append(vj)
    if len(current)==0:
        break

print(-1 if t not in dist else dist[t])

Submission status: Accepted

Solution code:
def main():
	N, M = map(int, input().split())
	INF = 2*31-1
	to = [[] for _ in range(N)]
	for _ in range(M):
		u, v = map(int, input().split())
		to[u-1].append(v-1)
	dist = [[INF, INF, INF] for _ in range(N)]

	S, T = map(int, input().split())
	queue = []
	for pos in to[S-1]:
		queue.append([pos, 1])
		dist[pos][1] = 1
	while queue:
		pos, l = queue.pop(0)
		next_positions = to[pos]
		for next_pos in next_positions:
			nl = (l+1)%3
			if dist[next_pos][nl] != INF:
				continue
			dist[next_pos][nl] = dist[pos][l]+1
			queue.append([next_pos, nl])
	ans = dist[T-1][0]
	if ans == INF:
		print(-1)
	else:
		print(ans//3)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

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

dist = [-1] * (3*N)
dist[S] = 0
que = deque([S])
while len(que) != 0:
    q = que.popleft()
    cost = dist[q]
    for v in graph[q]:
        if dist[v] == -1:
            dist[v] = cost + 1
            que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Accepted

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

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

dist = [-1] * (3*N)
dist[S] = 0
q = deque([S])
while q:
    v = q.popleft()
    d = dist[v]
    Vs = graph[v]
    for u in Vs:
        if dist[u] == -1:
            q.append(u)
            dist[u] = d + 1
if dist[T] != float("inf") and dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(M)]
inf=10**20
c=[[] for i in range(N*3)]
for i,j in edge:
    c[i-1].append(N+j-1)
    c[N+i-1].append(N+N+j-1)
    c[N+N+i-1].append(j-1)
S,T=map(int,input().split())
from collections import deque
def bfs(c,N,S):
    d=[inf]*N
    d[S]=0
    q=deque([S])
    x=1
    while len(q)>0:
        q2=deque()
        for i in q:
            for j in c[i]:
                if d[j]>x:
                    d[j]=x
                    q2.append(j)
        q=q2
        x+=1
    return d
d=bfs(c,N*3,S-1)
print(d[T-1]//3 if d[T-1]<inf else -1)

Submission status: Accepted

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = 3 * 10 ** 5 + 10
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


N, M = map(int, input().split())
from collections import defaultdict

graph = defaultdict(dict)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u][v + N] = 1
    graph[u + N][v + 2 * N] = 1
    graph[u + 2 * N][v] = 1
S, T = map(int, input().split())
S -= 1
T -= 1
dj = Dijkstra(graph, S)

dist, _ = dj.execute()
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Accepted

Solution code:
def e_hopscotch_addict(N, M, Edges, S, T, INF=float('inf')):
    from collections import deque

    graph = [[] for _ in range(N)]
    for u, v in Edges:
        graph[u - 1].append(v - 1)
    start, target = S - 1, T - 1

    # editorialに従って G' を構成
    graph_prime = [[INF] * N for _ in range(3)]
    graph_prime[0][start] = 0  # S_0を起点とする
    queue = deque([(start, 0)])  # S_0を最初にデックに入れる
    while queue:
        vertex, t = queue.popleft()
        u = (t + 1) % 3
        for to in graph[vertex]:
            if graph_prime[u][to] != INF:
                continue  # もう探索済み
            queue.append((to, u))
            graph_prime[u][to] = graph_prime[t][vertex] + 1
    return graph_prime[0][target] // 3 if graph_prime[0][target] != INF else -1

N, M = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
S, T = [int(i) for i in input().split()]
print(e_hopscotch_addict(N, M, Edges, S, T))

Submission status: Accepted

Solution code:
#import queue
from collections import deque
INF=-1

N,M=[int(e) for e in input().split(' ')]

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

for i in range(M):
    u,v=[int(e) for e in input().split(' ')]
    to[u-1].append(v-1)
S,T=[int(e)-1 for e in input().split(' ')]

dist=[[INF for i in range(3)] for j in range(N)]

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

dist[S][0]=0

while(q):
    v,l=q.popleft()
    for v_to in to[v]:
        nl=(l+1)%3
        if dist[v_to][nl] != INF:
            continue
        dist[v_to][nl]=dist[v][l]+1
        q.append([v_to,nl])
ans=dist[T][0]
if ans == INF:
    ans = -1
else:
    ans=ans//3

print(ans)

Submission status: Accepted

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

lst = [[] for i in range(3*n+1)]
dist = [-1 for i in range(3*n+1)]
for i in range(m):
    u, v = map(int, input().split())
    lst[u].append(v+n)
    lst[u+n].append(v+2*n)
    lst[u+2*n].append(v)

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

next = lst[s]
next_next = []
not_empty = True
cost = 1
while not_empty:
    not_empty = False
    for i in next:
        if dist[i] == -1:
            dist[i] = cost
            next_next.extend(lst[i])
            not_empty = True
    next = next_next.copy()
    next_next = []
    cost += 1

if dist[t] % 3 == 0:
    print(dist[t]//3)
else:
    print(-1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    aa = [LI() for _ in range(m)]
    s,t = LI()
    e = collections.defaultdict(set)
    for a,b in aa:
        e[a].add(b)

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[(s,0)] = 0
        q = []
        heapq.heappush(q, (0, (s,0)))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True
            uk = (k+1)
            kk = (k+1) % 3

            for uu in e[u[0]]:
                uv = (uu, kk)
                if v[uv]:
                    continue
                if d[uv] > uk:
                    d[uv] = uk
                    heapq.heappush(q, (uk, uv))

        return d

    d = search(s)
    r = d[(t,0)]
    if r == inf:
        return -1

    return r // 3


print(main())

Submission status: Accepted

Solution code:
from collections import deque

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

    # 状態を3倍化して保存
    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)


def bfs():
    cnt = 0
    q = deque()
    visited = [False for _ in range(3 * N)]
    q.append(S)
    visited[S] = True
    while len(q) > 0:
        new_q = deque()
        cnt += 1
        while(len(q) > 0):
            u = q.pop()
            for v in G[u]:
                if visited[v]:
                    continue
                if v == T:
                    return cnt // 3

                visited[v] = True
                new_q.append(v)
        q = new_q
    return -1


print(bfs())

Submission status: Accepted

Solution code:
from collections import deque

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

distance = [10**9 for _ in range(3*N)]
distance[S] = 0

queue = deque([S])
while queue:
    u = queue.popleft()
    for next in edge[u]:
        if distance[u]+1 < distance[next]:
            distance[next] = distance[u]+1
            queue.append(next)
if distance[T] < 10**9:
    print(distance[T]//3)
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bfs(N: int, nodes: list, src: int) -> list:
    """ 幅優先探索(頂点数, 隣接リスト(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [[INF] * N for i in range(3)]
    # スタート位置
    que = deque([(0, src)])
    res[0][src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # 現在のノード
        k, cur = que.popleft()
        # 出発ノードcurの到着ノードでループ
        for nxtk, nxt in nodes[k][cur]:
            # 今回の経路のが短い時
            if res[k][cur] + 1 < res[nxtk][nxt]:
                res[nxtk][nxt] = res[k][cur] + 1
                # 後ろに詰めて、近い方から処理するようにする
                que.append((nxtk, nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1

# 元の頂点を3層に拡張する
nodes2=[[[] for j in range(N)] for i in range(3)]
for i in range(3):
    for u, node in enumerate(nodes):
        for v in node:
            nodes2[i][u].append(((i+1)%3, v))

res=bfs(N, nodes2, S)
if res[0][T]==INF:
    print(-1)
else:
    # けんけんぱの回数なので/3する
    print(res[0][T]//3)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bfs(N: int, nodes: list, src: int) -> list:
    """ 幅優先探索(頂点数, 隣接リスト(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [[INF] * N for i in range(3)]
    # スタート位置
    que = deque([(0, 0, src)])
    res[0][src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # 現在のノード
        _, k, cur = que.popleft()
        # 出発ノードcurの到着ノードでループ
        for nxtk, nxt in nodes[k][cur]:
            # 今回の経路のが短い時
            if res[k][cur] + 1 < res[nxtk][nxt]:
                res[nxtk][nxt] = res[k][cur] + 1
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                que.append((res[nxtk][nxt], nxtk, nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1

# 元の頂点を3層に拡張する
nodes2=[[[] for j in range(N)] for i in range(3)]
for i in range(3):
    for u, node in enumerate(nodes):
        for v in node:
            nodes2[i][u].append(((i+1)%3, v))

res=bfs(N, nodes2, S)
if res[0][T]==INF:
    print(-1)
else:
    # けんけんぱの回数なので/3する
    print(res[0][T]//3)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from heapq import heappop, heappush

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [[INF] * N for i in range(3)]
    # スタート位置
    que = [(0, 0, src)]
    res[0][src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # 現在のノード
        _, k, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxtk, nxt in nodes[k][cur]:
            # 今回の経路のが短い時
            if res[k][cur] + 1 < res[nxtk][nxt]:
                res[nxtk][nxt] = res[k][cur] + 1
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (res[nxtk][nxt], nxtk, nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1

# 元の頂点を3層に拡張する
nodes2=[[[] for j in range(N)] for i in range(3)]
for i in range(3):
    for u, node in enumerate(nodes):
        for v in node:
            nodes2[i][u].append(((i+1)%3, v))

res=dijkstra(N, nodes2, S)
if res[0][T]==INF:
    print(-1)
else:
    # けんけんぱの回数なので/3する
    print(res[0][T]//3)

Submission status: Accepted

Solution code:
from heapq import *
f_inf = float('inf')

def dijkstra(start,node,edge):
    #始点sから各頂点への最短距離
    #node:頂点数
    #d:各頂点へのコスト(存在しないときはinf)
    #q:キュー(スタートからのコスト,頂点)
    d = [[f_inf, f_inf, f_inf] for _ in [0]*node]
    d[start][0] = 0
    #スタートをキューに入れる
    q = [(0,start)]

    while(len(q) != 0):
    #キューの先頭を取得
      ci,i = heappop(q)
    #キューの先頭から繋がっている頂点を探索
      for j in edge[i]:
        nc = ci + 1
        if (d[j][nc%3] > nc):
          d[j][nc%3] = nc
          heappush(q,(nc, j))
    return d
#入力
N,M = (int(x) for x in input().split())
#エッジ
E = [[] for _ in [0]*N]

for i in range(M):
  a,b = (int(x) for x in input().split())
  E[a-1].append(b-1)

S,T = (int(x)-1 for x in input().split())
d = dijkstra(S, N, E)
ans = d[T][0]

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