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: Time Limit Exceeded

Solution code:
import sys, collections

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

    graphB = [set() for i in range(N)]
    q = collections.deque()
    for i in range(N):
        q.append((0, i))
        pathi = set()
        while q:
            cost, now = q.popleft()
            if cost <= 1:
                for s in son[now]: q.append((cost+1, s))
            elif cost == 2: 
                for s in son[now]: pathi |= {s}
        graphB[i] = pathi
    
    visited = [-1] * N
    q.append((0, S-1))
    while q:
        cost, now = q.popleft()
        if visited[now] < 0:
            visited[now] = cost
            for s in graphB[now]:
                if visited[s] < 0: q.append((cost + 1, s))

    print(visited[T-1])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys, collections

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

    graphB = [set() for i in range(N)]
    for i in range(N):
        q = collections.deque()
        q.append((0, i))
        pathi = set()
        while q:
            cost, now = q.popleft()
            if cost > 3: break
            elif cost == 3:
                pathi |= {now}
                for s in son[now]: q.append((cost + 1, s))
            else:
                for s in son[now]: q.append((cost + 1, s))
        graphB[i] = pathi
    
    q = collections.deque()
    visited = [-1] * N
    q.append((0, S-1))
    while q:
        cost, now = q.popleft()
        if visited[now] < 0:
            visited[now] = cost
            for s in graphB[now]:
                if visited[s] < 0: q.append((cost + 1, s))

    print(visited[T-1])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
o=inputs()
s,T=map(int,o.pop().split())
for i in o:
    _,__=map(int,i.split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=set()
seen.add(3*s)
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if t not  in seen:
            dq.append((t,c+1))
            seen.add(t)
print("-1")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
o=inputs()
s,T=map(int,o.pop().split())
for i in o:
    _,__=map(int,i.split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=[0]*(3*n+3)
seen[3*s]=1
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if seen[t]==0:
            dq.append((t,c+1))
            seen[t]=1
print("-1")

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for _ 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

q = deque([(S, 0)])
visited = [[0]*3 for _ in range(N)]
visited[S][0] = 1

flg = True
res = -1
while q and flg:
    v = q.popleft()
    for n_v in graph[v[0]]:
        n_dist = v[1] + 1
        if n_v == T and n_dist % 3 == 0:
            res = n_dist // 3
            flg = False
            break
        if not visited[n_v][n_dist % 3]:
            visited[n_v][n_dist % 3] = 1
            q.append((n_v, n_dist))

print(res)

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N):  # 隣接リスト
    NEAR = [set() for _ in range(3 * N)]
    for a, b in uv:
        a, b = 3 * (a - 1), 3 * (b - 1)
        NEAR[a].add(b + 1)
        NEAR[a + 1].add(b + 2)
        NEAR[a + 2].add(b)
    return NEAR


def bfs(S, T, N):  # 幅優先探索  # キュー
    S, T = 3 * (S - 1), 3 * (T - 1)
    dist, flag = [-3] * (3 * N), [0] * (3 * N)  # 前処理
    dist[S], flag[S] = 0, 1
    que = deque([S])

    while que:
        q = que.popleft()
        for i in near[q]:  # 移動先の候補
            if flag[i]:  # 処理済みか否か
                continue
            dist[i], flag[i] = dist[q] + 1, 1
            que.append(i)
    return dist[T] // 3


n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

# 解説AC
near = nearlist(n)
print(bfs(s, t, n))

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N):  # 隣接リスト
    NEAR = [set() for _ in range(3 * N)]
    for a, b in uv:
        a, b = 3 * (a - 1), 3 * (b - 1)
        NEAR[a].add(b + 1)
        NEAR[a + 1].add(b + 2)
        NEAR[a + 2].add(b)
    return NEAR


def bfs(S, T, N):  # 幅優先探索  # キュー
    S, T = 3 * (S - 1), 3 * (T - 1)
    dist, flag = [-3] * (3 * N), [0] * (3 * N)  # 前処理
    dist[S], flag[S], que = 0, 1, deque([S])

    while que:
        q = que.popleft()
        for i in near[q]:  # 移動先の候補
            if flag[i]:  # 処理済みか否か
                continue
            dist[i] = dist[q] + 1
            flag[i] = 1
            que.append(i)
    return dist[T] // 3


n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

# 解説AC
near = nearlist(n)
ans = bfs(s, t, n)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [set() for _ in range(3 * N)]
    for a, b in LIST:
        a, b = 3 * (a - 1), 3 * (b - 1)
        NEAR[a].add(b + 1)
        NEAR[a + 1].add(b + 2)
        NEAR[a + 2].add(b)
    return NEAR


def bfs(S, T, N):  # 幅優先探索  # キュー
    S, T = 3 * (S - 1), 3 * (T - 1)
    dist, flag = [-3] * (3 * N), [0] * (3 * N)  # 前処理
    dist[S], flag[S], que = 0, 1, deque([S])

    while que:
        q = que.popleft()
        for i in near[q]:  # 移動先の候補
            if flag[i]:  # 処理済みか否か
                continue
            dist[i] = dist[q] + 1
            flag[i] = 1
            que.append(i)
    return dist[T] // 3


n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

# 解説AC
near = nearlist(n, uv)
ans = bfs(s, t, n)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [set() for _ in range(3 * N)]
    for a, b in LIST:
        a, b = 3 * (a - 1), 3 * (b - 1)
        NEAR[a].add(b + 1)
        NEAR[a + 1].add(b + 2)
        NEAR[a + 2].add(b)
    return NEAR


def bfs(S, T, N):  # 幅優先探索  # キュー
    S, T = 3 * (S - 1), 3 * (T - 1)
    dist = [-3] * (3 * N)  # 前処理
    dist[S] = 0
    que, flag = deque([S]), set([S])

    while que:
        q = que.popleft()
        for i in near[q]:  # 移動先の候補
            if i in flag:  # 処理済みか否か
                continue
            dist[i] = dist[q] + 1
            que.append(i), flag.add(i)
    return dist[T] // 3


n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

# 解説AC
near = nearlist(n, uv)
ans = bfs(s, t, n)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def main():

  n,m=map(int,input().split())
  INF=10**9
  d=[[INF]*3 for i in range(n)]
  to=[[] for i in range(n)]
  for i in range(m):
    u,v=map(lambda x:int(x)-1,input().split())
    to[u].append(v)
  s,t=map(lambda x:int(x)-1,input().split())

  #print(to)
  # calc d (after 3 times dist)
  d[s][0]=0
  cnt=0
  q=deque([(s,cnt)])
  while q:
    u,c=q.popleft()
    for v in to[u]:
      nc=(c+1)%3
      if d[v][nc]!=INF: continue;
      d[v][nc]=d[u][c]+1
      q.append((v,nc))
      
  #print(d)
  ans=d[t][0]
  print(ans//3 if ans!=INF else -1)

  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v)

s, t = map(int, input().split())
s -= 1
t -= 1
#dfs
from_s = [[-1]*3 for _ in range(n)]
d_s = deque()
d_s.append((s, 0))
from_s[s][0] = 0
while d_s:
    p, count = d_s.popleft()
    next_count = (count + 1) % 3
    for c in edges[p]:
        if from_s[c][next_count] != -1:
            continue
        from_s[c][next_count] = from_s[p][count] + 1
        d_s.append((c, next_count))
if from_s[t] == -1:
    print(-1)
else:
    print(from_s[t][0]//3)

Submission status: Accepted

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

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

from collections import deque

q = deque([(S, 0)])
v = [[-1] * 3 for i in range(N+1)]

while q:
    a, t = q.popleft()
    b = t % 3
    if v[a][b] != -1:
        continue
    v[a][b] = t
    t += 1
    for x in to[a]:
        q.append((x, t))
    #print(q)


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

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(N, M, G, S, T):
    INF = 10**10
    q = deque([S])
    dist = [INF] * (3 * N)
    dist[S] = 0
    while q:
        v = q.popleft()
        for to in G[v]:
            if dist[to] < INF: continue
            dist[to] = dist[v] + 1
            q.append(to)
    print(dist[T] // 3 if dist[T] < INF else -1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N * 3)]
    for _ 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 + N + N)
        G[x + N + N].append(y)
    S, T = map(lambda x: int(x) - 1, input().split())
    main(N, M, G, S, T)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(N, M, G, S, T):
    INF = 10**10
    dp = [[INF for _ in range(N)] for __ in range(3)]
    dp[0][S] = 0
    q = [(0, S)]
    while q:
        d, v = heappop(q)
        for to in G[v]:
            if d + 1 >= dp[(d + 1) % 3][to]: continue
            dp[(d + 1) % 3][to] = d + 1
            heappush(q, (d + 1, to))
    print(dp[0][T] // 3 if dp[0][T] < INF else -1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1
        G[x].append(y)
    S, T = map(lambda x: int(x) - 1, input().split())
    main(N, M, G, S, T)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(N, M, G, S, T):
    INF = 10**10
    dp = [[INF for _ in range(N)] for __ in range(3)]
    dp[0][S] = 0
    q = [(0, S)]
    while q:
        d, v = heappop(q)
        for to in G[v]:
            if d + 1 >= dp[(d + 1) % 3][to]: continue
            dp[(d + 1) % 3][to] = d + 1
            q.append((d + 1, to))
    print(dp[0][T] // 3 if dp[0][T] < INF else -1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1
        G[x].append(y)
    S, T = map(lambda x: int(x) - 1, input().split())
    main(N, M, G, S, T)

Submission status: Accepted

Solution code:
# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]

for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
S=(S,0)
T=(T,0)

q=deque()
q.append(S)
F=set()
res=-1
while q:
    node,r=q.popleft()
    if (node,r%3) in F:
        continue
    if (node,r%3) == T:
        res=r//3
        break
    F.add((node,r%3))
    for next_node in G[node]:
        if (next_node,(r+1)%3) in F:
            continue
        q.append((next_node,r+1))
print(res)

Submission status: Accepted

Solution code:
import sys
import heapq
import math

input = sys.stdin.readline
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(3*N)]
for a, b in uv:
    g[a-1].append(b-1+N)
    g[a-1+N].append(b-1+2*N)
    g[a - 1 + 2 * N].append(b - 1)

# bfsでよかった
hq = [(0, S-1)]
costs = [math.inf] * 3 * N
while len(hq) > 0:
    c, u = heapq.heappop(hq)
    if u == T - 1:
        print(c // 3)
        sys.exit()
    costs[u] = c
    for v in g[u]:
        if costs[v] > c+1:
            heapq.heappush(hq, (c + 1, v))
        costs[v] = min(costs[v], c+1)

print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#E - Hopscotch Addict
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M = map(int, readline().split())
graph = [[] for _ in range(3*N+1)]
for _ in range(M):
    x,y = map(int,readline().split())
    graph[x].append(y+N)
    graph[x+N].append(y+2*N)
    graph[x+2*N].append(y)
S,G = map(int,readline().split())
dist = [-1]*(N*3+1)
dist[S] = 0
root = S
q = deque([root])

def bfs(q):
    while q:
        x = q.popleft()
        for nx in graph[x]:
            if dist[nx] != -1:
                continue
            dist[nx] = dist[x] + 1
            q.append(nx)
            
bfs(q)
if dist[G] == -1:
    print(-1)
else:
    print(dist[G] // 3)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#E - Hopscotch Addict
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M = map(int, readline().split())
graph = [[[] for _ in range(3)] for _ in range(N+1)]
for i in range(M):
    x,y = map(int,readline().split())
    graph[x][0].append((y,1))
    graph[x][1].append((y,2))
    graph[x][2].append((y,0))
S,G = map(int,readline().split())
dist = [[-1]*3 for _ in range(N+1)]
dist[S][0] = 0
root = (S,0)

q = deque([root])
def bfs(q):
    while q:
        x,t = q.popleft()
        for nx,nt in graph[x][t]:
            if dist[nx][nt] != -1:
                continue
            dist[nx][nt] = dist[x][t] + 1
            q.append((nx,nt))
            
bfs(q)
if dist[G][0] == -1:
    print(-1)
else:
    print(dist[G][0] // 3)

Submission status: Accepted

Solution code:
from collections import deque
INF = float("inf")

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

# i + 0*N -> (3の倍数)回で移動できるi
# i + 1*N -> (3の倍数+1)回で移動できるi
# i + 2*N -> (3の倍数+2)回で移動できるi

# 有向グラフなので、u -> vのみ （v -> u は通れない）
G = [[] for _ in range(3 * N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = 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, T = S - 1, T - 1

ans = [INF] * (3 * N)
ans[S] = 0
dq = deque([S])

# BFS
while dq:
    now = dq.popleft()
    for next in G[now]:
        if ans[next] != INF:
            continue
        ans[next] = ans[now] + 1
        dq.append(next)

# 3の倍数回で移動できる、Tへの最短距離 = ans[T + 0*N]
if ans[T] != INF:
    print(ans[T] // 3)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


INF = 10**18


def bfs(N, v0, goal, edge):

    dp = [[-1 for _ in range(3)] for _ in range(N)]
    dp[v0][0] = 0
    q = deque()
    q.append((v0, 0))

    while q:
        v, cnt = q.popleft()

        if cnt == 2:
            nx_cnt = 0
        else:
            nx_cnt = cnt + 1

        for nv in edge[v]:
            if dp[nv][nx_cnt] == -1:
                q.append((nv, nx_cnt))
                if cnt == 0:
                    dp[nv][nx_cnt] = dp[v][cnt] + 1
                else:
                    dp[nv][nx_cnt] = dp[v][cnt]
        # print(v, dp)

    return dp[goal][0]


def main():

    N, M = in_nn()
    edge = [[] for _ in range(N)]

    for i in range(M):
        u, v = in_nn()
        u, v = u - 1, v - 1
        edge[u].append(v)

    S, T = in_nn()
    S, T = S - 1, T - 1
    ans = bfs(N, S, T, edge)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
import queue

N, M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
adj = [[] for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())    
    u -= 1
    v -= 1
    adj[u].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1

dist = [[INF,INF,INF] for _ in range(N+1)]
 
q = queue.Queue()
q.put((S, 0))
dist[S][0] = 0
while not q.empty():
    u, l = q.get()
    for v in adj[u]:
        nl = (l + 1) % 3
        if dist[v][nl] != INF:
            continue
        dist[v][nl] = dist[u][l] + 1
        q.put((v, nl))
d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
import queue

N, M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
adj = [[] for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())    
    u -= 1
    v -= 1
    adj[u].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1

dist = [[INF,INF,INF] for _ in range(N+1)]
 
d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in adj[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq
 
d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)

Submission status: Accepted

Solution code:
from collections import deque
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())

dist = [[-3] * 3 for _ in range(n+1)]
dist[s][0] = 0

q = deque([(s, 0)])

while q:
    now, c = q.popleft()
    ne = (c+1) % 3
    for node in graph[now]:
        if dist[node][ne] != -3:
            continue
        dist[node][ne] = dist[now][c] + 1
        q.append((node, ne))

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

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
n,m = ma()
G = [[]for i in range(3*n)]
for i in range(m):
    u,v = ma();u-=1;v-=1
    G[3*u].append(3*v+1)
    G[3*u+1].append(3*v+2)
    G[3*u+2].append(3*v)
s,t = ma()
s=(s-1)*3
t=(t-1)*3
visited=[False]*(3*n)
INF=10**9
dist = [INF]*(3*n)
que = collections.deque()
que.append(s)
visited[s]=True
dist[s]=0
while que:
    prev = que.popleft()
    for nex in G[prev]:
        if not visited[nex]:
            visited[nex]=True
            dist[nex]=dist[prev]+1
            que.append(nex)
if dist[t]==INF:
    print(-1)
else:
    print(dist[t]//3)

Submission status: Accepted

Solution code:
"""
これは、3の倍数かつ最小ステップでTにたどりつけ、という問題。
拡張ダイクストラを使えばよい。
"""
from collections import deque
N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split())
    edges[u].append(v)
visited = set()
S,T = map(int,input().split())
que = deque([(S,0)])
while que:
    cur,step = que.popleft()
    rest = step%3
    if cur == T and rest == 0:
        print(step//3)
        exit()
    if (cur,rest) in visited:
        continue
    else:
        visited.add((cur,rest))
        for nx in edges[cur]:
            que.append((nx,step+1))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
w = [set() for _ in range(n + 1)]
for _ in range(m):
  u, v = map(int, input().split())
  w[u].add(v)
s, t = map(int, input().split())

memo = [[-1,-1,-1] for _ in range(n+1)]

d = deque()
d.append((s,0,0))
while d:
    i,q,r = d.popleft()
    for nx in w[i]:
        if nx ==t and r ==2:
            print((q+1)//3)
            exit()
        if memo[nx][(r+1)%3] == -1:
            memo[nx][(r+1)%3] = q+1
            d.append((nx,q+1,(r+1)%3))
print(-1)

Submission status: Accepted

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

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

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

while q:
  v,cost,step = q.popleft()
  if seen[v][step]:
    continue
  seen[v][step] = True
  if step == 0:
    if v == T:
      print(cost)
      break
    cost += 1
    step = 3
  for u in graph[v]:
    q.append([u, cost, step - 1])
else:
  print(-1)

Submission status: Accepted

Solution code:
import collections

n, m = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
flag = [False for i in range(n + 1)]
s, t = map(int, input().split())

queue = collections.deque([s])
count = 0
while True:
    for i in range(2):
        temp = set()
        while queue:
            test = queue.popleft()
            for j in graph[test]:
                if j not in temp:
                    temp.add(j)
        for j in temp:
            queue.append(j)
    temp = set()
    while queue:
        test = queue.popleft()
        for i in graph[test]:
            if flag[i] == True:
                continue
            else:
                if i not in temp:
                    temp.add(i)
                    flag[i] = True
    count += 1
    if flag[t] == True:
        print(count)
        break
    if len(temp) == 0:
        print(-1)
        break
    for i in temp:
        queue.append(i)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 双方向グラフで幅優先探索

from collections import deque

n, m = map(int, input().split())
g = [set([]) for _ in range(n)]
#隣接リストの作成
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].add(b)

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

#幅優先探索
q = deque()
level = [[-1]*n for i in range(3)]
q.append((s, 0))
level[0][s] = 0
while len(q)>0:
    cur, lvl = q.popleft()
    nxtl = lvl + 1
    nxthp = nxtl%3
    for i in g[cur]:
        if level[nxthp][i]==-1:
            #階層
            level[nxthp][i] = nxtl
            q.append((i, nxtl))
print(level[0][t]//3)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 双方向グラフで幅優先探索

from collections import deque

n, m = map(int, input().split())
g = [set([]) for _ in range(n)]
#隣接リストの作成
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].add(b)

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

#幅優先探索
q = deque()
level = [[-1]*n for i in range(3)]
q.append((s, 0))
level[0][s] = 0
while len(q)>0:
    cur, hp = q.popleft()
    lvl = level[hp][cur]
    for i in g[cur]:
        if level[(hp+1)%3][i]==-1:
            #階層
            level[(hp+1)%3][i] = lvl + 1
            q.append((i, (hp+1)%3))
print(level[0][t]//3)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
w = [set() for _ in range(n + 1)]
for _ in range(m):
  u, v = map(int, input().split())
  w[u].add(v)
s, t = map(int, input().split())
l = [[-1, -1, -1] for _ in range(n + 1)] # 頂点までの最短移動回数（余りごとに３つ）

d = deque()
d.append((s, 0, 0))
while d: # qが小さい順に制御されている
  i, q, r = d.popleft() # 頂点番号、商、余り
  for _w in w[i]:
    if _w == t and r == 2: # 終了条件
      print((q + 1) // 3)
      exit()
    if l[_w][(r + 1) % 3] == -1: # 余り考慮での初到達時に、メモとTODO追加
      l[_w][(r + 1) % 3] = q + 1
      d.append((_w, q + 1, (r + 1) % 3))
print(-1)

Submission status: Accepted

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

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

from collections import deque
q = deque([S])
INF = float('inf')
dist = [INF] * (N*3)
dist[S] = 0
while q:
    v = q.popleft()
    for to in es[v]:
        if dist[to] <= dist[v]+1: continue
        dist[to] = dist[v]+1
        q.append(to)
        if to==T:
            print(dist[to] // 3)
            exit()
print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readlines
from collections import deque
def main():
    lines = input()
    n, m = list(map(int, lines[0].split()))
    #隣接リスト
    edges=[[] for i in range(n)]
    for i in range(m):
        u,v=list(map(int,lines[i+1].split()))
        edges[u-1].append(v-1)

    s,t=list(map(int,lines[m+1].split()))
    inf=100000000000
    score=[[inf]*3 for i in range(n)]
    now=deque()
    now.append((s-1, 0))
    score[s-1][0]=0
    def bfs():
        if now:
            u, mod = now.popleft()
            time = score[u][mod]
            mod = (mod+1)%3
            for v in edges[u]:
                if score[v][mod] == inf:
                    score[v][mod] = time+1
                    now.append((v, mod))

            bfs()

    bfs()
    ans = score[t-1][0]
    if ans == inf:
        print(-1)
    else:
        print(score[t-1][0]//3)
main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.buffer.readline
int1 = lambda x: int(x) - 1

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

S, T = map(int1, input().split())
S *= 3
T *= 3

# bfs
d = deque([S])
distance = [0] * (3 * N)
while d:
    v = d.popleft()
    dist_v = distance[v]
    if v == T:
        print(dist_v // 3)
        exit()
    for x in G[v]:
        if not distance[x]:
            d.append(x)
            distance[x] = dist_v + 1
print(-1)

Submission status: Accepted

Solution code:
from collections import*
n,m=map(int,input().split())
e=[[]for _ in range(3*(n+1))]
d=[-3]*(3*(n+1))
for _ in range(m):
  a,b=map(int,input().split())
  e[a]+=[b+n]
  e[a+n]+=[b+2*n]
  e[a+2*n]+=[b]
s,t=map(int,input().split())
q=deque([s])
d[s]=0
while q:
  now=q.popleft()
  for to in e[now]:
    if d[to]!=-3:continue
    d[to]=d[now]+1
    q.append(to)
print(d[t]//3)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_d(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


def main():
    N, M = NMI()
    edges = [NLI() for _ in range(M)]
    S, T = NMI()

    tree = [[] for _ in range(3*N+1)]
    for e in edges:
        tree[e[0]].append(e[1]+N)
        tree[e[0]+N].append(e[1]+2*N)
        tree[e[0]+2*N].append(e[1])

    stack = deque()
    stack.append(S)
    seen = [-1] * (3*N+1)
    seen[S] = 0
    while stack:
        now = stack.popleft()
        now_step = seen[now]
        for goto in tree[now]:
            if seen[goto] >= 0:
                continue

            stack.append(goto)
            seen[goto] = now_step + 1

    print(seen[T]//3)



if __name__ == "__main__":
    main()