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:
# -*- coding: utf-8 -*-
import sys
from collections import deque

n, m = map(int, input().split())
g = [[] for _ in range(3 * n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    # u0 -> v1
    g[3 * u].append(3 * v + 1)
    # u1 -> v2
    g[3 * u + 1].append(3 * v + 2)
    # u2 -> v0
    g[3 * u + 2].append(3 * v)

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

depth = dict()
depth[s] = 0
q = deque([s])


while(len(q) != 0):
    v = q.popleft()
    for u in g[v]:
        if u not in depth:
            q.append(u)
            depth[u] = depth[v] + 1

print(depth[t] // 3 if t in depth else -1)

Submission status: Accepted

Solution code:
from collections import deque

def BFS(path, start, goal):
  que = deque()
  for uv in path[start]:
    que.append(uv)
  visited=[-1 for i in range(3*N)]
  visited[start] = 0
  i = 0
  while que:
    uv = que.popleft()
    
    if visited[uv[1]] == -1:#未到達
      visited[uv[1]] = visited[uv[0]] + 1
      for vw in path[uv[1]]:
        que.append(vw)
    if i >3*N:break
  return visited[goal]

N,M = map(int,input().split())
edge = [[] for i in range(3*N)]
for i in range(M):
  u,v = map(int,input().split())
  edge[0*N + u - 1] += [[0*N + u - 1,1*N + v - 1]]
  edge[1*N + u - 1] += [[1*N + u - 1,2*N + v - 1]]
  edge[2*N + u - 1] += [[2*N + u - 1,0*N + v - 1]]
  
S, T = map(int,input().split())
print(BFS(edge, S-1, T-1)//3)

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))
# print('hoge', file=sys.stderr)

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

# E = {set() for _ in range(N + 1)}
E = defaultdict(lambda: set())

for i in range(M):
    u, v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    E[3 * u].add(3 * v + 1)
    E[3 * u + 1].add(3 * v + 2)
    E[3 * u + 2].add(3 * v)

S, T = [int(x) for x in input().split()]
S = 3 * (S - 1)
T = 3 * (T - 1)


def bfs(e, start, end):
    open = deque([start])
    w = dict()
    w[start] = 0
    while len(open) != 0:
        target = open.popleft()
        for next in E[target]:
            if not next in w:
                open.append(next)
                w[next] = w[target] + 1

    return w[end] // 3 if end in w else -1


print(bfs(E, S, T))

Submission status: Accepted

Solution code:
import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())

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

for i in range(M):
	u,v=map(int, sys.stdin.readline().split())
	nl[u].append(v)

S,T=map(int, sys.stdin.readline().split())

V=[ [ None for j in range(3) ] for i in range(N+1) ]
V[S][0]=0


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

while q:
	x=q.popleft()
	fro=x[0]
	cur_mod=x[1]

	for to in nl[fro]:
		next_mod=(cur_mod+1)%3
		if V[to][next_mod] is None:
			V[to][next_mod]=V[fro][cur_mod]+1
			if V[T][0] is not None:
				break
			q.append( ( to, next_mod ) )


if V[T][0] is None:
	print -1
else:
	print V[T][0]/3

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

from collections import deque

# q = queue.Queue()
q = deque()
q.append((S,0))
# Deep First Serch
while q:
    now, cost = q.popleft()
    state = cost % 3
    if used[now][state] == mod:
        used[now][state] = cost
        for route in routes[now]:
            q.append((route,cost+1))

# print(used)
try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

from collections import deque

# q = queue.Queue()
q = deque()
q.append((S,0))
# Deep First Serch
while q:
    now, cost = q.popleft()
    for route in routes[now]:
        n_state = (cost + 1) % 3
        if used[route][n_state] == mod:
            used[route][n_state] = cost + 1
            q.append((route,cost+1))


# print(used)
try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
INF = 1001001001
dist = [[INF for _ in range(3)] for _ in range(N)]

# 有向グラフG
G = [[] for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)

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

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

while q:
    k, l = q.popleft()
    for i in G[k]:
        nl = (l + 1) % 3
        if dist[i][nl] == INF:
            dist[i][nl] = dist[k][l] + 1
            q.append((i, nl))

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

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
INF = 1001001001
dist = [[INF for _ in range(3)] for _ in range(N)]

# 有向グラフG
G = [[] for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)

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

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

while q:
    v, l = q.popleft()
    for u in G[v]:
        nl = (l + 1) % 3
        if dist[u][nl] == INF:
            dist[u][nl] = dist[v][l] + 1
            q.append((u, nl))

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict,deque


class Graph:

  def __init__(self,N,uv,S,T):
    self.graph = uv
    self.start = S
    self.goal = T
    self.states  = [[-3 for _ in range(3)] for _ in range(N)]
    self.states[self.start][0] = 0

  def solve(self):
    nxt = deque([self.start])
    ## update
    while len(nxt) > 0:
      p = nxt.popleft()
      for q in self.graph[p]:
        for ps in range(3):
          if self.states[p][ps] >= 0:
            qs = (ps+1)%3
            if self.states[q][qs] < 0:
              self.states[q][qs] = self.states[p][ps]+1
              nxt.append(q)
            else:
              self.states[q][qs] = min(self.states[q][qs],self.states[p][ps]+1)
    ## return
    return self.states[self.goal][0]


def main():
  ## input
  N,M = map(int, input().split())
  uv = defaultdict(set)
  for _ in range(M):
    u,v = map(int, input().split())
    uv[u-1].add(v-1)
  S,T = map(int, input().split())

  ## solve
  graph = Graph(N,uv,S-1,T-1)
  print(graph.solve()//3)


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, m = LI()
    g = [[] for i in range(3*(n+1))]
    for i in range(m):
        u, v = LI()
        g[u].append(v + n + 1)
        g[u + n + 1].append(v + 2*(n + 1))
        g[u + 2*(n + 1)].append(v)

    s, t = LI()

    Q = deque([s])
    searched = [0 for i in range(3*(n+1))]
    searched[s] = 1
    depth = [0 for i in range(3*(n+1))]
    while len(Q) != 0:
        v = Q.popleft()
        for i in g[v]:
            if i == t:
                depth[i] = depth[v] + 1
                print(depth[i]//3)
                return
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq


def main():
    N, M = map(int, input().split())
    E_in = [list(map(int, input().split())) for _ in range(M)]
    S, T = map(int, input().split())

    N2 = N * 2
    # 1-indexed
    V = [0] + [i for i in range(3*N+1)]
    E = defaultdict(dict)
    for e in E_in:
        u = e[0]
        v = e[1]
        E[u][v+N] = 1
        E[u+N][v+N2] = 1
        E[u+N2][v] = 1
    
    INF = 10 ** 18

    def calc_distance(V, E, S):
        d = [INF] * len(V)
        d[S] = 0
        h = []
        heapq.heappush(h, (0, S))
        while h:
            du, u = heapq.heappop(h)
            for v, x in E[u].items():
                if du + x < d[v]:
                    d[v] = du + x
                    heapq.heappush(h, (d[v], v))
        return d
    

    d = calc_distance(V, E, S)
    if d[T] == INF:
        print(-1)
    else:
        print(d[T] // 3)


main()

Submission status: Accepted

Solution code:
import os
import os
import sys
from collections import deque

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
VU = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

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

que = deque()
que.append((S, 0))
reached = np.zeros((N + 1, 3), dtype=bool)
reached[S, 0] = True
ans = -1
while que:
    v, d = que.popleft()
    if v == T and d % 3 == 0:
        ans = int(d // 3)
    for u in graph[v]:
        if not reached[u, (d + 1) % 3]:
            reached[u, (d + 1) % 3] = True
            que.append((u, d + 1))
print(ans)

Submission status: Accepted

Solution code:
import heapq


def dijkstra(n: int, s: int, g: int, Graph) -> int:
    INF = float('inf')
    dis = [[INF, INF, INF] for _ in range(n)]
    dis[s][0] = 0
    hq = []
    heapq.heappush(hq, (0, s, 0))

    while hq:
        c, n, idx = heapq.heappop(hq)
        for i in Graph[n][idx]:
            to, idx, weight = i
            if dis[to][idx] > c + weight:
                dis[to][idx] = c + weight
                if to == g and idx == 0:
                    return dis[to][idx]//3
                heapq.heappush(hq, (dis[to][idx], to, idx))
    return -1


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

graph = [[[], [], []] for _ in range(N)]
for _ in range(M):
    frm, to = map(int, input().split())
    graph[frm-1][0].append((to-1, 1, 1))
    graph[frm-1][1].append((to-1, 2, 1))
    graph[frm-1][2].append((to-1, 0, 1))

S, T = map(int, input().split())
dis = dijkstra(N, S-1, T-1, graph)
print(dis)

Submission status: Accepted

Solution code:
import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
VU = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

#: :type: list of (list of int)
graph = [[] for _ in range(N * 3 + 1)]
for v, u in VU:
    graph[v].append(u + N)
    graph[v + N].append(u + N * 2)
    graph[v + N * 2].append(u)

heap = [(0, S)]
dist = [INF] * (N * 3 + 1)
ans = -1
while heap:
    d, v = heapq.heappop(heap)
    if v == T and d % 3 == 0:
        ans = int(d // 3)
        break
    for u in graph[v]:
        if d + 1 < dist[u]:
            dist[u] = d + 1
            heapq.heappush(heap, (d + 1, u))
print(ans)

Submission status: Accepted

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

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


G3 = [[] for i in range(3 * N)]
for u, v in Edge:
    u, v = u - 1, v - 1
    G3[u].append([v + N, 1])
    G3[u + N].append([v + N * 2, 1])
    G3[u + 2 * N].append([v, 1])


def dijkstra(x):
    d = [float('inf')] * (3 * N)
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G3[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u] + cost, node))
    return d


dist = dijkstra(S)
print(dist[T] // 3 if dist[T] != float('inf') else - 1)

Submission status: Accepted

Solution code:
import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

U = []
V = []
for u, v in UV:
    U.extend([u, u + N, u + N * 2])
    V.extend([v + N, v + N * 2, v])

# graph = csr_matrix(([1] * (M * 3), (U, V)), shape=(N * 3 + 1, N * 3 + 1))
# dist = dijkstra(graph, indices=S)[T]
# if dist < np.inf:
#     print(int(dist // 3))
# else:
#     print(-1)

#: :type: list of (list of int)
graph = [[] for _ in range(N * 3 + 1)]
for u, v in zip(U, V):
    graph[u].append(v)

# S から T までの距離
heap = [(0, S)]
dist = [IINF] * (N * 3 + 1)
while heap:
    d, v = heapq.heappop(heap)
    if v == T:
        print(int(d // 3))
        exit()
    for u in graph[v]:
        if d + 1 < dist[u]:
            dist[u] = d + 1
            heapq.heappush(heap, (d + 1, u))
print(-1)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

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

que = deque()
que.append((S, 0))
reached = np.zeros((N + 1, 3), dtype=bool)
reached[S, 0] = True

while que:
    u, step = que.popleft()
    for v in graph[u]:
        s = step + 1
        if not reached[v, s % 3]:
            reached[v, s % 3] = True
            que.append((v, s))
        if v == T and s % 3 == 0:
            print(s // 3)
            exit()
print(-1)

Submission status: Accepted

Solution code:
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

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

                    if visited[n1]:
                        continue

                    visited[n1] = True

                next_.add(n1)

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

    return -1


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

Submission status: Accepted

Solution code:
import sys, collections

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    son = [[] for i in range(N)] 
    for i in range(M):
        u, v = map(int, input().split())
        son[u-1].append(v-1)
    S, T = map(int, input().split())

    dist = [[-1, -1, -1] for i in range(N)]
    que = collections.deque()
    que.append((0, S-1, 0)) #k回目の移動, 場所, mod
    while que:
        cost, now, mod = que.popleft()
        if dist[now][mod] == -1:
            dist[now][mod] = cost
            if mod == 0:
                for s in son[now]:
                    if dist[s][1] == -1: que.append((cost + 1, s, 1))
            else:
                for s in son[now]:
                    if dist[s][(mod + 1) % 3] == -1: que.append((cost, s, (mod + 1) % 3))

    print(dist[T-1][0])  
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA, self), BridgeEdge(nodeB, self)]
        nodeA.addEdge(self.edges[1])
        #nodeB.addEdge(self.edges[0])

class BridgeEdge:
    def __init__(self, node, edge):
        self.edge = edge
        self.node = node
        self.flag = 0

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)
    def __repr__(self):
        return "({})".format(self.id)

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

for ui, vi in (map(int, input().split()) for _ in range(M)):
    Bridge(nodes[ui], nodes[vi])

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

#nodes[S].flag = 1
s = [(None, nodes[S], 0)]
idx = 0
isOK = False
while idx < len(s):
    pre, cur, level = s[idx]
    idx += 1
    nxtlevel = level + 1
    nxtflag = 1 << (nxtlevel % 3)

    for nxt in cur.bridges:
        if (nxt.flag & nxtflag) == 0:
            nxt.flag |= nxtflag 
            if nxt.node is nodes[T] and nxtflag == 1:
                isOK = True
                break
            s.append((cur, nxt.node, nxtlevel))
    else:
        continue
    break
if isOK:
    print(nxtlevel//3)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import collections


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    graph = collections.defaultdict(set)
    for _ in range(m):
        u, v = [int(s) for s in sys.stdin.readline().strip().split()]
        graph[u].add(v)
    s, t = [int(s) for s in sys.stdin.readline().strip().split()]

    shortest = dict()
    shortest[s] = 0
    q = collections.deque()
    q.append((0, s, 0))
    seen = dict()
    while q:
        level, loc, turn = q.popleft()
        children = graph[loc]
        child_turn = turn + 1
        child_level = (level+1) % 3
        for child in children:
            if (child_level, child) not in seen:
                if child_level == 0 and child == t:
                    print(child_turn // 3)
                    return
                seen[(child_level, child)] = child_turn
                q.append((child_level, child, child_turn))

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
def main():
    INF = float("inf")
    input = sys.stdin.readline
    N, M = map(int,input().split())
    G = [[] for k in range(N)]
    for k in range(M):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        G[u] += [v]
    S, T = map(int,input().split())
    S -= 1
    T -= 1
    D = [[INF,INF,INF] for k in range(N)]
    D[S][0] = 0
    Q = deque([[S,0]])
    while len(Q) > 0:
        t = Q.popleft()
        ima = t[0]
        k = t[1]
        for tsugi in G[ima]:
            if D[tsugi][(k+1)%3] != INF:
                pass
            else:
                D[tsugi][(k+1)%3] = D[ima][k] + 1
                Q.append([tsugi,(k+1)%3])
    if D[T][0] == INF or D[T][0]%3 != 0:
        print(-1)
    else:
        print(D[T][0]//3)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
MAX= 10**5+5
INF= 10**9
def resolve():
    n,m = map(int,input().split())
    net = [[] for i in range(MAX)]
    vn = [[INF]*3 for i in range(n+1)]
    for i in range(m):
        u,v = map(int,input().split())
        net[u].append(v)
    s,t = map(int,input().split())
    vn[s][0]=0
    q = deque()
    q.appendleft((s,0))
    while q:
        data = q.pop()
        v = data[0]
        l = data[1]
        nl=(l+1)%3
        for u in net[v]:
            if vn[u][nl]==INF:
                vn[u][nl] = vn[v][l]+1
                q.appendleft((u,nl))
    ans = vn[t][0]
    if( ans==INF):
        print(-1)
    else:
        print(ans//3)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N, M = [int(c) for c in input().split()]
path = [[] for _ in range(N)]
for i in range(M):
    u, v = [int(c) for c in input().split()]
    path[u-1].append(v-1)

S, T = [int(c)-1 for c in input().split()]

reach = [[-1 for _ in range(N)] for _ in range(3)]
reach[0][S] = 0

queue={S}

time = 1
for _ in range(4*N):
    queue_new = set()
    for q in queue:
        for v in path[q]:
            if reach[time%3][v]==-1:
                reach[time%3][v]=time
                queue_new.add(v)
		
    queue = queue_new
    time += 1

if reach[0][T]==-1:
    print(-1)
else:
    print(reach[0][T]//3)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

visited = [[False] * N for _ in range(3)]
visited[0][S] = True
queue = deque([(S, 0)])

while queue :
    q, cost = queue.popleft()
    p = (cost + 1) % 3
    for i in vec[q] :
        if p == 0 and i == T :
            print((cost + 1) // 3)
            exit()
        if not visited[p][i] :
            visited[p][i] = True
            queue.append((i, cost + 1))

print(-1)

Submission status: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n*3) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v+n)
    dst[u+n].append(v+n*2)
    dst[u+n*2].append(v)
s,t = inm()
s -= 1
t -= 1
ddprint(dst)

dist = [-1] * (n*3)
dist[s] = 0
q = deque([s])
while len(q)>0:
    v = q.popleft()
    #ddprint('v='+str(v))
    for nxt in dst[v]:
        #ddprint('nxt='+str(nxt))
        if nxt==t:
            print((dist[v]+1)//3)
            exit()
        if dist[nxt] > -1:
            continue
        dist[nxt] = dist[v]+1
        q.append(nxt)
    #ddprint(dist)
    #ddprint(q)
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
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 = deque([St-1,-1])
i = 1
while 1:
    q = queue.popleft()
    if q == -1:
        queue.append(-1)
        i += 1
        if queue == deque([-1]):
            break
    else:
        for j in S[q]:
            if D[j][i%3] > i:
                D[j][i%3] = i
                queue.append(j)
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)

Submission status: Accepted

Solution code:
import sys
import queue

input = sys.stdin.readline

N, M = map(int,input().split())
vy = [list(map(lambda x:int(x)-1,input().split())) for i in range(M)]
s, t = map(lambda x:int(x)-1,input().split())

nlist = [[[] for j in range(3)] for i in range(N)]
for v, y in vy:
    nlist[v][0].append([y,1])
    nlist[v][1].append([y,2])
    nlist[v][2].append([y,0])

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

def bfs(visit):
    Q = queue.Queue()
    visit[s][0] = True
    Q.put([[s,0],0])
    while not Q.empty():
        node = Q.get()
        if node[0][0] == t and node[0][1] == 0:
            return node[1]
        for i in nlist[node[0][0]][node[0][1]]:
            if not visit[i[0]][i[1]]:
                visit[i[0]][i[1]] = True
                Q.put([[i[0],i[1]],node[1]+1])
    return -1

ans = bfs(visit)
if visit[t][0]:
    print(ans//3)
else:
    print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
d = {i+1 : [] for i  in range(n)}
for _ in range(m):
    u, v = map(int, input().split())
    d[u].append(v)

visited1 = [False for i in range(n+1)]
visited2 = [False for i in range(n+1)]
visited3 = [False for i in range(n+1)]

s, t = map(int, input().split())
q = set([s])
c = 1
def solve():
    global visited1, visited2,visited3,  c, q
    while True:
        q2 = list(q)
        q = set([])
        for v in q2:
            for e1 in d[v]:
                if visited1[e1]:
                    continue
                visited1[e1] = True
                for e2 in d[e1]:
                    if visited2[e2]:
                        continue
                    visited2[e2] = True
                    for e3 in d[e2]:
                        if visited3[e3]:
                            continue
                        visited3[e3] = True
                        if e3 == t:
                            return c
                        else:
                            q.add(e3)
        if not len(q):
            return -1
        c += 1
print(solve())

Submission status: Accepted

Solution code:
import heapq, sys
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v in self.list[u]:
				if self.dist[v] > u_dist + 1:
					self.dist[v] = u_dist + 1
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
adj = [[] for _ in range(3*n)]
for _ in range(m):
	u, v = map(int, input().split())
	adj[u-1].append(v-1+n)
	adj[u-1+n].append(v-1+2*n)
	adj[u-1+2*n].append(v-1)
s, t = map(int, input().split())
s, t = s-1, t-1

d = DijkstraList(adj, s)
d.solve()
ans = d.distance(t)
print(ans//3 if ans != 10**30 else -1)

Submission status: Accepted

Solution code:
from collections import deque
# 木構造を作る
N,M = map(int, input().split())

G = [[] for i in range(3*N)]
for i in range(M):
    # グラフに頂点を追加(距離があるときは,u,vの後に入れる)
    u,v = map(int,input().split())
    G[3*(u-1)].append((3*(v-1)+1))
    G[3*(u-1)+1].append((3*(v-1)+2))
    G[3*(u-1)+2].append((3*(v-1)))

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

# 木をBFSをする
dist = [-1] * (3*N)
dist[3*(S-1)] = 0
q = deque([3*(S-1)])
while q:
    v = q.popleft()
    d = dist[v]
    Vs = G[v]
    for u in Vs:
        if dist[u] == -1:
            q.append(u)
            dist[u] = d + 1

ans = dist[3*(T-1)]
print(-1 if ans == -1 else ans//3)