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
from collections import deque

sys.setrecursionlimit(10000000)

n,m = map(int,input().split())
to=[[] for _ in range(n)]
dist=[[0] *3 for _ in range(100005)]
INF=10**15

for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    to[a].append(b)

sv,tv=map(int,input().split())
sv-=1;tv-=1

for i in range(n):
    for j in range(3):
        dist[i][j] =INF

q=deque()
q.append((sv,0))
dist[sv][0]=0

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

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
G=[[] for i in range(3*n)]
for i in range(m):
  u,v=map(int,input().split())
  for j in range(3):
    G[u+n*j-1].append(v+n*((j+1)%3)-1)
s,g=map(int,input().split())
s=s-1
g=g-1
D=deque([s])
V=[0]*3*n
V[s]=1
DD=[0]*3*n
while len(D)>0:
  x=D[0]
  D.popleft()
  for y in G[x]:
    if V[y]==0:
      V[y]=1
      D.append(y)
      DD[y]=DD[x]+1
if DD[g]==0:
  print(-1)
else:
  print(DD[g]//3)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



def main():
    #距離が3の倍数である経路のうち最短である経路が存在するかどうかを調べる
    #存在するときその経路の距離を3で割った商が答え
    #存在しないとき-1を出力する

    #経路の距離を3で割った余りで頂点の状態を分類する

    #与えられたグラグをGとする
    #Gの辺の張っている隣接頂点u,vを考える
    #Gは有効グラフであるからu->vの様に辺が張っているとする
    #次のようにグラフGの頂点拡張する
    #(u, r) := uへたどり着く最短経路を3で割ったときr余る状態（状態を頂点とした新たなグラフG'を考えることになる）
    #辺の重みは1であるので(u, 0)->(v, 1), (u, 1)->(v, 2), (u, 2) -> (v, 0)の状態遷移が考えられる
    #（例：余り0から1移動すれば経路は1伸びるから全経路を3で割った余りは1となる）

    #(S, 0) -> ... ->(T, 0)となる最短経路が「距離が3の倍数である経路のうち最短である経路」である

    N, M = map(int, readline().split())
    to = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, readline().split())
        u-=1
        v-=1
        to[u].append(v)
    S, T = map(int, readline().split())
    S-=1
    T-=1

    INF = int(1e9)
    #距離を3で割った余りで分類して状態の遷移を考える
    dist = [[INF for _ in range(3)] for _ in range(N)]     

    #BFS
    from collections import deque
    dq = deque()
    dq.append((S, 0))
    dist[S][0] = 0
    while len(dq)>0:
        v, r = dq.popleft() 
        for nxv in to[v]:
            nxr = (r+1)%3
            if dist[nxv][nxr] != INF:
                continue
            dist[nxv][nxr] = dist[v][r] + 1
            dq.append((nxv, nxr))

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

Submission status: Accepted

Solution code:
from collections import deque

N,M,*f = map(int, open(0).read().split())
uv = [f[i:i+2] for i in range(0, len(f)-2, 2)]
S = f[-2]
T = f[-1]
connected = [[] for _ in range(N+1)]
for u, v in uv:
    connected[u].append(v)
dist = [[-1] * 3 for _ in range(N+1)]
dist[S][0] = 0
ans = 0
d = deque([(S,0)])
while d:
    temp = d.popleft()
    for edge in connected[temp[0]]:
        if edge == T and temp[1] == 2:
            print((dist[temp[0]][2]+1)//3)
            break
        else:
            if dist[edge][(temp[1]+1)%3] < 0:
                dist[edge][(temp[1]+1)%3] = dist[temp[0]][temp[1]] + 1
                d.append((edge,(temp[1]+1)%3))
    else:
        continue
    break
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()
adj = [list() for _ in range(N)]
for _ in range(M):
    u, v = map(lambda s: int(s) - 1, sys.stdin.readline().split())
    adj[u].append(v)
S, T = map(lambda s: int(s) - 1, sys.stdin.readline().split())

q = deque([(0, S, 0)])
seen = {S}
while len(q) > 0:
    dim, v, cnt = q.popleft()
    if v == T and dim == 0:
        print(cnt // 3)
        exit(0)
    ndim = (dim + 1) % 3
    for nxt in adj[v]:
        if (ndim * N + nxt) not in seen:
            q.append((ndim, nxt, cnt + 1))
            seen.add(ndim * N + nxt)
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(G,s,N):
    dist=[[-1]*N for i in range(3)]
    d=deque()
    dist[0][s]=0
    d.append((0,s))
    while(len(d)!=0):
        p,v=d.popleft()
        for np,nv in G[p][v]:
            if(dist[np][nv]!=-1):
                continue
            dist[np][nv]=dist[p][v]+1
            d.append((np,nv))
    return dist

N,M=map(int,input().split())
G=[[[] for i in range(N)] for i in range(3)]
for i in range(M):
    u,v=map(lambda x:int(x)-1,input().split())
    G[0][u].append((1,v))
    G[1][u].append((2,v))
    G[2][u].append((0,v))
S,T=map(lambda x:int(x)-1,input().split())
dist=bfs(G,S,N)
ans=dist[0][T]
print(ans//3 if ans!=-1 else ans)

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

graph = [[] for _ in range(n)]
for v in uv:
    graph[v[0]-1].append(v[1]-1)
# print(graph)
s-=1
t-=1

is_checked=[[0]*3 for _ in range(n)]
is_checked[s][0]=1

ans=-1

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

while q:
    v, cnt=q.popleft()
    if v==t and cnt%3==0:
        ans=cnt//3
        break
    for i in graph[v]:
        if is_checked[i][(cnt+1)%3]==0:
            q.append([i, cnt+1])
            is_checked[i][(cnt+1)%3]=1
# print(is_checked)
print(ans)

Submission status: Accepted

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

N = 3 * (n + 1)
adj = [[] for _ in range(N)]
for u, v in uv:
    for i in range(3):
        uu = u + i * n
        vv = v + ((i + 1) % 3) * n
        adj[uu].append(vv)

dq = deque([s])
d = [-1] * N
d[s] = 0
while dq:
    u = dq.popleft()
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            dq.append(v)

ans = d[t] // 3
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(start, goal, g, n, visited):
    visited1 = [False]*(n+1)
    visited2 = [False]*(n+1)
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        if curr_node == goal: 
            return
        for next1_node in g[curr_node]:
            if visited1[next1_node]: continue
            visited1[next1_node] = True
            for next2_node in g[next1_node]:
                if visited2[next2_node]: continue
                visited2[next2_node] = True
                for next3_node in g[next2_node]:
                    if visited[next3_node] >= 0: continue
                    visited[next3_node] = visited[curr_node] + 1
                    q.append(next3_node)



def main():
    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())
    

    visited = [-1]*(n+1)
    visited[0] = 0

    bfs(s, t, g, n, visited)
    print(visited[t])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# vertexごとに3つの状態数を持つ
N, M = lr()
graph = [[] for _ in range((N+1)*3)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            #print(graph[prev],dist[next],next)
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# vertexごとに3つの状態数を持つ
N, M = lr()
graph = [[] for _ in range((N+1)*3)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for i in graph[prev]:
            #print(graph[prev],dist[next],next)
            d1 = d + 1
            if dist[i] > d1:
                dist[i] = d1
                heappush(que, (d1, i))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# vertexごとに3つの状態数を持つ
N, M = lr()
graph = [[] for _ in range((N+1)*3)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
u=[]
v=[]
g=[[] for _ in range(n)]

for i in range(m):
    uu,vv=map(int,input().split())
    u.append(uu)
    v.append(vv)
    g[uu-1].append(vv-1)
    
s,t=map(int,input().split())
s-=1
t-=1

from collections import deque
 
def bfs(u):
    queue1 = deque([u])
    queue2 = deque([0])
    d=[]
    for i in range(n):
        d.append([-1]*3)
    d[u][0]=0
    while queue1:
        v=queue1.popleft()
        l=queue2.popleft()
        nl=(l+1)%3
        for i in g[v]:
            if d[i][nl] is -1:
                d[i][nl]=d[v][l]+1
                queue1.append(i)
                queue2.append(nl)
    return d

d=bfs(s)

ans=int(d[t][0]/3)
if d[t][0]==-1:
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
if m==0:
    print(-1)
    exit()
es = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    es[u].append(v)
s,t = map(int,input().split())

INF = 10**9
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 es[u]:
            if dist[v][r] == INF:
                dist[v][r] = d
                qq.append(v)
    q = qq

d = dist[t][0]
print(-1 if d==INF else d//3)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        g[u - 1].append(v - 1)
    s, t = map(int, input().split())

    q = deque()
    q.append(s - 1)
    seen = [[-1 for _ in range(3)] for _ in range(n)]
    seen[s - 1][2] = 0

    while q:
        u = q.popleft()

        for v in g[u]:
            for i in range(3):
                if seen[u][i] != -1 and seen[v][(i + 1) % 3] == -1:
                    seen[v][(i + 1) % 3] = seen[u][i] + 1
                    q.append(v)
                    if seen[t - 1][2] != -1:
                        print(seen[t - 1][2] // 3)
                        exit()
    print(-1)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

queue = deque()
queue.append(s)
queue.append(1)
queue.append(0)
check = [[False for _ in range(3)] for _ in range(n)]
check[s][0] = True

while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    kkp = queue.popleft()
    for next_pos in uv[pos]:
        if next_pos == t and kkp == 2:
            print(ans // 3)
            exit()
        if check[next_pos][(kkp + 1) % 3]:
            continue
        check[next_pos][(kkp + 1) % 3] = True
        queue.append(next_pos)
        queue.append(ans + 1)
        queue.append((kkp + 1) % 3)
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s, t):
    dist = [-1] * (3 * n + 1)
    q = deque()
    q.append(s)
    dist[s] = 0
    while q:
        p = q.popleft()
        for i in G[p]:
            if dist[i] == -1:
                dist[i] = dist[p] + 1
                q.append(i)
    return dist[t]

n, m = map(int, input().split())
G = [[] for _ in range(3 * n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    G[u].append(v + n)
    G[u + n].append(v + 2 * n)
    G[u + 2 * n].append(v)
s, t = map(int, input().split())
ans = bfs(s, t)
print(ans // 3 if not ans == -1 else ans)

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

import heapq
from collections import defaultdict
g1 = defaultdict(set)
for u, v in uv:
    g1[u-1].add(v-1)

s -= 1
t -= 1

dist = [[float('inf')] * 3 for _ in range(n)]
dist[s][0] = 0

q = [(0, s, 0)] # (dist, pos, kenken)
heapq.heapify(q)

while q:
    du, u, c = heapq.heappop(q)
    if dist[u][c] < du:
        continue
    c2 = (c + 1) % 3
    for v in g1[u]:
        if du + 1 < dist[v][c2]:
            dist[v][c2] = du + 1
            heapq.heappush(q, (dist[v][c2], v, c2))

if dist[t][0] != float('inf'):
    print(dist[t][0] // 3)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

def read_tuple():
    return map(int, input().split())


N, M = read_tuple()
E = [[] for i in range(N+1)]
for i in range(M):
    u, v = read_tuple()
    E[u].append(v)
S, T = read_tuple()

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

Q = deque([(S,0)])
while len(Q):
    v, c = Q.popleft()
    for u in E[v]:
        k = (c + 1) % 3
        if dst[u][k] == -1:
            dst[u][k] = c + 1
            Q.append((u, c + 1))

print(dst[T][0] // 3 if dst[T][0] != -1 else -1)

Submission status: Accepted

Solution code:
def solve():
  N, M = map(int, input().split(' '))
  G = [[] for _ in range(N + 10)]
  dist = [[-1 for _ in range(3)] for _ in range(N + 10)]
  for _ in range(M):
    u, v = map(int, input().split(' '))
    G[u].append(v)
  S, T = map(int, input().split(' '))
  que = [[S, 0]]
  dist[S][0] = 0
  while que:
    q = que.pop(0)
    nv, np = q[0], q[1]
    for item in G[nv]:
      if dist[item][(np + 1) % 3] == -1:
        que.append([item, (np + 1) % 3])
        dist[item][(np + 1) % 3] = dist[nv][np] + 1
  if dist[T][0] == -1:
    return -1
  else:
    return dist[T][0] // 3
print(solve())

Submission status: Accepted

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

INF = 10 ** 18

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def dijkstra(n, G, s):
    dist = [[INF, INF, INF] for _ in range(n)]
    dist[s][0] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v][d%3] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            tmp = dist[v][d%3] + e.cost
            if dist[e.end][tmp%3] > tmp:
                dist[e.end][tmp%3] = tmp
                heapq.heappush(h, (dist[e.end][tmp%3], e.end))
    return dist

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

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

dist = dijkstra(n, g, s-1)
ans = dist[t-1][0]

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
path = [[[],[],[]] for i in range(n)]

gone = [[0]*3 for i in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    path[u-1][0].append([v-1,1])
    path[u-1][1].append([v-1,2])
    path[u-1][2].append([v-1,0])

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

now = [[s-1,0]]
gone[s-1][0] = 1
for ans in range(1,1000000):
    next = []
    for point,key in now:
        for go,gokey in path[point][key]:
            if go == t-1 and gokey == 0:
                print(ans//3)
                exit()
            if gone[go][gokey] == 0:
                gone[go][gokey] = 1
                next.append([go,gokey])
    now = next
  #     print(now)
print(-1)

Submission status: Accepted

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

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

cnt = 0
phase = 0
q = [s]
visited = [[False] * 3 for _ in range(n)]
while q:
    nextq = []
    for v in q:
        if visited[v][phase]:
            continue
        visited[v][phase] = True
        if v == t and phase == 0:
            print(cnt)
            exit()
        nextq += to[v]
    if phase == 0:
        cnt += 1
    phase = (phase + 1) % 3
    q = nextq
print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n*3)]
    for i in range(m):
        a,b=map(lambda x:int(x)-1,readline().split())
        for j in range(3):
            G[3*a+j].append(3*b+(j+1)%3)

    s,t=map(lambda x:int(x)-1,readline().split())
    s*=3
    t*=3
    #bfs
    d=deque([s])
    flags=[-1]*(3*n)
    flags[s]=0
    while len(d)>0:
        now=d.popleft()
        for nex in G[now]:
            if flags[nex]==-1:
                flags[nex]=flags[now]+1
                d.append(nex)

    print(flags[t]//3)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n*3)]
    for i in range(m):
        a,b=map(lambda x:int(x)-1,readline().split())
        for j in range(3):
            G[3*a+j].append(3*b+(j+1)%3)

    s,t=map(lambda x:int(x)-1,readline().split())
    s*=3
    t*=3
    #bfs
    d=deque([s])
    flags=[-1]*(3*n)
    flags[s]=0
    while len(d)>0:
        now=d.popleft()
        for nex in G[now]:
            if flags[nex]==-1:
                flags[nex]=flags[now]+1
                d.append(nex)

    print(flags[t]//3)

if __name__=="__main__":
    main()

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    edge = [[] * N for _ in range(N)]
    new_edge = [[] * N for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        
    S, T = map(int, input().split())
    S -= 1
    T -= 1
    d = [[float('inf')] * 3 for _ in range(N)]
    q = deque([])
    q.append((S,0))
    d[S][0] = 0
    while q:
        v,l = q.popleft()
        nl = (l + 1) % 3
        for nv in edge[v]:
            if d[nv][nl] != float('inf'):
                continue
            q.append((nv,nl))
            d[nv][nl] = d[v][l] + 1
    if d[T][0] == float('inf'):
        print(-1)
    else:
        print(d[T][0] // 3)
            



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
S,T=map(int,input().split())
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=[]
q.append([s,0])
while q:
    v,c=q.pop(0)
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]=1
print(ans)

Submission status: Accepted

Solution code:
import collections
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
S,T=map(int,input().split())
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=collections.deque()
q.append([s,0])
while q:
    v,c=q.popleft()
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]=1
print(ans)

Submission status: Accepted

Solution code:
#Hopscotch Addict

N,M=map(int,input().split())
graph={(i,j):[] for i in range(1,N+1) for j in range(1,4)}
for _ in range(M):
    u,v=map(int,input().split())
    graph[(u,1)].append((v,2))
    graph[(u,2)].append((v,3))
    graph[(u,3)].append((v,1))
S,T=map(int,input().split())

import heapq
def dijkstra(s,graph):
    dist={(i,j):float("inf") for i in range(1,N+1) for j in range(1,4)}
    dist[(s,3)]=0
    pq=[]
    heapq.heapify(pq)
    heapq.heappush(pq,(0,(s,3)))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for next_node in graph[node]:
            newlen=dist[node]+1
            if newlen<dist[next_node]:
                heapq.heappush(pq,(newlen,next_node))
                dist[next_node]=newlen
    return dist
K=dijkstra(S,graph)[(T,3)]
if K==float("inf"):
    print(-1)
else:
    print(K//3)

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(3*N)]
for _ in range(M):
  u, v = map(lambda x:int(x)-1, input().split())
  graph[3*u+0] += [[3*v+1, 1]]
  graph[3*u+1] += [[3*v+2, 1]]
  graph[3*u+2] += [[3*v+0, 1]]

def dijkstra(s):
  dist = [float('inf')]*(3*N)
  dist[s] = 0
  num = [0]*(3*N)
  num[s] = 1
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        num[v] = num[u]
        heapq.heappush(q, [dist[v], v])
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num

S, T = map(lambda x:int(x)-1, input().split())
dist, _ = dijkstra(3*S)

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**6
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()
    root = [[] for _ in range(N)]
    node = [[INF,INF,INF] for _ in range(N)]
    for _ in range(M):
        a,b = LI()
        root[a-1].append(b-1)
    S,T = LI()
    S -= 1; T -= 1
    q = collections.deque()
    q.append((S,0,0))
    node[S][0] = 0
    while q:
        v,n,d = q.popleft()
        t = (n+1) % 3
        for u in root[v]:
            if node[u][t] > d+1:
                node[u][t] = d+1
                q.append((u,t,d+1))
    if node[T][0] < INF:
        print(node[T][0]//3)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  roads0 = [[] for _ in range(n)]
  roads1 = [[] for _ in range(n)]
  roads2 = [[] for _ in range(n)]
  
  for i in range(m):
    u, v = map(int, input().split())
    roads0[u-1].append(v-1)
    roads1[u-1].append(v-1)
    roads2[u-1].append(v-1)
  

  s, t = map(int, input().split())
  not_yet = deque([])
  already = [[False]*3 for _ in range(n)]
  dist = [[0]*3 for _ in range(n)]
  for v in roads0[s-1]:
    not_yet.append((v, 1))
    dist[v][1] = 1
    already[v][1] = True
  already[s-1][0] = True
  while not_yet:
    key = not_yet.popleft()
    k1, k2 = key[0], key[1]
    if k2 == 0:
      for v in roads1[k1]:
        if already[v][1]:
          continue
        dist[v][1] = dist[k1][0]+1
        already[v][1] = True
        not_yet.append((v, 1))
    elif k2 == 1:
      for v in roads2[k1]:
        if already[v][2]:
          continue
        dist[v][2] = dist[k1][1]+1
        already[v][2] = True
        not_yet.append((v, 2))
    else:
      for v in roads0[k1]:
        if already[v][0]:
          continue
        dist[v][0] = dist[k1][2]+1
        already[v][0] = True
        not_yet.append((v, 0))
  if already[t-1][0]:
    print(dist[t-1][0]//3)
  else:
    print(-1)
  
    
if __name__ == "__main__":
  main()

Submission status: Accepted

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

INF = float('inf')
dist = [[INF] * N for _ in range(3)]
dist[0][S] = 0
q = [[S,0]]

while q:
    cp, cd = q.pop(0)
    nd = (cd + 1) % 3
    for np in E[cp]:
        if dist[nd][np] != INF:
            continue
        else:
            dist[nd][np] = dist[cd][cp] + 1
            q.append([np,nd])

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc132/tasks/abc132_e
# 拡張ダイクストラ

import heapq
from collections import defaultdict

INF = int(1e18)
N, M = map(int, input().split())
G = {n: [] for n in range(N)}
for _ in range(M):
    ui, vi = map(int, input().split())
    ui -= 1; vi -= 1
    G[ui].append((1, vi))
S, T = map(int, input().split()); S -= 1; T -= 1

Gp = {}
for n in G:
    for t in [0, 1, 2]:
        Gp[(n, t)] = []
for u in G:
    for c, v in G[u]:
        Gp[(u, 0)].append((c, (v, 1))) # Gp[(v, 1)].append((1, (u, 0)))
        Gp[(u, 1)].append((c, (v, 2))) # Gp[(v, 2)].append((1, (u, 1)))
        Gp[(u, 2)].append((c, (v, 0))) # Gp[(v, 0)].append((1, (u, 2)))

# dijkstra on Gp
s = (S, 0)
t = (T, 0)
d = {v: INF for v in Gp}
used = {v: True for v in Gp}
d[s] = 0
used[s] = False

edgelist = []
for e in Gp[s]:
    heapq.heappush(edgelist, e)

while len(edgelist) > 0:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
        continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in Gp[v]:
        if used[e[1]]:
            heapq.heappush(edgelist, (e[0] + d[v], e[1]))

if t not in d or d[t] == INF:
    print("-1")
else:
    print(d[t] // 3)