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:
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

N, M = inpl()
uv = [ set() for _ in range(3*N) ]
vu = [ set() for _ in range(3*N) ]
for _ in range(M):
    u, v = inpl()
    for k in range(3):
        uv[u-1 + k*N].add(v-1 + ((k+1)%3)*N)
        vu[v-1 + ((k+1)%3)*N].add(u-1 + k*N)
S, T = inpl()
S -= 1
T -= 1

cur = set({S})
for i in range(3*N):
    if i % 3 == 0 and T in cur:
        print(i//3)
        break
    elif len(cur) == 0:
        print(-1)
        break
    prev = cur
    cur = set()
    for u in prev:
        for fr in vu[u]:
            uv[fr].remove(u)
        cur |= uv[u]
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

INF = -1

nVertices, nEdges = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nEdges):
    u, v = map(int, input().split())
    edges[u].append(v)
s, t = map(int, input().split())

dist = [[INF for _ in range(3)] for _ in range(nVertices + 1)]
dist[s][0] = 0
q = deque()
q.append((s, 0))
while q:
    curVertex, curDist = q.popleft()
    for nextVertex in edges[curVertex]:
        nextDist = curDist + 1
        if dist[nextVertex][nextDist % 3] == INF:
            dist[nextVertex][nextDist % 3] = nextDist
            q.append((nextVertex, nextDist))

print(dist[t][0] // 3 if dist[t][0] != INF else INF)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
UV = [list(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())

if 0 == M:
	print(-1)
	exit()

graph = [set() for _ in range(N)]
for u, v in UV:
	graph[u - 1] |= {v - 1}

INF = 10 ** 12
depths = [[INF, INF, INF] for _ in range(N)]

def bfs(start, end):
	depth = 0
	nodes = {start}
	while nodes:
		if (0 == depth % 3) and (end in nodes):
			return depth // 3
		next_nodes = set()
		for node in nodes:
			if depths[node][depth % 3] <= depth:
				continue
			depths[node][depth % 3] = depth
			next_nodes |= graph[node]
		nodes = next_nodes
		depth += 1
	return -1

print(bfs(S - 1, T - 1))

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

if __name__ == "__main__":
    N, M = l_inpl()

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

    for _ in range(M):
        u, v = l_inpl()
        u, v = u-1, v-1
        to[u].append(v)

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

    dist = [[INF, INF, INF] for _ in range(N)]
    dist[S][0] = 0

    q = deque([])
    q.append([S, 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:
from collections import deque

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

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

INF = 10**10

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        0-indexedでなくてもよいことに注意
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d=1, directed=False, ):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        0-indexedでなくてもよいことに注意
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d


graph = Dijkstra()
N, M = map(int, input().split())
for i in range(M):
    u, v = map(int, input().split())
    graph.add(u, v+N, directed=True)
    graph.add(u+N, v+2*N, directed=True)
    graph.add(u+2*N, v, directed=True)


S, T = map(int, input().split())
d = graph.Dijkstra_search(S)
if d[T] == float('inf'):
    print(-1)
else:
    print(d[T] // 3)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(3*n)]
v=[-1 for _ in range(3*n)]
for i in range(m):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    g[x].append(y+n)
    g[x+n].append(y+2*n)
    g[x+2*n].append(y)
s,t=map(int,input().split())
s,t=s-1,t-1

def bfs(x,y):
    q=deque()
    q.append(x)
    v[x]=0
    while q:
        p=q.popleft()
        for nb in g[p]:
            if v[nb]==-1:
                q.append(nb)
                v[nb]=v[p]+1
                if nb==t:
                    return v[t]//3
    return -1
    
print(bfs(s,t))

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] != -1:
    print(dist[t]//3)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque


class Graph:

  def __init__(self, directed=True):
    self.directed = directed
    self.V = set()
    self.E = {}

  def add_edge(self, u, v, weight: float = 1.):
    self.V.add(u)
    self.V.add(v)

    if u not in self.E: self.E[u] = {}
    self.E[u][v] = weight

    if not self.directed:
      if v not in self.E: self.E[v] = {}
      self.E[v][u] = weight


def bfs(graph: Graph, s):
  V, E = graph.V, graph.E

  visited = set()
  pred = {}
  dist = {}
  for v in graph.V: dist[v] = -1

  if not s in E:
    return pred, dist

  visited.add(s)
  dist[s] = 0
  queue = deque()
  queue.append(s)
  while len(queue) > 0:
    u = queue.popleft()
    for v in E[u]:
      if v not in visited:
        pred[v] = u
        dist[v] = dist[u] + 1
        visited.add(v)
        if v in E: queue.append(v)

  return pred, dist


def main():
  graph = Graph()

  N, M = map(int, input().strip().split())
  for _ in range(M):
    u, v = input().strip().split()
    # graph.add_edge(u, v)
    graph.add_edge(u + '_0', v + '_1')
    graph.add_edge(u + '_1', v + '_2')
    graph.add_edge(u + '_2', v + '_0')

  s, t = input().strip().split()

  pred, dist = bfs(graph, s + '_0')
  # pred, dist = bfs(graph, s)
  key = t + '_0'
  if key in dist:
    distance = dist[key]
    if distance % 3 == 0:
      return (distance // 3)

  return -1


print(main())

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

# 拡張グラフにダイクストラ法を適用し最適解を求める
G = [{} for _ in range(3 * N + 1)]
for x, y in zip(A, B):
    G[x][y + N] = 1
    G[x + N][y + 2 * N] = 1
    G[x + 2 * N][y] = 1
INF = 10**18


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp = dijkstra(G, S)
ans = (
    -1 if dp[T] == INF else
    dp[T] // 3
)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Jul  1 11:43:19 2019

@author: Yamazaki Kenichi
"""
from collections import deque

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

Ta = [[] for i in range(3*N+1)]
for c in uv:
    Ta[c[0]].append(c[1]+N)
    Ta[c[0]+N].append(c[1]+2*N)
    Ta[c[0]+2*N].append(c[1])

check = [0 for i in range(3*N+1)]

q = deque([S])
check[S] = 1
counta = 0
flg = False
while len(q) > 0:
    for i in range(len(q)):
        nexts = Ta[q.popleft()]
        for next_ in nexts:
            if check[next_] != 1:
                q.append(next_)
                check[next_] = 1
    counta += 1
    if check[T] == 1:
        flg = True
        break
if flg:
    print(counta//3)
else:
    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 = {(u, i): set([(v, (i + 1) % 3) for v in E[u]])
     for u in E for i in range(3)}

# bfs
queue = deque([((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:
import collections
N, M = [int(_) for _ in input().split()]
UV = [[int(_) for _ in input().split()] for _ in range(M)]
s, t = [int(_) for _ in input().split()]
v = [[0] * (N + 1) for _ in range(3)]
v[0][s] = 1
G = collections.defaultdict(set)
for U, V in UV:
    G[U].add(V)
Q = collections.deque([[0, s]])
while Q:
    d, i0 = Q.popleft()
    d += 1
    for i1 in G[i0]:
        if not v[1][i1]:
            v[1][i1] = 1
            for i2 in G[i1]:
                if not v[2][i2]:
                    v[2][i2] = 1
                    for i3 in G[i2]:
                        if i3 == t:
                            print(d)
                            exit()
                        elif not v[0][i3]:
                            v[0][i3] = 1
                            Q += [[d, i3]]
print(-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)
#print(a)
 
S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    c2 = []
    for u in c:
      for v in a[u]:
        if (v == T and count %3 ==0):
          return count//3
        if not(m[v][count %3]):
          m[v][count %3]=True
          c2.append(v)
    c = c2
  return -1
print(main())

Submission status: Accepted

Solution code:
from collections import*
n,m,*w,s,t=map(int,open(0).read().split())
e=[[]for _ in[0]*-~n]
for u,v in zip(w[::2],w[1::2]):e[u]+=v,
f=[-3]*n*4
f[s*3]=0
q=deque([(s,0)])
while q:
  v,m=q.popleft()
  u=-~m%3
  for w in e[v]:
    if f[w*3+u]<0:
      f[w*3+u]=f[v*3+m]+1
      q+=(w,u),
print(f[t*3]//3)

Submission status: Accepted

Solution code:
from collections import*
n,m,*w,s,t=map(int,open(0).read().split())
e=[[]for _ in range(n+1)]
for u,v in zip(w[::2],w[1::2]):e[u].append(v)
f=[[-3]*3for _ in range(n+1)]
f[s][0]=0
q=deque([(s,0)])
while q:
  v,m=q.popleft()
  for w in e[v]:
    if f[w][-~m%3]<0:
      f[w][-~m%3]=f[v][m]+1
      q+=[(w,-~m%3)]
print(f[t][0]//3)

Submission status: Accepted

Solution code:
from collections import*
n,m,*t=map(int,open(0).read().split())
*w,s,t=[t-1for t in t]
e=[[]for _ in range(n)]
for u,v in zip(w[::2],w[1::2]):
  e[u].append(v)
INF=10**18
f=[[INF]*3for _ in range(n)]
f[s][0]=0
q=deque([(s,0)])
while q:
  v,m=q.popleft()
  if v==t and m==0:
    print(f[v][0]//3)
    break
  for w in e[v]:
    if f[w][-~m%3]<INF:continue
    f[w][-~m%3]=f[v][m]+1
    q.append((w,-~m%3))
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = map(int, input().split())

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

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

#p("N,M",N,M)
#p("G",G)
#p("S,T",S,T)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
# 3倍になる頂点を抽出するために、3ヵ所の記録が出来るよう「-1」を3つ準備する
V=[ [-1,-1,-1] for _ in range(N+1) ]			#=> [ [-1,-1,-1], [-1,-1,-1], ... [-1,-1,-1] ]
V[S][0]=0

# キューに行き先候補を入れて、
from collections import deque
Q = deque()
Q.append([S,0])

while Q:
	sv = Q[0][0]
	sl = Q[0][1]
	Q.popleft()
	
	for tv in G[sv]:
		tl = (sl+1)%3
		b = (V[tv][tl]==-1)									# 未訪問である
		#b = b or (V[tv][tl]>V[sv][sl]+1)		# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[tv][tl] = V[sv][sl]+1		# 訪問ステップ数の記録
			Q.append([tv,tl])					# 次の訪問先として、キューに追加

ans = V[T][0]
if ans > -1: ans //= 3
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
n, m = list(map(int, input().split()))
graph = defaultdict(list)
for i in range(m):
  u, v = list(map(int, input().split()))
  graph[u].append(v+n)
  graph[u+n].append(v+2*n)
  graph[u+2*n].append(v)
s, t = list(map(int, input().split()))
dist = [-1 for i in range(3*n+10)]

def bfs():
  que = deque([s])
  dist[s] = 0
  while len(que) > 0:
    cur = que.popleft()
    if cur==t:
      return dist[cur]//3
    for to in graph[cur]:
      if dist[to] == -1:
        dist[to] = dist[cur]+1
        que.append(to)
  return -1

print(bfs())

Submission status: Accepted

Solution code:
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = map(int, input().split())

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

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

#p("N,M",N,M)
#p("G",G)
#p("S,T",S,T)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
V=[ [-1,-1,-1] for _ in range(N+1) ]			#=> [ [-1,-1,-1], [-1,-1,-1], ... [-1,-1,-1] ]
V[S][0]=0

# キューに行き先候補を入れて、
from collections import deque
Q = deque()
Q.append([S,0])

while Q:
	FM = Q.popleft()
	
	fm = FM[0]
	l =  FM[1]
	
	for to in G[fm]:
		nl = (l+1)%3
		b = (V[to][nl]==-1)							# 未訪問である
		#b = b or (V[to]>(V[fm]+1))	# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[to][nl] = V[fm][l]+1		# 訪問ステップ数の記録
			Q.append([to,nl])			# 次の訪問先として、キューに追加

ans = V[T][0]
if ans > -1: ans //= 3
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
n, m = list(map(int, input().split()))
graph = defaultdict(list)
for i in range(m):
  u, v = list(map(int, input().split()))
  graph[u].append(v+n)
  graph[u+n].append(v+2*n)
  graph[u+2*n].append(v)
s, t = list(map(int, input().split()))
dist = [-1 for i in range(3*n+10)]

def bfs():
  que = deque([s])
  dist[s] = 0
  while len(que) > 0:
    cur = que.popleft()
    for to in graph[cur]:
      if dist[to] == -1:
        dist[to] = dist[cur]+1
        que.append(to)

bfs()
print(dist[t]//3)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
n, m = list(map(int, input().split()))
graph = defaultdict(set)
for i in range(m):
  u, v = list(map(int, input().split()))
  graph[u].add(v)
s, t = list(map(int, input().split()))
dist = [[-1 for i in range(3)] for i in range(10**5+10)]

def bfs():
  que = deque([(s, 0, 0)]) #(x, cost, kenkenpa)
  while len(que) > 0:
    p = que.popleft()
    if dist[p[0]][p[2]] != -1:
      continue
    dist[p[0]][p[2]] = p[1]
    for nx in graph[p[0]]:
      que.append((nx, p[1]+1, (p[2]+1)%3))

bfs()
print(dist[t][0]//3)

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]

inputs=[]
n,m=map(int,input().split())
for i in range(m):
    a=[int(j) for j in input().split()]
    inputs.append((a[0],a[1]+10**5,1))
    inputs.append((a[0]+10**5,a[1]+2*10**5,1))
    inputs.append((a[0]+2*10**5,a[1],1))
S,T=map(int,input().split())

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)

d = Dijkstra(g, S)   
ans=d.shortest_distance(T)

if ans>10**9+7:
    print(-1)
else:
    if ans%3==0:
        print(ans//3)
    else:
        print(-1)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
E = [list() for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    E[u].append(v)
S, T = map(int, input().split())

Visited = [[False]*(N+1) for _ in range(3)]
Visited[0][S] = True
queue = deque()
queue.append((S,0))

while queue:
    cur, path = queue.popleft()
    for neighbor in E[cur]:
        if Visited[(path+1)%3][neighbor]==False:
            queue.append((neighbor, path+1))
            Visited[(path+1)%3][neighbor] = path + 1
            
ans = Visited[0][T]

if ans==False:
    print(-1)
elif ans > 2:
    ans //= 3
    print(ans)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def bfs():
  while len(q) > 0:
    p = q.popleft()
    for e in g[p]:
      if d[e] < 0:
        q.append(e)
        d[e] = d[p] + 1
        f[e] = p
      elif d[e] > d[p] + 1:
        d[e] = d[p] + 1
        f[e] = p       

  
  
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[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())

d = [-1] * (3 * (n+1))
f = [-1] * (3 * (n+1))
d[3*s] = 0
f[3*s] = 0
q = deque([3*s])
bfs()
c = 0
if f[3*t] == -1:
  print(-1)
  exit()

t = 3 * t
while f[t] > 0:
  c += 1
  t = f[t]
  
print(c // 3)

Submission status: Accepted

Solution code:
from collections import deque

INF = int(1e9 + 7)


def bfs(g, s, t):
    q = deque()
    q.append((s, 0))
    d = [] * 100000
    for _ in range(100000):
        d.append([INF, INF, INF])
    d[s][0] = 0
    while q:
        v_c, l = q.popleft()
        nl = (l + 1) % 3
        for vt in g[v_c]:
            if d[vt][nl] != INF:
                continue
            d[vt][nl] = d[v_c][l] + 1
            if vt == t and nl == 0:
                return d[vt][nl] // 3
            q.append((vt, nl))
    return -1


n, m = map(int, input().split())
graph = [] * n
for i in range(n):
    graph.append([])
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)
s, t = map(int, input().split())
print(bfs(graph, s - 1, t - 1))

Submission status: Accepted

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

for i in range(3 * N):
    node_dic[i] = []

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

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

ans_array = [-1] * (3 * N)
use_array = [0] * (3 * N)

edge_queue = deque()
ans_array[(S-1)*3] = 0
use_array[(S-1)*3] = 1
edge_queue.append((S-1)*3)
while(len(edge_queue)):
    edge = edge_queue.popleft()
    value = ans_array[edge]
    for e in node_dic[edge]:
        if not use_array[e]:
            edge_queue.append(e)
            ans_array[e] = value + 1
            use_array[e] = 1

print(ans_array[(T-1)*3]//3)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    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[3 * u].append(3 * v + 1)
        edges[3 * u + 1].append(3 * v + 2)
        edges[3 * u + 2].append(3 * v)

    S, T = map(lambda x: (int(x) - 1) * 3, input().split())
    q = deque([(S, 0)])
    nodes = [-1] * (3 * N)

    while q:
        cv, count = q.popleft()

        if cv == T:
            nodes[cv] = count if nodes[cv] == -1 else min(nodes[cv], count)
        else:
            if nodes[cv] == -1 or count < nodes[cv]:
                nodes[cv] = count
                for u in edges[cv]:
                    q.append((u, count + 1))

    print(nodes[T] // 3 if nodes[cv] != -1 else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

inf = float('inf')

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

es = [[] for _ in range(N * 3)]
# 有向グラフ

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

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

dq = deque([(S, 0)])
dist = [inf] * (N * 3)
dist[S] = 0

while dq:
    v, c = dq.popleft()
    nc = c + 1
    for nv in es[v]:
        if nc < dist[nv]:
            dist[nv] = nc
            if v == T:
                break
            dq.append((nv, nc))

if dist[T] == inf:
    print(-1)
else:
    print(dist[T] // 3)

# print(dist)

Submission status: Accepted

Solution code:
import heapq
def sol(inp=input):
    s=3
    n,m=map(int,inp().split())
    G={(i+1,j):set() for i in range(n) for j in range(s)}
    for _ in range(m):
        u,v=map(int,inp().split())
        for i in range(s):
            G[(u,i)].add((v,(i+1)%s))
    s,t=map(int,inp().split())
    visited={(s,0)}
    que=[]
    heapq.heappush(que,(0,(s,0)))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in G[u]:
            if v not in visited:
                visited.add(v)
                heapq.heappush(que,(step+1,v))
            if v==(t,0):
                return (step+1)//3
    return -1
print(sol())

Submission status: Accepted

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

def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=0
    w=deque([0,s])
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n*=3
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

if __name__=="__main__":
    sol()

Submission status: Accepted

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

def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    #tmp=[0]*(n+1)
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)
#print(a)

S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    c2 = []
    for u in c:
      m[u][count %3] = True
      for v in a[u]:
        if (v == T and count %3 ==0):
          return count//3
        if not(m[v][(count+1) %3]):
          m[v][(count+1) %3]=True
          c2.append(v)
    c = c2
  return -1
print(main())