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
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
uv = LIR(M)
S, T = LI()
S, T = S-1, T-1

utov = [[] for i in range(N)]

for u, v in uv:
    utov[u-1].append(v-1)


ken1 = deque()
ken2 = deque()
pa = deque()

ken1_used = [False]*N
ken2_used = [False]*N
pa_used = [False]*N

pa.append(S)
pa_used[S] = True

ans = -1

while ken1 or ken2 or pa:
    ans += 1

    while ken1:
        u = ken1.popleft()
        for v in utov[u]:
            if (not ken2_used[v]):
                ken2_used[v] = True
                ken2.append(v)

    while ken2:
        u = ken2.popleft()
        for v in utov[u]:
            if (not pa_used[v]):
                if (v==T):
                    print(ans)
                    quit()
                pa_used[v] = True
                pa.append(v)    

    while pa:
        u = pa.popleft()
        for v in utov[u]:
            if (not ken1_used[v]):
                ken1_used[v] = True
                ken1.append(v)

print(-1)




"""
kenken = []

def bfs(s):
    ret = []
    bfs_map = [-1]*N
    q = deque()
    q.append(s)
    bfs_map[s] = 0
    while q:
        u = q.popleft()
        for v in utov[u]:
            if (edge[u][v] > 0) and (bfs_map[u] > bfs_map[v]):
                bfs_map[v] = bfs_map[u] + 1
                if (bfs_map[v] == 3):
                    ret.append(v)
                else:
                    q.append(v)
    return ret

for i in range(N):
    ret = bfs(i)
    kenken.append(ret)

kenkenedge = [[0]*N for i in range(N)]
for u, vs in enumerate(kenken):
    for v in vs:
        kenkenedge[u][v] = 1

def bfs_dist(S, T):
    bfs_map = [-1]*N
    q = deque()
    q.append(S)
    bfs_map[S] = 0
    while q:
        u = q.popleft()
        for v in kenken[u]:
            if (kenkenedge[u][v] > 0) and (bfs_map[u] > bfs_map[v]):
                bfs_map[v] = bfs_map[u] + 1
                if (v==T):
                    return bfs_map[T]
                else:
                    q.append(v)
    return -1

print(bfs_dist(S, T))
"""

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.prev = [-1 for _ in range(self.size)]
		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
					self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

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

	def path(self, goal):
		self.path = [goal]
		while self.path[-1] != self.start:
			self.path.append(self.prev[self.path[-1]])
		return self.path[::-1]

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:
N, M = [int(i) for i in input().split()]
E = [[] for _ in range(3 * N)]
for _ in range(M):
    u, v = [int(i) - 1 for i in input().split()]
    E[3 * u].append(3 * v + 1)
    E[3 * u + 1].append(3 * v + 2)
    E[3 * u + 2].append(3 * v)
S, T = [3 * (int(i) - 1) for i in input().split()]

from collections import deque
Q = deque()
Q.append((S, 0))

visited = [False] * (3 * N)
visited[S] = True

ans = -1
while Q:
    a, d = Q.popleft()
    if a == T:
        ans = d
        break
    for b in E[a]:
        if not visited[b]:
            Q.append((b, d + 1))
            visited[b] = True

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

Submission status: Accepted

Solution code:
import copy
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s,t=map(int,input().split())

connection=[[] for i in range(3*n)]
for i in range(m):
  connection[l[i][0]-1].append(l[i][1]-1+n)
  connection[l[i][0]-1+n].append(l[i][1]-1+2*n)
  connection[l[i][0]-1+2*n].append(l[i][1]-1)
distance=[-1 for i in range(3*n)]
distance[s-1]=0
L=[s-1]
L2=[]
L3=[]
ct=1
while len(L2)!=3*n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      if distance[connection[L[j]][k]]==-1:
        distance[connection[L[j]][k]]=ct
        L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
  ct+=1
if distance[t-1]==-1:
  print(-1)
else:
  x=distance[t-1]-distance[s-1]
  if x%3==0:
    print(x//3)
  else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
INF = 10**6

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

distance = [INF] * (n * 3)
dq = deque()
dq.append([0, s*3])
while(dq):
    dist, node = dq.popleft()
    if len(edge[node]) == 0:
        distance[node] = dist 
        continue
    if distance[node] != INF:
        continue
    distance[node] = dist 
    dist += 1
    for item in edge[node]:
        dq.append([dist, item])
if distance[t*3] == INF:
    print(-1)
else:
    print((distance[t*3]) // 3)

Submission status: Accepted

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(M):
    u, v = nl()
    edges[u].add(v+N)
    edges[u+N].add(v+2*N)
    edges[u+2*N].add(v)

S, T = nl()

import queue
q = queue.Queue()
q.put((S, 0))

done = [False] * (3*N+1)
done[S] = True

while not q.empty():
    src, cost = q.get()
    for dst in edges[src]:
        if dst == T:
            print((cost+1) // 3)
            import sys
            sys.exit()

        if not done[dst]:
            done[dst] = True
            q.put((dst, cost+1))

print(-1)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

INF = 10 ** 15

dd = [[INF, INF, INF] for _ in range(n)]
visited = [[False, False, False] for _ in range(n)]

s, t = map(int, input().split())
s -= 1
t -= 1
dd[s] = [0, 0, 0]
q = [(0, s)]
ans = -1

while q:
    d, v = heappop(q)
    if visited[v][d%3]:
        continue
    visited[v][d%3] = True
    if v == t and d % 3 == 0:
        ans = d//3
        break
    to_d = d+1
    for to_v in MAP[v]:
        if visited[to_v][to_d % 3]:
            continue
        heappush(q, (to_d, to_v))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

# 頂点数、辺数
N, M = list(map(int, input().split()))

# 隣接リスト表現
repn = [[[] for l in range(3)] for u in range(N)]
for j in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    repn[a][0].append((b, 1))
    repn[a][1].append((b, 2))
    repn[a][2].append((b, 0))

# 気にする頂点、０オリジンなのでちょっといじった
S, T = list(map(int, input().split()))
s = S - 1
t = T - 1

# ＳからＴまで３の倍数でたどり着く最短経路を求めたい
# 「３の倍数」の条件が無ければBFSで片付く
# そこでグラフを３層にして「３の倍数」の条件を外す

# 具体的にはグラフの頂点を (u, l) = {頂点uで階層lの点（l = 0, 1, 2）}
# グラフの辺を(u, l) -> (v, l+1)と読み替える
# 求めるのは(S, 0) -> (T, 0)の最短経路
# 後はただのBFS

color = [['WHITE' for l in range(3)] for u in range(N)]
d = [[-1, -1, -1] for u in range(N)]
Q = deque([])

color[s][0] = 'GRAY'
d[s][0] = 0
Q.append((s, 0))

while len(Q) != 0:
    u, l = Q.popleft()
    for x in repn[u][l]:
        v, r = x
        if color[v][r] == 'WHITE':
            color[v][r] = 'GRAY'
            d[v][r] = d[u][l] + 1
            Q.append(x)
    color[u][l] = 'BLACK'

print(d[t][0] // 3)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(graph, start, end):
    queue = deque([start])
    visited = [-1] * len(graph)
    visited[start] = 0
    while queue:
        pos = queue.popleft()
        if pos == end: return visited[pos]
        for next_pos in graph[pos]:
            if visited[next_pos] == -1:
                visited[next_pos] = visited[pos] + 1
                queue.append(next_pos)
    return -1

def solve():
    N, M = map(int, input().split())
    graph = [[] for i in range(N * 3)]
    for i in range(M):
        u, v = map(lambda s: int(s) - 1, input().split())
        graph[N * 0 + u].append(N * 1 + v)
        graph[N * 1 + u].append(N * 2 + v)
        graph[N * 2 + u].append(N * 0 + v)
    S, T = map(lambda s: int(s) - 1, input().split())
    dist = bfs(graph, S, T)
    return dist // 3 if dist != -1 else -1


print(solve())

Submission status: Accepted

Solution code:
from collections import deque
import sys
inputs = sys.stdin.readline
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,inputs().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[] for i in range(3*N)]
for u,v in UV:
    es[u].append(v+N)
    es[u+N].append(v+2*N)
    es[u+2*N].append(v)

q = deque([S])
INF = float('inf')
dist = [INF] * (3*N)
dist[S] = 0

while q:
    v = q.popleft()
    for to in es[v]:
        if dist[to] != INF: continue
        dist[to] = dist[v] + 1
        if to==T:
            print(dist[to] // 3)
            exit()
        q.append(to)
print(-1)

Submission status: Accepted

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

N,M=map(int,input().split())
E=[list(map(int,input().split())) for i in range(M)]
S,G=map(int,input().split())

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

for x,y in E:
    ELIST[x].append(y)

DIS=[[-1,-1,-1] for i in range(N+1)]
DIS[S][0]=0

from collections import deque

S=deque([S])
i=1

while S:
    #print(S)
    NEWS=deque()
    while S:     
        x=S.pop()

        for to in ELIST[x]:
            if DIS[to][i%3]==-1:
                DIS[to][i%3]=i
                NEWS.append(to)

    i+=1
    S=NEWS

print(DIS[G][0]//3)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     d=[float('inf') for i in range(3*n)]
     d[s]=0
     
     que=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if j==t:
                         print(cnt//3)
                         return
                    if d[j]>cnt:
                         d[j]=cnt
                         que2.append(j)
                         
          que=que2
     if d[t]==float('inf'):
          print(-1)
     else:
          print(d[t]//3)
     return 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     d=[float('inf') for i in range(3*n)]
     d[s]=0
     
     que=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if d[j]>cnt:
                         d[j]=cnt
                         que2.append(j)
          que=que2
     if d[t]==float('inf'):
          print(-1)
     else:
          print(d[t]//3)
     return 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

S, T = map(int, input().split())
S -= 1
T -= 1
Q = deque([S])
D = [999999] * N * 3

D[S] = 0
while Q:
    x = Q.popleft()
    for c in X[x]:
        if D[c] == 999999:
            D[c] = D[x]+1
            Q.append(c)
print(-1 if D[T] == 999999 else D[T]//3)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N*3)]
    dp = [[[] for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].add(N*1+v)
        adj[N*1+u].add(N*2+v)
        adj[N*2+u].add(v)
    S, T = map(int, input().split())
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost//3)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
inf = float('INF')

def dijkstra(graph, n, s):
    costs = [[inf for j in range(3)] for i in range(n+1)]
    costs[s][0], Q = 0, []
    heapq.heappush(Q, [costs[s][0], 0, s])

    while(Q != []):
        c, num, u = heapq.heappop(Q)
        next_ = (num+1)%3
        if u not in graph:
            continue
        for v, three in graph[u].items():
            if costs[u][num] + 1 < costs[v][next_]:
                heapq.heappush(Q, [costs[u][num] + 1, three[next_], v])
                costs[v][next_] = costs[u][num] + 1
    return costs

N,M = map(int, input().split())
graph = {}
for i in range(M):
    u,v = map(int, input().split())
    if u not in graph:
        graph[u] = {}
    graph[u][v] = {}
    graph[u][v][0] = 0
    graph[u][v][1] = 1
    graph[u][v][2] = 2
S,T = map(int,input().split())

di = dijkstra(graph, N, S)
if di[T][0] == inf:
    print(-1)
else:
    print(di[T][0]//3)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

INF = pow(10, 15)

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

  dd = [[INF, INF, INF] for _ in range(n)]
  visited = [[False, False, False] for _ in range(n)]
  s, t = map(int, input().split())
  s -= 1
  t -= 1
  dd[s] = [0,0,0]
  q = [(0, s)]
  ans = -1
  while q:
    d, v = heappop(q)
    if visited[v][d%3]:
      continue
    visited[v][d%3] = True
    if v == t and d % 3 == 0:
      ans = d // 3
      break
    to_d = d + 1
    for to_v in edges[v]:
      if visited[to_v][to_d % 3]:
        continue
      heappush(q, (to_d, to_v))
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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
    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)
S,T = map(int,input().split())
S -=1
T -=1
def dijkstra(v):
    d = [inf] * (3*N)
    d[v] = 0
    hq =[(0,v)]

    while hq:
        u = heappop(hq)[1]
        for v in G[u]:
            if d[v] > d[u] + 1:
                d[v] = d[u] +1
                heappush(hq,(d[u]+1,v))
    return d
dist = dijkstra(S)
if dist[T]==inf:
    print(-1)
else:
    print(dist[T]//3)

Submission status: Accepted

Solution code:
import sys
from collections import deque
n, m=map(int,input().split())
"""
頂点1~nを1~3nに3倍加する
"""
edges=[[] for i in range(3*n)]
for i in range(m):
    """
    uからvへの枝を
    uからv+n, u+nからv+2n, u+2nからv+3n
    とする
    (枝を3倍加)
    """
    u, v=map(int, input().split())
    u, v=u-1, v-1
    edges[u].append(v+n)
    edges[u+n].append(v+2*n)
    edges[u+2*n].append(v)
s, t=map(int, input().split())
s, t=s-1, t-1
q=deque()
q.append(s)
dist=[-1]*(3*n)
dist[s]=0
"""
結局求めるものは，s~tへの最短距離を3で割ったもの
"""
while len(q)!=0:
    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 collections

N,M = map(int, input().split())
G = [[] for i in range(3*N+1)]

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

def bfs(s):
  que = collections.deque()
  que.append(s)
  d = [-1 for _ in range(3*N+1)]
  d[s] = 0

  while (0 < len(que)):

    p = que.popleft()
    if (T == p):
      return d[p]

    for pp in G[p]:
      if d[pp] == -1:
        que.append(pp)
        d[pp] = d[p]+1

  return -1

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

Submission status: Accepted

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

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

num = s
step = 0
q = [[num, step]]
check = [[False for i in range(N)] for j in range(3)]
ok = False
while len(q) > 0:
    num, step = q.pop(0)
    tmp = step % 3
    if tmp == 0 and num == t:
        print(step//3)
        ok = True
        break
    for next in nodes[num]:
        if not check[tmp][next]:
            check[tmp][next] = True
            q.append([next, step+1])
if not ok:
    print(-1)

Submission status: Accepted

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

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

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  #if t>300003:
  #  print(-1)
  #  sys.exit()
  
  #nlist = []
  nset = set()
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          #nlist.append(vv)
          nset.add(vv)
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  #vlist = nlist
  vlist = list(nset)
  if len(vlist) == 0:
    print(-1)
    break

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, M = LI()
    graph = []
    from collections import defaultdict
    reversed_graph_dict = defaultdict(list)
    for _ in range(M):
        u, v = LI()
        graph.append([u,v])
        reversed_graph_dict[v].append(u)
    S, T = LI()

    # print(reversed_graph_dict)

    import collections
    def bfs(graph, root):
        seen, queue = set([root]), collections.deque([[root, 0],])
        first_step_seen = set([])
        second_step_seen = set([])
        while queue:
            vertex, tries = queue.popleft()
            tries += 1

            # 三段先を見に行く。
            first_step = graph[vertex]

            second_step = []
            for x in set(first_step) - first_step_seen:
                second_step += graph[x]
            first_step_seen |= set(first_step)

            third_step = []
            for x in set(second_step) - second_step_seen:
                third_step += graph[x]
            second_step_seen |= set(second_step)

            for node in set(third_step):
                if node == S:
                    print(tries)
                    return
                if node not in seen:
                    seen.add(node)
                    queue.append([node, tries])
        print(-1)
        return

    bfs(reversed_graph_dict, T)


main()

Submission status: Accepted

Solution code:
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
s,t=map(int,input().split())
check=[[0]*3 for _ in range(n+1)]
check[s][0]=1
q=collections.deque()
q.append([s,0])
ans=0
while len(q)!=0:
  v,c=q.popleft()
  if v==t and c%3==0:
    ans=c//3
    break
  for i in g[v]:
    if check[i][(c+1)%3]==0:
      q.append([i,c+1])
      check[i][(c+1)%3]=1
if ans==0:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M = [int(i) for i in input().split()]
#N = int(input())

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

S, T = [int(i) for i in input().split()]
d1 = Dijkstra(g, (S-1)*3)
ans = 0
if d1.dist[(T-1)*3] != float("inf"):
    print(d1.dist[(T-1)*3]//3)
else:
    print(-1)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
link = {(i, j) : [] for i in range(1, N+1) for j in range(3)}
for _ in range(M):
    u, v = map(int, input().split())
    link[(u, 0)].append((v, 1))
    link[(u, 1)].append((v, 2))
    link[(u, 2)].append((v, 0))
S, T = map(int, input().split())

''' dijkstra '''
INF = 10 ** 9
vstd = {(i, j): False for i in range(1, N+1) for j in range(3)}
dist = {(i, j): INF for i in range(1, N+1) for j in range(3)}  # distance
# prev = {i: -1 for i in range(1, N+1)}  # for extract min cost path
pq = []
# initialize
dist[(S, 0)] = 0
heappush(pq, (0, (S, 0)))
while pq:
    _, u = heappop(pq)
    vstd[u] = True
    for v in link[u]:
        if vstd[v]:
            continue
        if dist[u] + 1 < dist[v]:
            dist[v] = dist[u] + 1
            # prev[v] = u
            heappush(pq, (dist[v], v))


print(dist[(T, 0)] // 3 if dist[(T, 0)] % 3 == 0 else -1)

Submission status: Accepted

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

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

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

INF = 10**10
d = [INF for i in range(3*N)]

que = []
d[S-1] = 0
heapq.heappush(que, [0, S-1])

while not(len(que) == 0):
    q = heapq.heappop(que)
    ver = q[1]
    dis = q[0]
    
    if d[ver] < dis:
        continue

    for i in range(len(G[ver])):
        e = G[ver][i]
        if d[e[0]] > d[ver] + e[1]:
            d[e[0]] = d[ver] + e[1]
            heapq.heappush(que, [d[e[0]], e[0]])

if d[T-1] == INF:
    print(-1)
else:
    print(d[T-1]//3)

Submission status: Accepted

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

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

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

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

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    NextCost = 1
    while heap:
        cost,thisNode = heappop(heap)
        for NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

inf = float('inf')
dist = dijkstra(graph1, n*3, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t]//3)

Submission status: Accepted

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

import heapq

INF = float('inf')

def dijkstra(graph, st):
    n  = len(graph)
    ds = [[INF]*3 for _ in range(n)]
    ds[st][0] = 0
    ds[st][1] = INF
    ds[st][2] = INF
    
    qs = [(0, st, 0)]
    heapq.heapify(qs)

    while len(qs) > 0:
        d, nodeId, mod = heapq.heappop(qs)
        
        if d > ds[nodeId][mod]:
            continue
        
        for destId in graph[nodeId]:
            d2 = d + 1
            mod2 = d2%3

            if ds[destId][mod2] > d2:
                ds[destId][mod2] = d2
                heapq.heappush(qs, (d2, destId, mod2))
                
    return (ds)


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

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

    ds = dijkstra(V, S-1)
    x = ds[T-1][0]

    print(x//3 if x != INF else -1)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
S,T = map(int,input().split())
dij = dijkstra(g,3*N,S-1)
ans = dij[T-1]//3
if ans == float('inf') or ans!=ans:
    ans = -1
print(ans)