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 python3
import sys
import heapq
INF = float("inf")


# 無向グラフを仮定する。
class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u]+w:
                dist[v] = dist[u]+w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    g1 = Graph(3*N)
    for from_, to_ in zip(u, v):
        g1.add_edge((from_-1, N+to_-1, 1))
        g1.add_edge((N+from_-1, 2*N+to_-1, 1))
        g1.add_edge((2*N+from_-1, to_-1, 1))

    dist1, prev1 = shortestPath(g1, S-1)
    # print(dist1)
    # print(dist1)
    m = INF
    for i in range(3):
        if dist1[i*N+T-1] % 3 == 0 and m > (dist1[i*N+T-1]//3):
            m = dist1[i*N+T-1]//3
    if m == INF:
        print(-1)
    else:
        print(m)

    return


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
    solve(N, M, u, v, S, T)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
D = [[-1, -1, -1] for i in range(N)]
Q = [[-1, -1, -1] for i in range(M)]
if M:
  Q[0] = [S - 1, 0, RD[S - 1] % 3]
o = 0
i = 1
while Q:
  q, d, m = Q[o]
  Q[o] = [-1, -1, -1]
  o = (o + 1) % M
  if q == -1:
    break
  if RD[q] == -1:
    continue
  D[q][m] = d + RD[q]
  if m != 0:
    for adj in E[q]:
      _m = (d + 1 + RD[adj]) % 3
      if D[adj][_m] == -1:
        Q[i] = [adj, d + 1, _m]
        i = (i + 1) % M
P = [d[0] for d in D if d[0] != -1]
if P:
  print(min(P) // 3)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
n,m=map(int,input().split())
Edges=[[] for _ in range(3*n)]
for _ in range(m):
    u,v=map(lambda x: int(x)-1,input().split())
    Edges[u].append(v+n)
    Edges[u+n].append(v+2*n)
    Edges[u+2*n].append(v)
s,t=map(lambda x: int(x)-1,input().split())
q=deque()
q.append(s)
Dist=[-1]*(3*n)
Dist[s]=0
while q:
    fr=q.popleft()
    for to in Edges[fr]:
        if Dist[to]==-1:
            Dist[to]=Dist[fr]+1
            q.append(to)
print(Dist[t]//3)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import time
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

t = time.time()
N, M = MAP()

uv = [LIST() for _ in range(M)]
S, T = MAP()
S = S-1
T = T-1
graph = defaultdict(list)
flag = False
for u, v in uv:
	if v-1 == T:  # T にたどりつける
		flag = True
	graph[v-1].append(u-1)
if not flag:
	print(-1)
	sys.exit(0)
# print(graph)
q = deque([])
q.append((T, 0, "a"))
sirusi = [[] for _ in range(N)]  # "a":3n "b":3n-1 "c":3n-2
count = 0
while q:
	if count >= 3*N+1:  # すべてに印つけおわる
		break
	search, step, state = q.popleft()
	# print(search, step, state)
	if state in sirusi[search]:
		continue
	sirusi[search].append(state)
	count += 1
	# print(search, step, state)
	if search == S and state == "a":
		break

	for node in graph[search]:
		if state == "a":
			q.append((node, step+1, "b"))
		elif state == "b":
			q.append((node, step+1, "c"))
		else:
			q.append((node, step+1, "a"))
# print(sirusi)
if "a" in sirusi[S]:
	print(step//3)
else:
	print(-1)

Submission status: Accepted

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

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

stack = [s]
stack_new = []
used = [-1 for i in range(3*n)]

time = 0
while len(stack) > 0:
    now = stack.pop()
    if used[now] == -1:
        used[now] = time
        if now == t:
            print(time//3)
            exit()
        stack_new+=f[now]
    if len(stack) == 0:
        stack = stack_new
        stack_new = []
        time += 1

print(-1)

Submission status: Accepted

Solution code:
from heapq import *
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=[[] for i in range(3*N)]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    G[3*u+0].append([3*v+1,0])
    G[3*u+1].append([3*v+2,0])
    G[3*u+2].append([3*v+0,1])
S,T=map(int,input().split())
INF=10**9+7
def dijkstra(G,s):

  d=[INF]*(3*N)
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d
d=dijkstra(G,(S-1)*3)
if d[(T-1)*3]==INF:
  print(-1)
else:
  print(d[(T-1)*3])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
n,m=map(int,input().split())
Edges=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(lambda x: int(x)-1,input().split())
    Edges[u].append(v)
s,t=map(lambda x: int(x)-1,input().split())
q=deque()
q.append((s,0))
Flag=[[False]*n for _ in range(3)]
while q:
    v,dist=q.popleft()
    if Flag[dist%3][v]==True:
        continue
    if dist%3!=0:
        for to in Edges[v]:
            q.append((to,dist+1))
        Flag[dist%3][v]=True
        continue
    elif v==t:
        print(dist//3)
        exit()
    else:
        for to in Edges[v]:
            q.append((to,dist+1))
        Flag[0][v]=True
print(-1)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
edge = [[[] for i in range(N)] for j in range(3)]

for i in range(M):
	u,v = map(int,input().split())
	u -= 1
	v -= 1
	edge[0][u].append(v)
	edge[1][u].append(v)
	edge[2][u].append(v)
S,T = map(int,input().split())
S -= 1
T -= 1
INF = 10**10
dist = [[0 if i == S and j == 0 else INF for i in range(N)] for j in range(3)]
search = []
searched = [[False for i in range(N)] for j in range(3)]
heapq.heapify(search)
heapq.heappush(search, (0, 0, S))
while len(search) > 0 and dist[0][T] == INF:
	x = heapq.heappop(search)
	d, t, node = x[0], x[1], x[2]
	if searched[t][node]:
		continue
	searched[t][node] = True
	dist[t][node] = d
	for i in edge[t][node]:
		if not searched[(t+1)%3][i]:
			heapq.heappush(search, (d+(t+1)//3, (t+1) % 3, i))
if dist[0][T] < INF:
	print(dist[0][T])
else:
	print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    # power_funcを用いて(nCk) mod p を求める 
    # nCk = n!/((n-k)!k!)を使用

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    # a^b mod p を求める
    # bを2進数分解して高速累乗

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

#D
def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge, g):

    dist = defaultdict(lambda: inf)
    dist[(start,0)] = 0
    q = [(dist[(start,0)], start, 0)]
    while q:
        du, u, t = heappop(q)
        for j in edge[u]:
            if t == 2:
                t = -1
            if dist[(j, t + 1)] > du + 1:
                dist[(j, t + 1)] = du + 1
                heappush(q, [dist[(j, t + 1)], j, t + 1])
    return dist
#E
def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = defaultdict(list)
    for x,y in v:
        edge[x].append(y)
    d = dijkstra(n, s, edge, t)
    if d[(t,0)] == inf:
        print(-1)
    else:
        print(d[(t,0)]//3)
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Accepted

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

uv = {}
for i in range(M):
    u, v = map(int, input().split())
    if not u in uv:
        uv[u] = [v]
    else:
        uv[u].append(v)


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

b = [[False] * (10**5+1) for i in range(3)]
us = [S]
b[-1][S] = True
cnt = 0
while us:
    cnt += 1
    for i in range(3):
        tmpus = []
        for u in us:
            if u in uv:
                for v in uv[u]:
                    if b[i][v] is False:
                        b[i][v] = True
                        tmpus.append(v)
        us = tmpus

    if T in us:
        print(cnt)
        break

if not T in us:
    print(-1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[[]for i in range(n+1)]
t=[[0,0,0]for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    s[a].append(b)
c,d=map(int,input().split())
t[c][0]=0
do=0
p=[c]
while t[d][0]==0 and len(p)!=0:
    do+=1
    q=[]
    for i in p:
        for j in s[i]:
            if t[j][do%3]==0:
                t[j][do%3]=do
                q.append(j)
    p=q[:]
print(t[d][0]//3if t[d][0]>0 else -1)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())

graph = [[] for _ in range(N + 1)]
for u, v in edges:
    graph[u].append(v)

INF = 10 ** 9 + 7
dp = [[INF] * (N + 1) for _ in range(3)]
dp[0][S] = 0
q = deque()
q.append((S, 0))

while q:
    v, t = q.popleft()
    u = (t + 1) % 3
    d = dp[t][v]
    if t == 2:
        d += 1
    for w in graph[v]:
        if dp[u][w] != INF:
            continue
        dp[u][w] = d
        q.append((w, u))
        
print(dp[0][T] if dp[0][T] < INF else -1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = [St-1]
i = 0
while queue != []:
    i += 1
    hoge = []
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > i:
                D[s][i%3] = i
                if not s in hoge:
                    hoge.append(s)
    queue = hoge[:]
    if D[T-1][0] != float('inf'):
        break
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)

Submission status: Accepted

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

import sys

v1mask= set()
v2mask= set()

def getVertex(i,e):
    global v1mask, v2mask
    v= set()
    for v1 in e[i]:
        if v1 in v1mask: continue
        v1mask.add( v1 )
        for v2 in e[v1]:
            if v2 in v2mask: continue
            v2mask.add( v2 )
            for v3 in e[v2]: v.add( v3 )
    #
    return v
#
n,m = [ int(x) for x in sys.stdin.readline().split() ]
e = { i:[] for i in range(n) }
for _ in range(m):
    u,v = [ int(x) for x in sys.stdin.readline().split() ]
    e[u-1].append( v-1 )
s,t = [ int(x)-1 for x in sys.stdin.readline().split() ]
#
hop= 0
now = {s}
visit = {s}
while True:
    hop+= 1
    n= set()
    for i in now:
        n |= getVertex(i,e) - visit
        if t in n: break
    #
    if t in n: break
    if not n:
        hop= -1
        break
    now = n
    visit|= n
#
print( hop )

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict


def solve(N: int, M: int, U: "List[int]", V: "List[int]", S: int, T: int):
    S -= 1
    T -= 1
    adj = [[] for i in range(N)]
    for u, v in zip(U, V):
        adj[u-1].append(v-1)
    color = [[0, 0, 0] for i in range(N)]
    color[S][0] = 1
    Q = [(0, S)]

    while len(Q) > 0:
        d, u = heapq.heappop(Q)
        if u == T and d % 3 == 0:
            print(d // 3)
            return
        for v in adj[u]:
            if color[v][(d+1) % 3] == 1:
                continue
            heapq.heappush(Q, (d+1, v))
            color[v][(d+1) % 3] = 1

    print(-1)
    return


# Generated by 1.1.4 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
    solve(N, M, u, v, S, T)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

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

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

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

inf = float('inf')
d = [[inf, inf, inf] for i in range(n)]
d[s][0]=0

q = queue.Queue()
for i in range(len(a[s])):
    q.put(a[s][i])
    d[a[s][i]][1]=1


while not q.empty():
    p = q.get()
    for i in range(len(a[p])):
        r = a[p][i]
        c = []
        if d[r][0]==inf:
            c.append(0)
        if d[r][1]==inf:
            c.append(1)
        if d[r][2]==inf:
            c.append(2)
        if not c:
            continue

        flag = False
        for j in range(len(c)):
            if c[j]==0:
                if d[p][2]!=inf:
                    break
            elif c[j]==1:
                if d[p][0]!=inf:
                    break
            elif c[j]==2:
                if d[p][1]!=inf:
                    break
            if j==len(c)-1:
                flag=True
        if flag:
            continue

        q.put(r)
        for j in range(len(c)):
            if c[j]==0:
                d[r][0] = d[p][2] + 1
            elif c[j]==1:
                d[r][1] = d[p][0] + 1
            elif c[j]==2:
                d[r][2] = d[p][1] + 1

        if r==t and d[r][0]!=inf:
            print(d[r][0]//3)
            exit()
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
E = {u: set() for u in range(1, N+1)}
for i in range(M):
    u, v = map(int, input().split())
    E[u].add(v)
S, T = map(int, input().split())

X = {}
for u in E:
    for i in range(3):
        X[(u, i)] = set([(v, (i + 1) % 3) for v in E[u]])

# bfs
queue = deque()
queue.append(((S, 0), 0))
visited = set()

while len(queue) > 0:
    u, n = queue.popleft()
    if u in visited:
        continue
    visited.add(u)
    if u == (T, 0):
        print(n // 3)
        exit()
    for v in X[u]:
        queue.append((v, n + 1))

print(-1)

Submission status: Accepted

Solution code:
# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
edge = [[] for _ in range(N+1)]
for _ in range(M):
  u,v = map(int,input().split())
  edge[u].append(v)
S,T = map(int,input().split())

INF = 10 ** 9
dist = [[INF,INF,INF] for _ in range(N+1)]

d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in edge[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq

d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)

Submission status: Accepted

Solution code:

import sys
import copy
sys.setrecursionlimit(4100000)

n,m = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for i in range(m)]
t = [int(i) for i in input().split()]
from collections import defaultdict
steps = defaultdict(list)
for a,b in l:
    steps[a].append(b)
seen = set()
counter = 0
queue = [t[0]]
nextqueue = []
ans = False
depth = 0
while queue:
    current = queue.pop(0)
    if counter == 0 and current == t[1]:
        ans = True
        break
    if counter == 3 and current == t[1]:
        ans = True
        break
    for a in steps[current]:
        if (a,counter+1) not in seen:
            seen.add((a,counter+1))
            nextqueue.append(a)
    if queue == []:
        if counter == 3:
            counter = 1
        else:
            counter += 1
        queue = copy.deepcopy(nextqueue)
        nextqueue = []
        depth += 1

if ans is True:
    print(depth//3)
else:
    print(-1)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = [[] for _ in range(N)]
    for _ in range(M):
        u,v = MI_()
        edge[u].append(v)
    S, T = MI_()

    queue = [S]
    checked = set()
    for i in range(1,max(3*N+1,3*M+2)):
        tmp = set()
        while queue:
            s = queue.pop()
            if i % 3 == 0:
                if s in checked:
                    continue
                else:
                    checked.add(s)
            for to in edge[s]:
                if to == T:
                    if i%3==0:
                        print(i//3)
                        exit()
                tmp.add(to)
        queue = tmp
    print(-1)
            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
c=[[0]*(n+1) for i in range(3)]
s,t=map(int,input().split())
c[2][s]=1
q=[s]
def ken(a):
    tl=[]
    for i in q:
        for j in edge[i]:
            if not c[a][j]:
                tl.append(j)
                c[a][j]=1
    return tl
for i in range(n):
    q=ken(0)
    q=ken(1)
    q=ken(2)
    if c[2][t]==1:
        print(i+1)
        break
else:
    print(-1)

Submission status: Accepted

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

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

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

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

cost = [-1 for _ in range(N)]
q = []
heapq.heappush(q, (0, S))

step1memo = set()
step2memo = set()
step3memo = set()

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for u1 in edges[u]:
        if u1 in step1memo:
            continue
        step1memo.add(u1)
        for u2 in edges[u1]:
            if u2 in step2memo:
                continue
            step2memo.add(u2)
            for u3 in edges[u2]:
                heapq.heappush(q, (c+1, u3))

print(cost[T])

Submission status: Accepted

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    UV = ii2nnn(M)
    S, T = i2nn()
    to = [[] for _ in range(N+1)]
    for u, v in UV:
        to[u].append(v)
    bit = [0] * (N+1)
    q = deque()
    q.append((S, 1, 0))
    while q:
        i, b, c = q.popleft()
        if b & bit[i] == b:
            continue
        if i == T and (b & 1) == 1:
            print(c//3)
            return
        bit[i] |= b
        b2 = bit[i] << 1
        if b2 >= 8:
            b2 -= 7
        for j in to[i]:
            q.append((j, b2, c+1))
    print(-1)

main()

Submission status: Accepted

Solution code:
import heapq

n, m = [int(i) for i in input().split()]
U = [[int(i) for i in input().split()] for j in range(m)]
s, t = [int(i) for i in input().split()]

E = [[] for i in range(n + 1)]

for u, v in U:
    E[u].append(v)

visited = [[False] * 3 for i in range(n + 1)]

V = []
heapq.heappush(V, (0, s))

while V:
    c, v = heapq.heappop(V)
    if v == t and c % 3 == 0:
        print(c // 3)
        exit()
    if visited[v][c % 3]:
        continue
    visited[v][c % 3] = True

    for to in E[v]:
        heapq.heappush(V, (c + 1, to))

print(-1)