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

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,M = list(map(int,input().split()))

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

    def z(i,j):
        return i + j*N

    for i in range(M):
        u,v = list(map(int,input().split()))
        u,v = u-1,v-1
        e_list[z(u,0)].append(z(v,1)) 
        e_list[z(u,1)].append(z(v,2)) 
        e_list[z(u,2)].append(z(v,0))

    S,T = list(map(int,input().split()))
    S,T = S-1,T-1
    from collections import deque

    vi = z(S,0)  #change
    INF = float('inf')

    Q = deque([vi])

    checked_list = [False]*3*N
    checked_list[vi]=True

    min_path_list = [INF]*3*N #change
    min_path_list[vi] = 0

    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if not checked_list[v1]:
                checked_list[v1]=True
                Q.appendleft(v1)
                min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #change

    if min_path_list[z(T,0)]<10**9:
        print(min_path_list[z(T,0)]//3)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

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

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = deque([S])
ans[S][0] = 0
while q:
    now = q.popleft()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

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

Submission status: Accepted

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    uvs = [tuple(map(int, input().split())) for _ in range(m)]
    s, t = map(int, input().split())
    edges = [{} for _ in range(n*3)]
    for u, v in uvs:
        x, y = u-1, v-1
        for i in range(3):
            c = 1 if i == 0 else 0
            z = y + n*((i+1)%3)
            edges[x + n*i][z] = c
    l = dijkstra(edges, s-1, t-1)
    if l is None:
        print(-1)
    else:
        print(l)

def dijkstra(graph, start, end):
    q = []
    heapq.heapify(q)
    visited = set()

    for next_, cost in graph[start].items():
        heapq.heappush(q, (cost, next_))

    while len(q) > 0:
        node_cost, current = heapq.heappop(q)
        if current in visited:
            continue
        if current == end:
            return node_cost

        visited.add(current)
        for next_, path_cost in graph[current].items():
            heapq.heappush(q, (node_cost + path_cost, next_))

    return None

main()

Submission status: Accepted

Solution code:
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

FIFO=deque()
N,M=LI()
MP=[[[],[],[]] for i in range(N+1)]

# グラフ作成
for _ in range(M):
    i,j=LI()
    MP[i][0].append((j,1))
    MP[i][1].append((j,2))
    MP[i][2].append((j,0))

S,T=LI()
FIFO.append((S,0,0))
visited = [[False,False,False] for i in range(N+1)]
visited[S][0] = True

res = -1
while FIFO:
    i, rest_i, dist = FIFO.popleft()
    if i == T and rest_i == 0:
        res = dist // 3
        break
    for j, rest_j in MP[i][rest_i]:
        if not visited[j][rest_j]:
            visited[j][rest_j] = True
            FIFO.append((j, rest_j, dist+1))

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC132 E
#有向グラフ上の路長が3の倍数であるようなものの内、最短の長さを3で割ったものを出力

import sys
sys.setrecursionlimit(1000000)
from collections import deque

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

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

for i in UV:
    G[i[0]-1].append(i[1]-1)

reach = [[-1 for _ in range(N)] for _ in range(3)]#元のグラフのGの状態数3倍化
reach[0][S-1] = 0#スタート位置を0にする

que = deque()
que.append(S-1)#スタート位置を追加

time = 1
for _ in range(4*N):
    new_que = deque()
    for q in que:
        for v in G[q]:#qから移動できる辺を見る
            if reach[time%3][v] == -1:#まだたどり着いていない辺なら
                reach[time%3][v] = time#たどり着けた時刻をたどり着いた時刻を3で割った余りのリストに入れる
                new_que.append(v)#たどり着いた頂点をqueueにいれて次のターンでそこから移動できる辺を見る
    que = new_que
    time += 1
if reach[0][T-1] == -1:
    print(-1)
else:
    print(reach[0][T-1]//3)

Submission status: Accepted

Solution code:
##########################################
inf=10**9
import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """    
    class Edge():
        #重み付き有向辺
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        #引数Vは頂点数
        self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
        self. _E = 0 #辺の数
        self._V = V #頂点数
    
    #proparty - 辺の数
    def E(self):
        return self._E
    
    #proparty - 頂点数
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        #2頂点と辺のコストを追加
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        #2頂点と辺のコスト（無向）を追加
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s):
        #始点sから頂点iまでの最短経路長のリストを返す
        
        que = [] #priority queue
        d = [inf] * self.V()
        prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
        d[s] = 0
        heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
        
        while len(que)!=0:
            #キューに格納されてある中で一番コストが小さい頂点を取り出す
            cost,v = heapq.heappop(que)
            
            #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
            if d[v] < cost:
                continue
                
            #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
            for i in range(len(self.G[v])):
                e = self.G[v][i] #vのi個目の隣接辺
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost #更新
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

        return d
########################

#グラフの頂点を3倍化

import sys
input = sys.stdin.readline

N,M=map(int,input().split())
djk = Dijkstra(N*3)

for i in range(M):
    u,v=map(int,input().split())
    u-=1
    v-=1
    djk.add(u,N+v,1)
    djk.add(N+u,2*N+v,1)
    djk.add(2*N+u,v,1)
S,T=map(int,input().split())

d = djk.shortest_path(S-1)
ans=d[T-1]//3
if ans==inf//3:
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)

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

ans = -1
visited = set()  # 通常であればvisited = [False]*N
q = [(0, S)]
while q:
    c, v = heappop(q)  # cはカウント, vは頂点の番号
    key = (c % 3, v)
    if key in visited:
        continue
    visited.add(key)  # グラフのノードの番号だけでなく、カウントも記録していく
    if v == T and c % 3 == 0:
        ans = c//3
        break
    c += 1  # u, 0から伸びる辺はv, 1で、u, 1から伸びる辺はv, 2
    d = c % 3  # 三種類の状態を記録したいのでmod3
    for u in graph[v]:
        new_key = (d, u)
        if new_key in visited:
            continue
        heappush(q, (c, u))

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
S, T = map(lambda x: int(x)-1, input().split())

ans = -1
visited = set()
q = [(0, S)]
ans = -1
while q:
    c, v = heappop(q)  # cはカウント, vは頂点の番号
    key = (c % 3, v)
    if key in visited:
        continue
    visited.add(key)
    if v == T and c % 3 == 0:
        ans = c//3
        break
    c += 1
    d = c % 3
    for u in graph[v]:
        new_key = (d, u)
        if new_key in visited:
            continue
        heappush(q, (c, u))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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


is_visited = [[False]*N for i in range(3)]
is_visited[0][s] = True

d = deque([s])
ans = 0
while d:
  ans += 1
  for step in [1, 2, 0]:
    diff = 0
    if d:
      len_d = len(d)
      for i in range(len_d):
        node = d.popleft()
        children = graph[node]
        for child in children:
          if step == 0:
            if child == t:
              d = []
              diff = 1
              break
          
          if not is_visited[step][child]:
            is_visited[step][child] = True
            diff += 1
            d.append(child)
          
        else:
          continue
        break
    
    else:
      ans = -1
      break
  
  if not diff:
    ans = -1
    break

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

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

next_dict = {}

for i in range(1,n*3 + 1):
    next_dict[i] = []

for i in range(m):
    u,v = uv[i]
    for j in range(3):
        next_dict[u + (j * n)].append((v + ((j+1)%3 * n )))

from collections import deque
d = deque()
d.append(s)

length = [-1] * (3*n + 1)
length[s] = 0

while(True):
    if(len(d) == 0):
        break

    num = d.popleft()
    for i in next_dict[num]:
        if( length[i] == -1 ):
            d.append(i)
            length[i] = length[num] + 1

    if(length[t] != -1):
        break

print(length[t] // 3)

Submission status: Accepted

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

from collections import deque
q=deque()
seen=[[False for i in range(3)] for j in range(N)]
q.append([S,0,1])
while q:
  node=q.popleft()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      print(turn)
      break
    step=0
    turn+=1
  if seen[v][step]:
    continue
  seen[v][step]=True
  children=E[v]
  for child in children:
    q.append([child,step+1,turn])
else:
  print(-1)

Submission status: Accepted

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

from collections import deque
stack=deque()
seen=[[False for i in range(3)] for j in range(N)]
stack.append([S,0,1])
while stack:
  node=stack.popleft()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      print(turn)
      break
    step=0
    turn+=1
  if seen[v][step]:
    continue
  seen[v][step]=True
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  print(-1)

Submission status: Accepted

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

def dijkstra(graph,N,s):
    distance = {(i + 1, j): 1e7 for i in range(N) for j in range(3)}
    distance[s]=0
    q=[]
    heapq.heappush(q,(distance[s],s))
    while len(q)>0:
        cost,v=heapq.heappop(q)
        if cost>distance[v]:
            continue
        else:
            for w in graph[v]:
                if distance[w]>distance[v]+1:
                    distance[w]=distance[v]+1
                    heapq.heappush(q,(distance[w],w))
    return distance


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))
    distance=dijkstra(graph,N,(S,0))
    d=distance[(T,0)]
    if d%3==0:
        print(d//3)
    else:
        print(-1)

Submission status: Accepted

Solution code:
from collections import deque

N,M=map(int,input().split())
a=[[[] for j in range(N)] for i in range(3)] # 0-indexのグラフが3つある
for i in range(M):
    u,v=map(lambda x:int(x)-1,input().split())
    a[0][u].append((1,v))
    a[1][u].append((2,v))
    a[2][u].append((0,v))
S,T=map(lambda x:int(x)-1,input().split())
# print(a)

r=[[-3 for j in range(N)] for i in range(3)]
q=deque()
q.append((0,S));r[0][S]=0
while q:
    ui,uj=q.popleft()
    for vi,vj in a[ui][uj]:
        if r[vi][vj]==-3:
            r[vi][vj]=r[ui][uj]+1
            q.append((vi,vj))
# print(r)
print(r[0][T]//3)

Submission status: Accepted

Solution code:
import sys
from collections import deque

# 最短経路に閉路がくっついているとは限らなかった・・・

read = sys.stdin.read
N, M, *uv, S, T = map(int, read().split())

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 15
# [けん,けんけん,けんけんぱ] * (N + 1)
dist = [[INF] * (N + 1) for _ in range(3)]
stack = deque([(0, S)])

while stack:
    cost, v = stack.popleft()
    r = cost % 3
    if dist[r][v] != INF:
        continue
    if r == 0 and v == T:
        print(cost // 3)
        exit()

    dist[r][v] = cost
    for i in graph[v]:
        stack.append((cost + 1, i))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

# 最短経路に閉路がくっついているとは限らなかった・・・

read = sys.stdin.read
N, M, *uv, S, T = map(int, read().split())

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 15
# [けん,けんけん,けんけんぱ] * (N + 1)
dist = [[INF] * (N + 1) for _ in range(3)]
stack = deque([(0, S)])

while stack:
    cost, v = stack.popleft()
    if dist[cost % 3][v] != INF:
        continue

    dist[cost % 3][v] = cost
    for i in graph[v]:
        stack.append((cost + 1, i))

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

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
F = [set() for _ in range(3*n)]
for _ in range(m):
  u, v = map(int, input().split())
  u = (u-1)*3
  v = (v-1)*3
  F[u].add(v+1)
  F[u+1].add(v+2)
  F[u+2].add(v)
s, t = map(int, input().split())
s = (s-1)*3
t = (t-1)*3
dist = [-1]*(3*n)
dist[s] = 0
dq = deque([s])
while dq:
  v = dq.popleft()
  for nv in F[v]:
    if dist[nv] != -1:
      continue
    dist[nv] = dist[v]+1
    dq.append(nv)
    if nv == t:
      break
  else:
    continue
  break
print(dist[t]//3)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
L = [[] for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    L[a].append(b)

# print(L)
S, T = map(int, input().split())
dist = [[10**9 for i in range(N + 1)] for j in range(3)]
dist[0][S] = 0
# print(dist)
Q = []
for i in L[S]:
    Q.append([i, S, 0])

for i in range(10 ** 7):
    if len(Q) == i:
        break
    if dist[(Q[i][2] + 1) % 3][Q[i][0]] == 10**9:
        dist[(Q[i][2] + 1) % 3][Q[i][0]] = dist[(Q[i][2]) % 3][Q[i][1]] + 1
        for j in L[Q[i][0]]:
            if dist[(Q[i][2] + 2) % 3][j] == 10**9:
                Q.append([j, Q[i][0], Q[i][2] + 1])
if dist[0][T] % 3 == 0:
    print(dist[0][T] // 3)
else:
    print(-1)
    #print(dist[0][:30])

Submission status: Accepted

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


visited = [[-1] * 3 for _ in range(N+1)]

que = deque([(S, 0, 0)])
visited[S][0] = 0

while que:
    ci, l, d = que.popleft()

    for ni, nl in G[ci][l]:
        if visited[ni][nl] == -1:
            que.append((ni, nl, d+1))
            visited[ni][nl] = d+1

print(visited[T][0]//3)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in range(N*3+1)]
    for i in range(M):
        u, v = map(int, input().split())
        u2, u3 = u+N, u+2*N
        v2, v3 = v+N, v+2*N
        edges[u].append(v2)
        edges[u2].append(v3)
        edges[u3].append(v)
    S, T = map(int, input().split())
    
    dist = [10**15 for _ in range(N*3+1)]
    dist[S] = 0
    que = [S]
    while que:
        que_tmp = []
        for parent in que:
            for child in edges[parent]:
                if dist[child] != 10**15:
                    continue
                que_tmp.append(child)
                dist[child] = dist[parent] + 1
        que = que_tmp
    
    if dist[T] != 10**15:
        print(dist[T]//3)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
l=[[] for i in range(n+1)]
lb=[[] for i in range(n+1)]
d0={}#gから逆走して3の倍数回でいけるか
d1={}
d2={}
for i in range(n):
  d1[i+1],d2[i+1],d0[i+1]=0,0,0
for i in range(m):
  a,b=map(int,input().split())
  l[a].append(b)
  lb[b].append(a)
s,t=map(int,input().split())
q0=deque([t])
q1=deque([])
q2=deque([])
bool1=True
now=0
ans=-1
while q0 or q1 or q2:
  if now%3==0:
    while q0:
      a=q0.popleft()
      d=lb[a]
      for i in d:
        if d1[i]==1:
          pass
        else:
          d1[i]=1
          q1.append(i)
  elif now%3==1:
    while q1:
      a=q1.popleft()
      d=lb[a]
      for i in d:
        if d2[i]==1:
          pass
        else:
          d2[i]=1
          q2.append(i)
  elif now%3==2:
    while q2:
      a=q2.popleft()
      d=lb[a]
      for i in d:
        if i==s and bool1:
          ans=(now+1)//3
          bool1=False
        if d0[i]==1:
          pass
        else:
          d0[i]=1
          q0.append(i)
  now=now+1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

N, M = map(int, input().split())
INF = 10**10

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

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

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

minDist = [INF] * (3 * N)
que = [(0, S)]

while que:
    dist, now = heappop(que)

    if minDist[now] <= dist:
        continue
    minDist[now] = dist

    dist += 1

    for to in edges[now]:
        if minDist[to] > dist:
            heappush(que, (dist, to))

ans = minDist[T]

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=list(map(int,input().split()))
    g[u-1].append(v-1)
S,T=map(int,input().split())
S-=1;T-=1
INF=10**9
U=[[INF]*n for i in range(3)]
U[0][S]=0
que=deque([(0,S)])
while que:
    t,v=que.popleft()
    u=(t+1)%3
    if t==2:
        U[t][v]+=1
    for w in g[v]:
        if U[u][w]!=INF:
            continue
        que.append((u,w))
        U[u][w]=U[t][v]
print(U[0][T] if U[0][T]<INF else -1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n,m=map(int,input().split())
    N=3*n
    E=[[] for _ in range(N)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[3*u].append(3*v+1)
        E[3*u+1].append(3*v+2)
        E[3*u+2].append(3*v)

    s,t=map(int,input().split())
    s-=1; t-=1
    S=3*s; T=3*t
    dist=[INF]*N
    dist[S]=0
    Q=deque([S])
    while(Q):
        v=Q.popleft()
        for nv in E[v]:
            if(dist[nv]!=INF): continue
            dist[nv]=dist[v]+1
            Q.append(nv)

    print(dist[T]//3 if(dist[T]!=INF) else -1)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter, defaultdict
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import queue
import bisect
MOD = 10**9 + 7
from logging import getLogger, StreamHandler, DEBUG, WARNING
logger = getLogger(__name__)
handler = StreamHandler()
handler.setLevel(DEBUG)
logger.setLevel(DEBUG)
# handler.setLevel(WARNING)
# logger.setLevel(WARNING)
logger.addHandler(handler)
def main():
    INF = 10 ** 7
    n, m = getList()
    kempa = [[] for i in range(3 * n)]
    costs = [INF for i in range(3 * n)]
    for _ in range(m):
        u, v = getList()
        kempa[3 * u - 3].append(3 * v - 2)
        kempa[3 * u - 2].append(3 * v - 1)
        kempa[3 * u - 1].append(3 * v - 3)

    # =================--探索===================
    s, t = getList()
    deq = deque()
    deq.append(3 * s - 3)
    costs[3 * s - 3] = 0
    while(deq):
        tmp = deq.popleft()
        tcost = costs[tmp]
        for nxt in kempa[tmp]:
            if costs[nxt] > tcost + 1:
                deq.append(nxt)
                costs[nxt] = tcost + 1
    # =================--探索===================
    # print(costs)
    if costs[t * 3 - 3] == INF:
        print(-1)
    else:
        print(costs[t * 3 - 3] // 3)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import deque

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

dic = {}

for i in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []

    dic[u].append(v)


far = [[float("inf")] * 3 for i in range(N)]
nend = [ [True] * 3 for i in range(N) ]

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

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

while len(q) > 0:

    now = q.popleft()

    nd = now[0]
    np = now[1]
    nend[np][nd % 3] = False

    far[np][nd % 3] = min(far[np][nd % 3],nd)

    if np in dic:
        for i in dic[np]:

            if nend[i][(nd + 1) % 3] and far[i][(nd+1)%3] > far[np][nd%3] + 1:
                q.append([nd + 1 , i])
                nend[i][(nd+1)%3] = False

if far[T][0] == float("inf"):
    print (-1)
else:
    print (far[T][0] // 3)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inf = float('inf')
mod = 10**9 + 7

# ダイクストラ法 計算量O(ElogV)
# [引数]: 隣接リスト, 始点
class Dijkstra:
    def __init__(self, to:list, start:int):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.dist = [inf] * self.N
        self.dist[start] = 0
        # cnt : 最短経路の数
        self.cnt = [0] * self.N
        self.cnt[start] = 1
        self.pq = [(self.dist[start], start)]

    # distを更新
    def update(self) -> None:
        while self.pq:
            _, v = heappop(self.pq)
            for nv, w in self.to[v]:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    heappush(self.pq, (self.dist[nv], nv))
                if self.dist[nv] == self.dist[v] + w:
                    self.cnt[nv] += self.cnt[v]
                    self.cnt[nv] %= mod

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

DI = Dijkstra(to, 3*S)
DI.update()

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

Submission status: Accepted

Solution code:
import sys
INF = 10 ** 9
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = [s]
flg = False
already = set()
dist = [INF for i in range(3 * n)]
dist[s] = 0
while que:
    cur= que[0]
    que.pop(0)
    for i in graph[cur]:
        if i not in already:
            if i == t:
                res = dist[cur] + 1
                que.clear()
                flg = True
                break
            que.append(i)
            dist[i] = dist[cur] + 1
            already.add(i)
if not flg:
    res = -1
else:
    res //= 3

print(res)

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):
    a,b=map(int,input().split())
    g[3*(a-1)].append(3*(b-1)+1)
    g[3*(a-1)+1].append(3*(b-1)+2)
    g[3*(a-1)+2].append(3*(b-1))
s,t=map(int,input().split())
s-=1
t-=1
s*=3
t*=3
q=deque([[s,0]])
v=[0]*(3*n)
while q:
    p=q.popleft()
    v[p[0]]=1
    for j3 in g[p[0]]:
        if j3==t:
            print((p[1]+1)//3)
            exit()
        if v[j3]==0:
            v[j3]=1
            q.append([j3,p[1]+1])
print(-1)

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    s,t=map(int,input().split())
    visit=[[False]*3 for _ in [0]*n]
    s-=1
    t-=1
    visit[s][0]=True
    cnt=0
    q=[s]
    while q:
        qq=[]
        cnt+=1
        c=cnt%3
        for i in q:
            for j in g[i]:
                if visit[j][c]==False:
                    visit[j][c]=True
                    qq.append(j)
        q=qq
        if visit[t][0]:
            print(cnt//3)
            break
    else:
        print(-1)
main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N, M = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    G[(u-1, 0)].append((v-1, 1))
    G[(u-1, 1)].append((v-1, 2))
    G[(u-1, 2)].append((v-1, 0))
S, T = map(int, input().split())
dist = defaultdict(lambda : -1)
que = deque([(S-1, 0)])
dist[(S-1, 0)] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]>=0:
            continue
        dist[nv] = d+1
        que.append(nv)
print(dist[(T-1, 0)]//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, n: int, start: int, INF: int = float('inf')) -> list:
    # graph[node] = [(cost, to)]
    dist = [INF] * n
    num = [0] * n

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        _, v_from = heappop(heap)
        for v_to in graph[v_from]:
            dist_cand = dist[v_from] + 1
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist
    # dist = [costs to nodes]


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