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:
#from collections import deque
import sys
input = sys.stdin.readline
def MI():return map(int,input().split())
def main():
  n,m=MI()
  G=[[] for _ in range(n)]
  for _ in range(m):
    u,v=MI()
    u-=1
    v-=1
    G[u].append(v)
  s,t=MI()
  s-=1
  t-=1
  
  fi=[True]*n
  se=[True]*n
  th=[True]*n
  th[s]=False
  
  #dq=deque([])
  #dq.append(s)
  dq=[s]
  depth=0
  
  while dq:
    depth+=1
    tank1=[]
    tank2=[]
    tank3=[]
    
    for p in dq:
      for c in G[p]:
        if fi[c]:
          fi[c]=False
          tank2.append(c)
    for p in tank2:
      for c in G[p]:
        if se[c]:
          se[c]=False
          tank3.append(c)
    for p in tank3:
      for c in G[p]:
        if th[c]:
          th[c]=False
          tank1.append(c)
        if c==t:
          print(depth)
          exit()
    dq=tank1
  print(-1)  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def MI():return map(int,input().split())
def main():
  n,m=MI()
  G=[[] for _ in range(n)]
  for _ in range(m):
    u,v=MI()
    u-=1
    v-=1
    G[u].append(v)
  s,t=MI()
  s-=1
  t-=1
  
  fi=[True]*n
  se=[True]*n
  th=[True]*n
  th[s]=False
  
  dq=deque([])
  dq.append(s)
  depth=0
  
  while dq:
    depth+=1
    tank1=[]
    tank2=[]
    tank3=[]
    
    for p in dq:
      for c in G[p]:
        if fi[c]:
          fi[c]=False
          tank2.append(c)
    for p in tank2:
      for c in G[p]:
        if se[c]:
          se[c]=False
          tank3.append(c)
    for p in tank3:
      for c in G[p]:
        if th[c]:
          th[c]=False
          tank1.append(c)
        if c==t:
          print(depth)
          exit()
    dq=deque(tank1)
  print(-1)  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:


import heapq as hq

def bfs(connections:list,s,t):
    inf = float('inf')
    costs =[[inf,inf,inf] for i in connections]
    visited = [[False,False,False] for i in connections]
    costs[s][0]=0
    q =[]
    hq.heappush(q,(0,0,s))

    while q:
        cost,step,node = hq.heappop(q)
        if visited[node][step]:
            continue
        visited[node][step] = True
        
        for target in connections[node]:
            if costs[target][(step+1)%3]>cost+1:
                costs[target][(step+1)%3]=cost+1
                hq.heappush(q,(cost+1,(step+1)%3,target)) 

    ans = costs[t][0]

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


    



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

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

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

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



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

s, t = map(int, input().split())
dist = [-1] * (3 * n)
queue = deque([3 * s - 3])
dist[3 * s - 3] = 0
while queue:
  vertex = queue.popleft()
  for next_vertex in adj_list[vertex]:
    if dist[next_vertex] != -1:
      continue
    dist[next_vertex] = dist[vertex] + 1
    queue.append(next_vertex)
t_distance = dist[3 * t - 3]
if t_distance == -1:
  print(-1)
else:
  print(t_distance // 3)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

INF = float("inf")
n, m = map(int, input().split())
idx = [[i*3 + j for j in range(3)] for i in range(n)]
g = [[] for _ in range(n*3)]
for _ in range(m):
    u, v = map(lambda x: int(x)-1, input().split())
    for i in range(3):
        g[idx[u][i]].append((idx[v][(i+1) % 3], 1))
s, t = map(lambda x: int(x)-1, input().split())

def dijkstra(graph, n, s):
    d = [INF] * n
    d[s], q = 0, []
    heappush(q, (0, s))
    while q:
        dist, v = heappop(q)
        if d[v] < dist: continue
        for nv, cost in graph[v]:
            if d[nv] > d[v] + cost:
                d[nv] = d[v] + cost
                heappush(q, (d[nv], nv))
    return d

res = dijkstra(g, n*3, idx[s][0])[idx[t][0]]
print(-1 if res == INF else res // 3)

Submission status: Accepted

Solution code:
#ダイクストラ
#単一始点最短経路(正の辺のみ)
#s=始点 n=頂点数 edgeは隣接リスト(edge=[[[1,2],[2,4]],[[2,1]],[]])
#0-indexed
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
n,m=map(int,input().split())
edge=[[]for _ in range(n*3)]
for _ in range(m):
	u,v=map(int,input().split())
	u-=1
	v-=1
	edge[u*3].append([v*3+1,1])
	edge[u*3+1].append([v*3+2,1])
	edge[u*3+2].append([v*3,1])
s,t=map(int,input().split())
s-=1
t-=1
dij=dijkstra(s*3,n*3,edge)
if dij[t*3]==10**20:print(-1)
else:print(dij[t*3]//3)

Submission status: Accepted

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


s, t = map(int, input().split())
q = deque([[s, 0]])
visited = [[False] * 3 for _ in range(n+1)]
visited[s][0] = True
dist = [[-3] * 3 for _ in range(n+1)]
dist[s][0] = 0
while q:
    num, cnt = q.popleft()
    for i, j in graph[num][cnt]:
        if visited[i][j]:
            continue
        q.append([i, j])
        visited[i][j] = True
        dist[i][j] = dist[num][cnt] + 1

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

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    from collections import deque
    n,m = map(int,input().split())
    Es = [[] for i in range(n)]
    Et = [[] for i in range(n)]
    for i in range(m):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        Es[a].append(b)
        Et[b].append(a)
    s,t = map(int,input().split())

    diss = [[float("INF")] for i in range(n)]
    dist = [[float("INF")] for i in range(n)]
    diss[s-1] = [0]
    dist[t-1] = [0]
    def bfs(x,E,dis):
        q = deque([])
        q.append((x,0))
        while q:
            now,d = q.popleft()
            for nex in E[now]:
                if dis[nex] == [float("INF")]:
                    dis[nex] = [d+1]
                    q.append((nex,d+1))
                else:
                    check = True
                    for i in dis[nex]:
                        if i%3 == (d+1)%3:
                            check = False
                    if check:
                        q.append((nex,d+1))
                        dis[nex].append(d+1)

    bfs(s-1,Es,diss)
    bfs(t-1,Et,dist)

    ans = float("INF")
    for i in range(n):
        for j in diss[i]:
            for k in dist[i]:
                if (j+k)%3 == 0:
                    ans = min(ans,(j+k)//3)
    if ans == float("INF"):
        print(-1)
    else:
        print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def bfs():
    dist = [-1]*(3*N)
    dist[serial[S][0]] = 0
    q = deque([serial[S][0]])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist[serial[T][0]]

N, M = map(int, input().split())
serial = [[-1]*3 for _ in range(N)]
c = 0

for i in range(N):
    for j in range(3):
        serial[i][j] = c
        c += 1

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

for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[serial[u][0]].append(serial[v][1])
    G[serial[u][1]].append(serial[v][2])
    G[serial[u][2]].append(serial[v][0])

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from queue import Queue
# 12:55~
sys.setrecursionlimit(10**9)

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

S -= 1
T -= 1
#%%
adj_list = [[[] for _ in range(3)] for _ in range(N)]
for u,v in uv:
    for i in range(3):
        adj_list[u-1][i].append([v-1,(i+1)%3])


INF = 10**9+7
dist = [[INF]*3 for _ in range(N)]
dist[S][0] = 0

stack = Queue()
stack.put([S,0])
while not stack.empty():
    v,c = stack.get()
    nxt_v = adj_list[v][c]
    for nv,nc in nxt_v:
        if dist[nv][nc]==INF:
            dist[nv][nc] = dist[v][c] + 1
            stack.put([nv,nc])
            
            
if dist[T][0]==INF:
    ans = -1
else:
    ans = dist[T][0]//3
print(ans)

Submission status: Accepted

Solution code:
import heapq as h

N,M=map(int,input().split())
hen={(i,j):[] for i in range(0,N) for j in range(0,3)}
for i in range(0,M):
    u,v=map(int,input().split())
    hen[(u-1,0)].append((v-1,1))
    hen[(u-1,1)].append((v-1,2))
    hen[(u-1,2)].append((v-1,0))

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

start=(S-1,0)
goal=(T-1,0)

distance={(i,j):-1 for i in range(0,N) for j in range(0,3)}

q=[]
q.append(start)
distance[start]=0
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
            if distance[p]==-1:
                h.heappush(sub,p)
                distance[p]=distance[x]+1
        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

if distance[goal]==-1:
    print(-1)
else:
    print(distance[goal]//3)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
n,m = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)

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

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

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*(n*3)
que = deque([s-1])
dist[s-1] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
print(dist[t-1]//3)

Submission status: Accepted

Solution code:
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, ipti().split()))
    node_next = [set() for _ in range(n)]

    for i in range(m):
        u, v = list(map(int, ipti().split()))
        node_next[u - 1].add(v - 1)

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

    dist = [[INF] * n for _ in range(3)]
    dist[0][s] = 0

    que = deque()
    que.append((0, s))

    while que:
        cstate, cnode = que.popleft()
        d = dist[cstate][cnode]
        nstate = (cstate + 1) % 3
        for nnode in node_next[cnode]:
            if dist[nstate][nnode] == INF:
                dist[nstate][nnode] = d + 1
                que.append((nstate, nnode))

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


if __name__ == '__main__':
    main()

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

adj = [[] for _ in range(3 * n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v + n)
    adj[u + n].append(v + 2 * n)
    adj[u + 2 * n].append(v)


def bfs(s):
    q = deque([s])
    d = [-1] * (3 * n)
    d[s] = 0
    while q:
        u = q.popleft()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                q.append(v)

    return d


dist = bfs(s - 1)
ans = dist[t - 1]
print(ans // 3)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)

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

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

PATH = [[] for _ in range(N + 1)]

for u, v in UV:
    PATH[u].append(v)

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

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

while q:
    u, mod = q.popleft()
    d = dist[u][mod]

    nmod = (mod + 1) % 3
    for v in PATH[u]:
        if dist[v][nmod] != -1:
            continue
        dist[v][nmod] = d + 1
        q.append((v, nmod))


if dist[T][0] == -1:
    ans = -1
else:
    ans = dist[T][0] // 3

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
mod = 10**9 + 7

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

s, t = [int(x) for x in input().split()]

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

def bfs(u):
    queue = deque([[u, 0]])
    d[u][0] = 0
    while queue:
        v, d_ = queue.popleft()
        for i in g[v]:
            if d[i][(d_ + 1) % 3] < 0:
                d[i][(d_ + 1) % 3] = d_ + 1
                queue.append([i, d_ + 1])
    return d

d = bfs(s - 1)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

#1回ずつ数えて答えを3で割る
N, M = lr()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(M):
    u, v = lr()
    graph[u].append(v)

S, T = lr()
que = deque([(S, 0)])
time_set = [set() for _ in range(N+1)] # 1-indexed
while que:
    q, time = que.popleft()
    if time > M * 3:
        break
    for next in graph[q]:
        if (time+1) % 3 in time_set[next]:
            continue
        if next == T and (time+1) % 3 == 0:
            print((time+1)//3); exit()
        que.append((next, time+1))
        time_set[next].add((time+1)%3)

print(-1); exit()
# 52

Submission status: Accepted

Solution code:
from collections import deque 
MOD = 10**9 +7
INF = 10**9
def main():
    n,m = map(int,input().split())
    V0 = [[] for _ in range(n)]
    V1 = [[] for _ in range(n)]
    V2 = [[] for _ in range(n)]
    for _ in range(m):
        u,v = map(int,input().split())
        u -= 1
        v -= 1
        V0[u].append(v)
        V1[u].append(v)
        V2[u].append(v)
    
    s,t = map(int,input().split())
    s -= 1
    t -= 1
    
    d0 = [-1]*n
    d1 = [-1]*n
    d2 = [-1]*n
    d0[s] = 0

    q = deque()
    q.append((s,0))
    while len(q):
        v,mod = q.popleft()
        if mod == 0:
            for e in V0[v]:
                if d1[e] == -1:
                    d1[e] = d0[v] + 1
                    q.append([e,1])

        elif mod == 1:
            for e in V1[v]:
                if d2[e] == -1:
                    d2[e] = d1[v] + 1
                    q.append([e,2])
        
        else:
            for e in V2[v]:
                if e == t:
                    print((d2[v] + 1)//3)
                    exit()           
                if d0[e] == -1:
                    d0[e] = d2[v] + 1
                    q.append([e,0])
    
    if d0[t] == -1:
        print(-1)
   
if __name__=='__main__':
    main()

Submission status: Accepted

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

import heapq

INF = float('inf')

def dijkstra(graph, st):
    n  = len(graph)
    ds = [INF]*n
    ds[st] = 0
    prevs = [None]*n
    
    qs = [(0, st)]

    while len(qs) > 0:
        d, nodeId = heapq.heappop(qs)
        
        if d > ds[nodeId]:
            continue
        
        for destId, length in graph[nodeId]:
            d2 = d + length
            if ds[destId] > d2:
                ds[destId] = d2
                prevs[destId] = nodeId
                heapq.heappush(qs, (d2, destId))
                
    return (ds, prevs)


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

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


S, T = map(int, input().split())
ds, prevs = dijkstra(G, S*3-3)

ans = ds[T*3-3]
print(ans//3 if ans != INF else -1)

Submission status: Accepted

Solution code:
import queue 
MOD = 10**9 +7
INF = 10**9
def main():
    n,m = map(int,input().split())
    V0 = [[] for _ in range(n)]
    V1 = [[] for _ in range(n)]
    V2 = [[] for _ in range(n)]
    for _ in range(m):
        u,v = map(int,input().split())
        u -= 1
        v -= 1
        V0[u].append(v)
        V1[u].append(v)
        V2[u].append(v)
    
    s,t = map(int,input().split())
    s -= 1
    t -= 1
    
    d0 = [-1]*n
    d1 = [-1]*n
    d2 = [-1]*n
    d0[s] = 0

    q = queue.Queue()
    q.put([s,0])
    while q.qsize() != 0:
        p = q.get()
        mod = p[1]
        v = p[0]
        if mod == 0:
            for e in V0[v]:
                if d1[e] == -1:
                    d1[e] = d0[v] + 1
                    q.put([e,1])

        elif mod == 1:
            for e in V1[v]:
                if d2[e] == -1:
                    d2[e] = d1[v] + 1
                    q.put([e,2])
        
        else:
            for e in V2[v]:
                if d0[e] == -1:
                    d0[e] = d2[v] + 1
                    q.put([e,0])
    
    if d0[t] == -1:
        print(-1)
    else:
        print(d0[t]//3)
   
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def dijkstra1(V, n, inf, source):
    # O(ElogV)

    dist = [inf] * (n+1)
    dist[source] = 0
    q = [(0, source)]

    while q:
        cost, u = heappop(q)
        if dist[u] < cost:
            continue
        for c, v in V[u]:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
                heappush(q, (dist[v], v))

    return dist


def solve():
    INF = 10**25
    N, M = map(int, input().split())
    V = {i:[] for i in range(1, 3*N+1)}
    for _ in range(M):
        u, v = map(int, input().split())
        V[u].append((1, v+(N)))
        V[u+(N)].append((1, v+(2*N)))
        V[u+(2*N)].append((1, v))

    S, T = map(int, input().split())
    dist = dijkstra1(V, 3*N, INF, S)[T]
    print(-1 if dist==INF else dist//3)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def dijkstra1(V, n, source):
    # O(ElogV)

    inf = float("inf")
    dist = [inf] * (n+1)
    dist[source] = 0
    q = [(0, source)]

    while q:
        cost, u = heappop(q)
        if dist[u] < cost:
            continue
        for c, v in V[u]:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
                heappush(q, (dist[v], v))

    return dist


def solve():
    N, M = map(int, input().split())
    V = {i:[] for i in range(1, 3*N+1)}
    for _ in range(M):
        u, v = map(int, input().split())
        V[u].append((1, v+(N)))
        V[u+(N)].append((1, v+(2*N)))
        V[u+(2*N)].append((1, v))

    S, T = map(int, input().split())
    dist = dijkstra1(V, 3*N, S)[T]
    print(-1 if dist==float("inf") else dist//3)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def dijkstra1(V, n, source):
    # O(ElogV)

    inf = float("inf")
    dist = [inf] * (n+1)
    dist[source] = 0
    q = [(0, source)]

    while q:
        cost, u = heappop(q)
        if dist[u] < cost:
            continue
        for c, v in V[u]:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
                heappush(q, (dist[v], v))

    return dist


if __name__ == "__main__":
    N, M = map(int, input().split())
    V = {i:[] for i in range(1, 3*N+1)}
    for _ in range(M):
        u, v = map(int, input().split())
        V[u].append((1, v+(N)))
        V[u+(N)].append((1, v+(2*N)))
        V[u+(2*N)].append((1, v))

    S, T = map(int, input().split())
    dist = dijkstra1(V, 3*N, S)[T]
    print(-1 if dist==float("inf") else dist//3)

Submission status: Accepted

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


def bfs(V, s, t):
    q = deque([(0, s)])
    used = set()
    
    while q:
        dist, a = q.popleft()
        used.add(a)
        if a == t:
            break
        for b in V[a]:
            if b in used: continue
            q.append((dist+1, b))
    
    if a != t:
        dist = -1
    else:
        dist = -1 if dist%3 else dist//3
    return dist

def dijkstra1(V, n, source):
    # O(ElogV)

    inf = float("inf")
    dist = [inf] * (n+1)
    dist[source] = 0
    q = [(0, source)]

    while q:
        cost, u = heappop(q)
        if dist[u] < cost:
            continue
        for c, v in V[u]:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
                heappush(q, (dist[v], v))

    return dist


if __name__ == "__main__":
    V = defaultdict(list)
    N, M = map(int, input().split())
    for _ in range(M):
        u, v = map(int, input().split())
        V[u].append((1, v+(N)))
        V[u+(N)].append((1, v+(2*N)))
        V[u+(2*N)].append((1, v))

    S, T = map(int, input().split())
    dist = dijkstra1(V, 3*N, S)[T]
    print(-1 if dist==float("inf") else dist//3)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy

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

data=[[] for i in range(N+1)]
for u,v in UV:
    data[u].append(v)

visited={S}
visited1=set()
visited2=set()
stack=deque([[S,0]])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        z=(m+1)

        if z%3==0:
            if p in visited:
                continue
            elif p == T:
                print(z//3)
                exit()
            else:
                visited.add(p)
        if z%3==1:
            if p in visited1:
                continue
            else:
                visited1.add(p)
        if z%3==2:
            if p in visited2:
                continue
            else:
                visited2.add(p)
        stack.append([p,z])

print(-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

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

    s, t = map(int, input().split())
    que = deque()
    que.append(s)
    seen = [-1] * (N*3+5)
    seen[s] = 0
    while que:
        v = que.popleft()
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                que.append(u)

    if seen[t] == -1:
        print(-1)
    else:
        assert seen[t] % 3 == 0
        print(seen[t] // 3)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
l = [[] for i in range(n+1)]
rl = [[-1 for i in range(n+1)] for i in range(3)]
for i in range(m):
    u,v = map(int,input().split())
    l[u].append(v)
s,t = map(int,input().split())
d = deque()
ans = -1
d.append([s,0])
rl[0][s] = 0
while len(d):
    now,count = d.popleft()
    for i in l[now]:
        if i == t and count % 3 == 2:
            ans = (count + 1)//3
            break
        else:
            if rl[(count%3 + 1)%3][i] == -1:
                d.append([i,count+1])
                rl[(count%3+1)%3][i] = count+1
    if ans >= 0:
        break
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
s,t = map(int, input().split())

from collections import deque
Q = deque()
Q.append([s-1,0,0])
visited = [[] for _ in range(n)]
visited[s-1]=[0]

while Q:
    now,kkp,cnt = Q.popleft()
    nxt_kkp = (kkp+1)%3
    for nxt in link[now]:
        if nxt == (t-1) and nxt_kkp == 0:
            print((cnt+1)//3)
            exit()
        if nxt_kkp in visited[nxt]:
            continue
        visited[nxt].append(nxt_kkp)
        Q.append([nxt,nxt_kkp,cnt+1])

print(-1)

Submission status: Accepted

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

graphs = [[] for _ in range( 3 * N)]
dists = [-1 for _ in range( 3 * N)]
for uv in UVm:
  u = uv[0] - 1
  v = uv[1] - 1
  graphs[u].append(v + N)
  graphs[u + N].append( v + 2 * N)
  graphs[u + 2 * N].append(v)

  
from collections import deque
que = deque()
que.append(S - 1)
dists[S - 1] = 0
while len(que) > 0:
  nex = que.popleft()
  for edge in graphs[nex]:
    if dists[edge] != -1:
      continue
    que.append(edge)
    dists[edge] = dists[nex] + 1

print(dists[T-1]//3)

Submission status: Accepted

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

graphs = [[] for _ in range( 3 * N)]
dists = [-1 for _ in range( 3 * N)]
for uv in UVm:
  u = uv[0] - 1
  v = uv[1] - 1
  graphs[u].append(v + N)
  graphs[u + N].append( v + 2 * N)
  graphs[u + 2 * N].append(v)
  
def dist(s, t, g):
    q = [s]
    dists = [-1]*len(g)
    dists[s] = 0
    while len(q) != 0:
        p = []
        for u in q:
            for v in g[u]:
                if dists[v] != -1:
                    continue
                p.append(v)
                dists[v] = dists[u] + 1
        q = p
    return dists[t]
print(dist(S-1, T-1, graphs)//3)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque

N,M = list(map(int,stdin.readline().split()))
Cs = [tuple(map(int,stdin.readline().split())) for _ in range(M)]
S,T = list(map(int,stdin.readline().split()))

INF = 10 ** 15
# visit = [False] * ( (N + 1) * 3 )
dist  = [-1] * ( (N) * 3 + 1 )
graph_connection = defaultdict(lambda :[])
graph_cost = defaultdict(lambda :defaultdict(lambda :INF))
#
# def dfs(v,dist_before):
#
#     dist[v] = dist_before + 1
#     next_vertexs = graph_connection[v]
#     for next_v  in next_vertexs :
#         if dist[next_v] == -1:
#             dfs(next_v,dist[v])
#     return 0
#

for cost in  Cs:
    a,b= cost
    for i in range(0,3):
        from_v = a + (i) * N
        to_v = b + (i + 1) % 3 * N
        graph_connection[from_v].append(to_v )

        # from_v = b + (i) * N
        # to_v = a + (i + 1) % 3 * N
        # graph_connection[from_v].append(to_v )

# dist[S] = 0


que = deque()
#(from_v,to_v)
dist[S] = 0
que.append(S)
while len(que) != 0:
    from_v = que.popleft()
    nexts = graph_connection[from_v]
    for next_v in nexts:
        if dist[next_v] == -1:
            dist[next_v] = dist[from_v] + 1
            que.append(next_v)

if dist[T] < 0:
    print(dist[T] )
else:
    print(dist[T]//3)

Submission status: Accepted

Solution code:
def dist(s, t, g):
    q = [s]
    dists = [-1]*len(g)
    dists[s] = 0
    while len(q) != 0:
        p = []
        for u in q:
            for v in g[u]:
                if dists[v] != -1:
                    continue
                p.append(v)
                dists[v] = dists[u] + 1
        q = p
    return dists[t]

def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n*3)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append(v+n)
        g[u+n].append(v+2*n)
        g[u+2*n].append(v)
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    print(dist(s, t, g)//3)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
inf = 10**9
def bfs(start):
    dist = [inf for i in range((n+1) * 3)]
    que = deque()
    que.append(start)
    finished = set()
    dist[start] = 0
    while que:
        node = que.popleft()
        if node not in finished:
            finished.add(node)
            for i in adjacent_list[node]:
                dist[i] = min(dist[i], dist[node] + 1)
                que.append(i)
    return dist

adjacent_list = [[] for i in range((n+1)*3)]
for _ in range(m):
    u, v = map(int, input().split())
    for i in range(3):
        adjacent_list[u*3 + i].append(v*3 +((i+1)%3))
start, goal = map(int, input().split())
graph = bfs(start*3)
if graph[goal*3] != inf:
    print(int(graph[goal*3]) // 3)
else:
    print(-1)