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
n, m = map(int, input().split())
edges = [[] for i in range(3*n)]
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v+n)
    edges[u+n].append(v+2*n)
    edges[u+2*n].append(v)

s,t = map(int, input().split())
s -= 1
t -= 1
INF = 1<<50
dists = [INF] * (3*n)

q = deque([])
q.append(s)
dists[s] = 0

while len(q)>0:
    v = q.popleft()
    for u in edges[v]:
        if dists[u] != INF: continue
        q.append(u)
        dists[u] = dists[v] + 1

if dists[t] == INF:
    print(-1)
else:
    print(dists[t]//3)

Submission status: Accepted

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

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

D = [[-1]*3 for _ in range(N)]
D[S][0] = 0
q = [(S, 0)]
while q:
    qq = []
    for p, d in q:
        for np in graph[p]:
            nd = (d+1)%3
            if D[np][nd] == -1:
                D[np][nd] = D[p][d] + 1
                qq.append((np, nd))
    q = qq

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        #最短のpathをたす


        class Edge():
            #重み付き有向辺

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            #引数Vは頂点数
            self.inf=10**20
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数

        #proparty - 辺の数
        def E(self):
            return self._E

        #proparty - 頂点数
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            que = [] #priority queue
            d = [self.inf] * self.V()

            #prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            #復元で使う

            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加

            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)

                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue

                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新

                        #prev[e.to] = v
                        #復元で使う

                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""

            return d#,path
    ########################
    mod=10**9+7
    N,M=MI()
    djk=Dijkstra(3*N)
    for _ in range(M):
        u,v=MI()
        u-=1
        v-=1
        djk.add(u,v+N,1)
        djk.add(u+N,v+2*N,1)
        djk.add(u+2*N,v,1)
    S,T=MI()
    S-=1
    T-=1
    D=djk.shortest_path(S)
    ans=D[T] //3
    
    if ans>10**7:
        ans=-1
        
    print(ans)
        
    


main()

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
dis = [[-1,-1,-1] for _ in range(N+1)]
Tree = [[] for _ in range(N+1)]
for i in range(M):
    ui,vi = map(int,input().split())
    Tree[ui].append(vi)
S,T = map(int,input().split())
d = deque([(S,0)])
dis[S][0] = 0
while d:
    x,z = d.popleft()
    for y in Tree[x]:
        if dis[y][(z+1)%3] == -1:
            dis[y][(z+1)%3] = dis[x][z] + 1
            d.append((y,(z+1)%3))
if dis[T][0] == -1:
    print(-1)
else:
    print(dis[T][0]//3)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
from collections import deque
import itertools

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n, m = map(int, input().split())
    u_s = [list(map(int, input().split())) for i in range(m)]
    s, t = map(int, input().split())

    point_s = [[] for i in range(n + 1)]
    [point_s[u[0]].append(u[1]) for u in u_s]

    # deq作成
    ans = [999999999 for i in range(n + 1)]
    bef = [999999999 for i in range(n + 1)]
    ans[s] = 0
    bef[s] = 0

    que = deque()
    que.appendleft(s)

    arrived1 = {}
    arrived2 = {}
    arrived3 = {}

    # BFS開始
    while len(que) is not 0:
        now = que.pop()

        # ケンケンパ
        work_s = point_s[now]
        ken = []
        for work in work_s:
            if arrived1.get(work, 0) == 0:
                ken.append(work)
                arrived1[work] = 1

        # list(itertools.chain.from_iterable(l_2d))
        work_s = [point_s[k] for k in ken]
        work_s = list(itertools.chain.from_iterable(work_s))
        kenken = []
        for work in work_s:
            if arrived2.get(work, 0) == 0:
                kenken.append(work)
                arrived2[work] = 1

        work_s = [point_s[k] for k in kenken]
        work_s = list(itertools.chain.from_iterable(work_s))
        kenkenpa = []
        for work in work_s:
            if arrived3.get(work, 0) == 0:
                kenkenpa.append(work)
                arrived3[work] = 1

        for ken in kenkenpa:
            if ans[ken] == 999999999:
                ans[ken] = ans[now] + 1
                bef[ken] = now
                # キューに追加(先頭に追加するのでappendleft())
                que.appendleft(ken)
            elif ans[ken] > ans[now] + 1:
                bef[ken] = now

    if ans[t] == 999999999:
        print(-1)
        return

    aa = bef[t]
    cnt = 1
    for i in range(9999999):
        if aa == s:
            break
        cnt += 1
        aa = bef[aa]

    print(cnt)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4
1 2
2 3
3 4
4 1
1 3"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3 3
1 2
2 3
3 1
1 2"""
        output = """-1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """2 0
1 2"""
        output = """-1"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6"""
        output = """2"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

n, m = map(int, input().split())

graph = [[] for _ in range(3*n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b+n)
    graph[a+n].append(b+2*n)
    graph[a+2*n].append(b)

dist = [-3] * (3*n+1)
dist[0] = 0
s, t = map(int, input().split())
dist[s] = 0

d = deque()
d.append(s)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -3:
            continue
        dist[i] = dist[v] + 1
        d.append(i)

print(dist[t]//3)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
list=[[] for i in range(3*N)]
for i in range(M):
  u,v=map(int,input().split())
  list[3*u-3].append(3*v-2)
  list[3*u-2].append(3*v-1)
  list[3*u-1].append(3*v-3)
s,t=map(int,input().split())
def bfs(a,b):
  visited=[-1 for i in range(3*N)]
  visited[a]=0
  h=[]
  h.append(a)
  while h:
    v=h.pop(0)
    for k in list[v]:
      if visited[k]==-1:
        visited[k]=visited[v]+1
        h.append(k)
  return visited[b]

print(bfs(3*s-3,3*t-3)//3)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  adj[a].append(b)

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

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

while q:
  n,d = q.popleft()
  for v in adj[n]:
    nd = (d+1)%3
    if dist[v][nd] != INF: continue
    dist[v][nd] = dist[n][d]+1
    q.append((v,nd))

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

Submission status: Accepted

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

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

INF = 10**7
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = nq
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

Submission status: Accepted

Solution code:
# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
edge = [[] for _ in range(N+1)]
for _ in range(M):
  u,v = map(int,input().split())
  edge[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 edge[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq

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

Submission status: Accepted

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

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

INF = 10**7
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

Submission status: Accepted

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

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

INF = 10**18
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

Submission status: Accepted

Solution code:
import copy

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

INF = 10**11
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

Submission status: Accepted

Solution code:
import copy

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

INF = 10**18
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc132/tasks/abc132_e
"""
タグ: bfs、拡張グラフ
"""

import sys
input = sys.stdin.readline
from collections import deque


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.visited = set()
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        p, t = start, time
        self.visited.add((p,0))
        next_set = deque([(p, t)])
        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if (q, (t+1)%3) in self.visited:
                    continue
                if q == goal and (t+1)%3==0:
                    return (t+1)//3
                self.visited.add((q,(t+1)%3))
                next_set.append((q, t + 1))
        return -1

##################################################################################################

N, M = map(int, input().split())
graph = Graph(N, directed=True, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)
S, T = map(int, input().split())
print(graph.bfs(start=S, goal=T))

Submission status: Accepted

Solution code:
from collections import deque
INF = 10**9

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

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

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

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

dist = [INF] * (3*N)
dist[s] = 0

Q = deque([s])
while len(Q) > 0:
    u = Q.popleft()
    for v in G[u]:
        if dist[v] == INF:
            dist[v] = dist[u] + 1
            Q.append(v)

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

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [[True] * 3 for _ in range(n)]

    que = collections.deque()
    que.append([0, s])
    visited[s][0] = False
    cnt = 0
    ans = -1
    flg = True

    while que and flg:
        cnt += 1
        for _ in range(len(que)):
            i, q = que.popleft()
            for ei in e[q]:
                tmp = (i + 1) % 3
                if tmp == 0 and ei == t:
                    ans = cnt // 3
                    flg = False
                    break
                elif visited[ei][tmp]:
                    visited[ei][tmp] = False
                    que.append([tmp, ei])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

#create digraph
#nodes will be (steps % 3) * N + node
N, M = map(int, input().split())
adj = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    adj[      u].append(  N + v)
    adj[  N + u].append(2*N + v)
    adj[2*N + u].append(      v)

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

#bfs
q = deque([S])
depth = [10 ** 9] * (3*N)
depth[S] = 0
while q:
    node = q.popleft()
    if node == T:
        break
    for next_node in adj[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.append(next_node)

if depth[T] == 10 ** 9:
    print(-1)
else:
    print(depth[T] // 3)

Submission status: Accepted

Solution code:

from heapq import heappop, heappush

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
d = [[INF] * 3 for _ in range(N + 1)]
d[S][0] = 0
pq = []
heappush(pq, (0, S))

while pq:
    _, u = heappop(pq)
    for v in graph[u]:
        for i in range(3):
            if d[v][(i + 1) % 3] > d[u][i] + 1:
                d[v][(i + 1) % 3] = d[u][i] + 1
                heappush(pq, (d[v][(i + 1) % 3], v))

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

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,M = IL()
graph = [[] for i in range(N*3)]
for _ in range(M):
  a,b = IL()
  a,b = a-1,b-1
  graph[a*3].append(b*3+1)
  graph[a*3+1].append(b*3+2)
  graph[a*3+2].append(b*3)
S,T = IL()
S,T = S-1,T-1

def bfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    for v in graph[u]:
      if d[v] != INF: continue
      d[v] = d[u] + 1
      q.append(v)
  return d

d = bfs(graph,S*3)
if d[T*3] == INF:
  print(-1)
else:
  print(d[T*3]//3)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[[]for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  A[a-1].append(b-1)
S,T=map(int,input().split())  
from collections import deque
import sys
sys.setrecursionlimit(10**7) #再帰制限のとっぱらい
D=[[-1]*3 for i in range(N)]
def bfs(x,n):
  q=deque()
  q.append((x,n)) 
  while len(q):
    x,n=q.popleft()
    for i in A[x]:
      d=(n+1)%3
      if D[i][d]==-1:
        D[i][d]=D[x][n]+1
        q.append((i,d))
D[S-1][0]=0
bfs(S-1,0)
if D[T-1][0]==-1:
  print(-1)
else:
  print(D[T-1][0]//3)

Submission status: Accepted

Solution code:
from collections import  deque

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

m = 0
p = 0
d[s][0] = 0

queue = deque([(s, 0)])
while queue:
    i, p0 = queue.popleft()
    p1 = (p0 + 1) % 3
    for j in g[i]:
        if d[j][p1] >= 0:
            continue
        d[j][p1] = d[i][p0] + 1
        if j == t and p1 == 0:
            print(d[j][p1] // 3)
            quit()
        queue.append((j, p1))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
edge = [[] for i in range(n)]
kkp = [0] * n
for i in range(m):
    u, v = map(int, input().split())
    edge[u - 1].append(v - 1)
s, t = map(int, input().split())
que = deque([(s - 1, 0)])
while que:
    now, dis = que.popleft()
    for next in edge[now]:
        if next == t - 1 and (dis + 1) % 3 == 0:
            exit(print((dis + 1) // 3))
        if not kkp[next] & (2 ** ((dis + 1) % 3)):
            kkp[next] = kkp[next] | (2 ** ((dis + 1) % 3))
            que.append((next, dis + 1))
print(-1)

Submission status: Accepted

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

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

    g = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v + N)
        g[u + N].add(v + N + N)
        g[u + N + N].add(v)

    S, T = (int(x) - 1 for x in input().split())

    dist = [-1] * (N * 3)
    dist[S] = 0

    dq = deque()
    dq.append(S)
    while dq:
        v = dq.popleft()
        for u in g[v]:
            if ~dist[u]: continue
            dist[u] = dist[v] + 1
            dq.append(u)

    if dist[T] % 3:
        print(-1)
        return

    print(dist[T] // 3)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,M = MI()
G = {}
for i in range(1,N+1):
    G[(i,0)] = []
    G[(i,1)] = []
    G[(i,2)] = []
for _ in range(M):
    u,v = MI()
    G[(u,0)].append((v,1))
    G[(u,1)].append((v,2))
    G[(u,2)].append((v,0))

S,T = MI()

flag = [[-1]*3 for i in range(N+1)]

from collections import deque

q = deque([(S,0,0)])  # 頂点、mod 3、Sからの最短距離
while q:
    n,m,r = q.pop()
    for d,e in G[(n,m)]:
        if flag[d][e] != -1:
            continue
        else:
            flag[d][e] = r+1
            q.appendleft((d,e,r+1))

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

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
to = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a].append(b)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Q = deque([(start,0)]) #今の点、何歩目か
visit = [[INF,INF,INF] for _ in range(N)] #三歩目、一歩目、二歩目
visit[start][0] = 0
while Q: #今の点、けんけんぱのどれか、一個前に止まった点
  v,step = Q.popleft()
  now = visit[v][step]
  step = (step+1)%3 #ここでstep+1歩目でvへ行く
  for w in to[v]:
    #print(visit[w][step],step,now)
    if visit[w][step] != INF:
      continue
    Q.append((w,step)) #step歩目でwにいて次vへ行く。
    if step %3 == 0:
      visit[w][step] = min(visit[w][step],now+1)
    else:
      visit[w][step] = min(visit[w][step],now)
#print(visit)
if visit[end][0] == INF:
  ans = -1
else:
  ans = visit[end][0]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
to = [[] for _ in range(N*3)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a*3].append(b*3+1)
  to[a*3+1].append(b*3+2)
  to[a*3+2].append(b*3)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Q = deque([start*3])
visit = [INF for _ in range(N*3)]
visit[start*3] = 0
while Q:
  v = Q.popleft()
  for w in to[v]:
    if visit[w] != INF:
      continue
    visit[w] = visit[v]+1
    if w == end*3:
      print(visit[w]//3)
      exit()
    Q.append(w) #step歩目でwにいて次vへ行く。

#print(visit)
if visit[end*3] == INF:
  ans = -1
else:
  ans = visit[end*3]//3
print(ans)

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

queue = deque()
queue.append((S,0,0))
visited = set()
while queue:
	n, r, d = queue.popleft()
	if n == T and r == 0:
		print(d//3)
		exit()
	nr = (r+1)%3
	for m in E[n]:
		if (m, nr) in visited: continue
		visited.add((m, nr))
		queue.append((m, nr, d+1))
print(-1)