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, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
E = defaultdict(list)
for i in range(M):
	u, v = rl()
	E[u-1].append(v-1)
S, T = rl()
S -= 1
T -= 1

dp = [[float('inf')]*3 for i in range(N)]

heap = []
heappush(heap, (0, S, 0))
while heap:
	d, n, r = heappop(heap)
	if n == T and r == 0:
		continue
	#if dp[n][r] != d:
	#	continue
	nr = (d+1)%3
	for m in E[n]:
		if dp[m][nr] > d+1:
			dp[m][nr] = d+1
			heappush(heap, (d+1, m, nr))

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n)]
gg=[[] for _ in range(3*n)]
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  gg[a].append(n+b)
  gg[n+a].append(2*n+b)
  gg[2*n+a].append(b)
s,t=map(int,input().split())
s,t=s-1,t-1
from collections import deque
todo=deque([s])
seen=[-1]*(3*n)
seen[s]=0
while todo:
  v=todo.popleft()
  for l in gg[v]:
    if seen[l]==-1:
      todo.append(l)
      seen[l]=seen[v]+1
      if l==t:
        print(seen[l]//3)
        exit()
if seen[t]>0:
  print(seen[t]//3)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, p):
        for u in edge_extend[p][v]:
            next_p = 0 if p == 2 else p + 1
            if dist[next_p][u] <= dist[p][v] + 1:
                continue
            else:
                dist[next_p][u] = dist[p][v] + 1
                dfs(u, next_p)

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

    edge_extend = []
    for _ in range(3):
        edge_extend.append(edge)

    dist = [[f_inf] * n for _ in range(3)]
    dist[0][s - 1] = 0
    que = deque([[0, s - 1]])
    while que:
        p, v = que.popleft()
        next_p = 0 if p == 2 else p + 1
        for u in edge_extend[p][v]:
            if dist[next_p][u] > dist[p][v] + 1:
                dist[next_p][u] = dist[p][v] + 1
                que.append([next_p, u])

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ 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])
INF = 10**10
dist = [[INF]*3 for _ in range(n)]
dist[s][0] = 0
while q:
    node = q.popleft()
    for c_node in graph[node]:
        flg = False
        for i in range(3):
            nd = dist[node][i]+1
            if dist[c_node][nd%3] > nd:
                dist[c_node][nd%3] = nd
                flg = True
        if flg:
            q.append(c_node)
if dist[t][0]==INF:
    print(-1)
else:
    print(dist[t][0]//3)

Submission status: Accepted

Solution code:
from collections import deque

n,m=list(map(int,input().split()))
g=[[] for _ in range(10*(n+1)+3)]


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

s,t=list(map(int,input().split()))
inf=10**10
q=deque([10*s])
d=[inf]*(10*(n+1)+3)
d[10*s]=0

while len(q)>0:
    u=deque.pop(q)
    res=u%10
    for i in range(3):
        nres=(res+i)%3
        for v in g[u]:
            if d[v]<inf:
                continue
            d[v]=min(d[v],d[u]+1)
            deque.appendleft(q,v)

if d[10*t]==inf:
    print(-1)
else:
    print(d[10*t]//3)

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())
    edges[u-1].append(v-1)
 
S, T = map(int,input().split())
S -= 1
T -= 1
 
visited = {}
q = deque()
q.append((S, 0))
d = -1
while q:
    s, c = q.popleft()
    if s in visited and (c % 3) in visited[s]:
        continue
    if s not in visited:
        visited[s] = set()
    visited[s].add(c % 3)
    for n in edges[s]:
        if n == T and c % 3 == 2:
            d = c + 1
            break
        q.append((n, c+1))
 
    if d % 3 == 0:
        break
 
if d == -1:
    print(-1)
else:
    print(d//3)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    layers = [set() for _ in range(3)]
    
    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    if root not in layers[i]:
                        layers[i].add(root)
                        purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
adjacent_list = [[] for i in range(3*n + 3)]
for i in range(m):
    u, v = map(int, input().split())
    for j in range(1,4):
        p = j + 3 * u - 3
        q = (j % 3) + 3 * v - 2
        #print("{} -> {}".format(p, q))
        adjacent_list[p].append(q)
s, t = map(int, input().split())

def bfs(start, target):
    que = deque()
    finished = set()
    que.append([start, 0])
    while que:
        node, dist = que.popleft()
        if (node, dist % 3) in finished:
            continue
        if node == target:
            return dist // 3
        for i in adjacent_list[node]:
            que.append([i, dist+1])
            finished.add((node, dist % 3))
    return -1
print(bfs(s*3 -2, 3*t-2))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())
dijkstra = Dijkstra(3 * N)
for a, b in edges:
    a, b = a - 1, b - 1
    dijkstra.add_edge(a, N + b, 0)
    dijkstra.add_edge(N + a, 2 * N + b, 0)
    dijkstra.add_edge(2 * N + a, b, 1)
ans = dijkstra.distance(S - 1)[T - 1]
print(ans if ans != float('inf') else -1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque
n,m=map(int,input().split())
edges=[[] for i in range(n)]
for i in range(m):
    u,v=map(int,input().split())
    edges[u-1].append(v-1)
s,t=map(int,input().split())
inf=100000000000
score=[[inf]*3 for i in range(n)]
now=deque()
now.append(s-1)
score[s-1][0]=0
def bfs(dep,l):
    global n,m,edges,s,t,score,inf,now
    f=False
    for i in range(l):
        ne=now.popleft()
        for j in edges[ne]:
            if score[j][dep%3]==inf:
                score[j][dep%3]=dep
                now.append(j)
    l_ne=len(now)
    if l_ne:bfs(dep+1,l_ne)
bfs(1,1)
if score[t-1][0]!=inf:
    print(score[t-1][0]//3)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    edges[u-1].append(v-1)

S, T = map(int, sys.stdin.readline().split())
S -= 1
T -= 1

visited = {}
q = deque()
q.append((S, 0))
d = -1
while q:
    s, c = q.popleft()
    if s in visited and (c % 3) in visited[s]:
        continue
    if s not in visited:
        visited[s] = set()
    visited[s].add(c % 3)
    for n in edges[s]:
        if n == T and c % 3 == 2:
            d = c + 1
            break
        q.append((n, c+1))

    if d % 3 == 0:
        break

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M = getNM()
query = [getList() for i in range(M)]
S, T = getNM()

def build_tree_dis(N, edge_list):

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

    for i in range(len(edge_list)):
        a, b = edge_list[i]
        G[a - 1].append(b - 1)

    # 葉（末端の数）
    leaves = []
    for i in range(N):
        if len(G[i]) == 1:
            leaves.append(i)

    return G

edges = build_tree_dis(N, query)

ignore = [[-1] * 3 for i in range(N)]
ignore[S - 1][0] = 0

pos = deque([[S - 1, 0]])

while len(pos) > 0:
    u, t = pos.popleft()
    t += 1
    j = t % 3
    for i in edges[u]:
        if ignore[i][j] == -1:
            ignore[i][j] = t
            pos.append([i, t])

if ignore[T - 1][0] % 3 == 0:
    print(ignore[T - 1][0] // 3)
    exit()
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    edge = [[] for i in range(N)]
    for i in range(M):#木の場合M=N-1
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
    S, T = map(int, input().split())
    S-=1;T-=1

    def dfs():
        q=deque([(0,S)])
        visited=[[False]*N for _ in range(3)]
        while len(q):
            
            d,e=q.popleft()#ここをpopleftにすると幅優先探索BFSになる
            
            if visited[d%3][e]:continue
            elif d%3==0:
                if e==T:
                    print(d//3)
                    return 
            visited[d%3][e]=True
            
            for ne in edge[e]:
                q.append((d+1,ne))
        print(-1)
    dfs()
    




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
def bfs(start, g, visited, goal):
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        for next_node in g[curr_node]:
            if visited[next_node] >= 0: continue
            visited[next_node] = visited[curr_node] + 1
            if next_node == goal: return
            q.append(next_node)


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

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

s,t = map(int, input().split())
visited = [-3]*(3*n)
bfs(s*3-3, g, visited, t*3-3)
print(visited[t*3-3]//3)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    dist = [[f_inf] * 3 for _ in range(n)]
    que = deque([])
    que.append([s - 1, 0])
    dist[s - 1][0] = 0
    while que:
        v, l = que.popleft()
        for u in edge[v]:
            nl = (l + 1) % 3
            if dist[u][nl] == f_inf:
                dist[u][nl] = dist[v][l] + 1
                que.append([u, nl])

    res = dist[t - 1][0]
    print(-1 if res == f_inf else res // 3)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for _ in range(N + 1)]
for u, v in X:
    graph[u].append(v)

INF = 10 ** 9 + 7
ctr = [[INF] * (N + 1) for _ in range(3)]
ctr[0][S] = 0
stack = deque()
stack.append((0, S))
while stack:
    i, u = stack.popleft()
    j = (i + 1) % 3
    for v in graph[u]:
        if ctr[j][v] > ctr[i][u] + 1:
            ctr[j][v] = ctr[i][u] + 1
            stack.append((j, v))
            
if ctr[0][T] < INF:
    print(ctr[0][T] // 3)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

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

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
def bfs():
    while len(q) > 0:
        now,cnt = q.popleft()
        step = cnt % 3
        if now == T and step  == 0:  
            return cnt
        for x in path[now]:
            if vis[x][(step+1)%3] == -1:
                vis[x][(step+1)%3] = cnt
                q.append((x,cnt+1))
    return -3
vis[S][0] = 1
q.append([S,0])
print(bfs()//3)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

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

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            vis[x][(step+1)%3] = cnt
            q.append((x,cnt+1))

if vis[T][0] == -1:
    print(-1)
else:
    print(vis[T][0]//3+1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
e = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    e[u].append(v)

'''
頂点を%3で考える(1つの頂点にを3つに分解する)
(u,0)->(v,1)
(v,1)->(u,2)
(u,2)->(v,0)
'''

S, T = map(int, input().split())
q = deque([[S, 0]])
dist = [[-3]*3 for _ in range(N+1)]
dist[S][0] = 0
while q:
    u, c = q.popleft()
    for v in e[u]:
        step = (c+1) % 3
        if dist[v][step] < 0:
            dist[v][step] = c+1
            q.append([v, c+1])

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def kenkenpa(s, visited):
    res = []
    for v1 in e[s]:
        if visited[v1][1]:
            continue
        visited[v1][1] = True
        for v2 in e[v1]:
            if visited[v2][2]:
                continue
            visited[v2][2] = True
            for v3 in e[v2]:
                if visited[v3][0]:
                    continue
                visited[v3][0] = True
                res.append(v3)
    return res


N, M = map(int, input().split())
e = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    e[u].append(v)

S, T = map(int, input().split())
q = deque([[S, 0]])
visited = [[False]*3 for _ in range(N+1)]
visited[S][0] = True
ans = -1
while q:
    u, c = q.popleft()
    if u == T:
        ans = c
        break
    l = kenkenpa(u, visited)
    for v in l:
        q.append([v, c+1])
print(ans)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for i in range(n+1)]
    for _ in range(m):
        u,v = map(int,ipt().split())
        way[u].append(v)
    dist = [[-1]*3 for _ in range(n+1)]
    s,t = map(int,ipt().split())
    dist[s][0] = 0
    q = queue.Queue()
    q.put((s,0))
    while not q.empty():
        pi,pd = q.get()
        for i in way[pi]:
            if dist[i][(pd+1)%3] == -1:
                dist[i][(pd+1)%3] = (pd+1)//3
                q.put((i,pd+1))
    print(dist[t][0])

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
INF = 10 ** 10


def dijkstra(n, adj, s, t):
    dist = [INF for _ in range(n)]
    dist[s] = 0
    h = [(0, s)]
    while len(h) > 0:
        d, node = heapq.heappop(h)
        for next_node in adj[node]:
            next_d = d + 1
            if next_d < dist[next_node]:
                dist[next_node] = next_d
                heapq.heappush(h, (next_d, next_node))
    return dist[t]


def main():
    N, M = list(map(int, input().split(' ')))
    adj = [[] for _ in range(3 * N)]
    for _ in range(M):
        u, v = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[3 * u].append(3 * v + 1)
        adj[3 * u + 1].append(3 * v + 2)
        adj[3 * u + 2].append(3 * v)
    S, T = list(map(lambda x: int(x) - 1, input().split(' ')))
    d = dijkstra(3 * N, adj, 3 * S, 3 * T)
    if d == INF:
        print(-1)
    else:
        print(d // 3)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    G = [set() for i in range(N)]
    G2 = [set() for i in range(N*3)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        G[u].add(v)
    S, T = map(int, input().split())
    S -= 1
    T -= 1

    import collections
    q = collections.deque()
    q.append((S, 0))
    D = [-1]*N*3
    D[3*S] = 0
    while(q):
        x, d = q.popleft()
        for y in G[x]:
            if D[y*3+(d+1) % 3] < 0:
                # G2[x*3 + d].add(y)
                q.append((y, d+1))
                D[y*3 + (d+1) % 3] = d+1

    if D[T*3] > 0:
        print(D[T*3] // 3)

    else:
        print(-1)


main()

Submission status: Accepted

Solution code:
import sys
from collections import *
I=sys.stdin.readlines()
N,M=map(int,I[0].split())
E=[]
for i in range(M):
  E.append(list(map(lambda x:x-1,(list(map(int,I[i+1].split()))))))
S,T=map(int,I[M+1].split())
G=[[] for i in range(3*N)]
for i in range(M):
  G[E[i][0]].append(E[i][1]+N)
  G[E[i][0]+N].append(E[i][1]+N+N)
  G[E[i][0]+N+N].append(E[i][1])
D=deque()
Z=set()
def qao(x):
  global D,Z
  if x in Z:
    return False
  D.append(x)
  Z.add(x)
  return True

def bfs():
  global D,G,N
  v=0
  for i in range(len(D)):
    v=D.popleft()
    for j in range(len(G[v])):
      qao(G[v][j])
  return len(D)==0

qao(S-1)
for i in range(3*N):
  bfs()
  if T-1 in Z:
    print((i+1)//3)
    exit()
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    dist = [[-1] * 3 for _ in range(N)]
    dist[S][0] = 0
    queue = deque([(S, 0)])
    while queue:
        v, step = queue.popleft()
        if step == 0 and v == T:
            break

        for nv in G[v]:
            if dist[nv][(step - 1) % 3] != -1:
                continue
            dist[nv][(step - 1) % 3] = dist[v][step] + 1
            queue.append((nv, (step - 1) % 3))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n, m = map(int, input().split())
g = [[] for _ in range(3*n)]
for i 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

from collections import deque
q = deque()
visit = [-1]*(3*n)
q.append(s)
visit[s] = 0
while q:
    u = q.popleft()
    for v in g[u]:
        if visit[v] == -1:
            visit[v] = visit[u]+1
            q.append(v)
if visit[t] == -1:
    print(-1)
else:
    print(visit[t]//3)

Submission status: Accepted

Solution code:
def main():
  N, M = map(int, input().split())
  edge = [[[] for _ in range(3)] for _ in range(N)]
  for i in range(M):
    u, v = map(int, input().split())
    edge[u-1][0].append([v-1,1])
    edge[u-1][1].append([v-1,2])
    edge[u-1][2].append([v-1,0])
  d = [[-1]*3 for _ in range(N)]
  S, T = map(int, input().split())
  d[S-1][0] = 0
  que = [[S-1, 0]]
  while len(que)>0:
    now = que.pop(0)
    for nex in edge[now[0]][now[1]]:
      if d[nex[0]][nex[1]] != -1:continue
      d[nex[0]][nex[1]] = d[now[0]][now[1]]
      if now[1] == 2:
        d[nex[0]][nex[1]] += 1
      que.append(nex)
  print(d[T-1][0])
  
if __name__ == "__main__":
  main()

Submission status: Accepted

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

dist = [[-1]*3 for _ in range(n)]
dist[s][0] = 0
Q = deque([(s,0)])
while Q:
    now,r = Q.popleft()
    for nxt,nr in G[now][r]:
        if dist[nxt][nr] != -1: continue
        dist[nxt][nr] = dist[now][r]
        if r == 2: dist[nxt][nr] += 1
        Q.append((nxt,nr))
# print(dist)
print(dist[t][0])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc132/tasks/abc132_e
# ぱっと思いつくのはダイクストラで3回で到達できる点を探索していくとかかなぁ
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# 距離を3で割ったときに0,1,2余る場合について各ノードの最短距離を求めればよい

N, M = read_ints()
graph = defaultdict(lambda: [])
for _ in range(M):
    u, v = mina(*read_ints())
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)

S, T = mina(*read_ints())

pq = deque([])
D = [-3] * (N * 3)
D[S] = 0
pq.append((0, S))  # (最短距離, 次のノード)
while pq:
    d, v = pq.popleft()
    for to in graph[v]:
        if D[to] != -3:
            continue
        D[to] = d + 1
        pq.append((D[to], to))

print(D[T] // 3)

Submission status: Accepted

Solution code:
import heapq

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

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

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

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

D=[10**6 for i in range(3*N)]
D[~-S]=0
A=[(0,~-S)]
heapq.heapify(A)

while len(A)>0:
  d,v=heapq.heappop(A)
  if D[v]<d:
    continue
  for i in L[v]:
    if D[i]>D[v]+1:
      D[i]=D[v]+1
      heapq.heappush(A,(D[v]+1, i))

print(D[~-T]//3 if D[~-T]!=10**6 else -1)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
K = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    K[a-1].append(b-1)
S, T = map(int, input().split())
used = [[0]*3 for _ in range(N)]

q = deque([[S-1, 0, 0]])
used[S-1][0] = 1
ans = [[-3]*3 for _ in range(N)]
while(len(q)>0):
    u, v, c = q.popleft()
    v_n = (v + 1) % 3
    for j in K[u]:
        if used[j][v_n] == 0:
            used[j][v_n] = 1
            ans[j][v_n] = c+1
            q.append([j, v_n, c+1])

print(ans[T-1][0]//3)