Problem:


Score : 500 points

Problem Statement

Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G.
G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.

First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.

Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq \min(10^5, N (N-1))

1 \leq u_i, v_i \leq N(1 \leq i \leq M)

u_i \neq v_i (1 \leq i \leq M)

If i \neq j, (u_i, v_i) \neq (u_j, v_j).

1 \leq S, T \leq N

S \neq T

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
:
u_M v_M
S T

Output

If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1.
If he can, print the minimum number of ken-ken-pa needed to reach vertex T.

Sample Input 1

4 4
1 2
2 3
3 4
4 1
1 3

Sample Output 1

2

Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.

Sample Input 2

3 3
1 2
2 3
3 1
1 2

Sample Output 2

-1

Any number of ken-ken-pa will bring Ken back to Vertex 1, so he cannot reach Vertex 2, though he can pass through it in the middle of a ken-ken-pa.

Sample Input 3

2 0
1 2

Sample Output 3

-1

Vertex S and Vertex T may be disconnected.

Sample Input 4

6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6

Sample Output 4

2



Sample input:
4 4
1 2
2 3
3 4
4 1
1 3


Sample output:
2

Submission status: Time Limit Exceeded

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

# 再帰処理上限(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)

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

        # ケンケンパ
        ken = point_s[now]
        kenken = [point_s[k] for k in ken]
        kenkenpo = [[point_s[k] for k in ken] for ken in kenken]

        work_s = []
        for kenken in kenkenpo:
            for ken in kenken:
                work_s += ken

        work_s = set(work_s)
        for work in work_s:
            if ans[work] == 999999999:
                ans[work] = ans[now] + 1
                bef[work] = now
                # キューに追加(先頭に追加するのでappendleft())
                que.appendleft(work)
            elif ans[work] > ans[now] + 1:
                bef[work] = 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: Time Limit Exceeded

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

# 再帰処理上限(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)]
    ans[s] = 0
    que = deque()
    que.appendleft(s)

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

        # ケンケンパ
        ken = point_s[now]
        kenken = [point_s[k] for k in ken]
        kenkenpo = [[point_s[k] for k in ken] for ken in kenken]

        work_s = []
        for kenken in kenkenpo:
            for ken in kenken:
                work_s += ken

        work_s = set(work_s)
        for work in work_s:
            # 最短経路なら
            if ans[work] > ans[now] + 1:
                ans[work] = ans[now] + 1
                # キューに追加(先頭に追加するのでappendleft())
                # que.appendleft(work)
                que.append(work)

    if ans[t] == 999999999:
        ans[t] = -1

    print(ans[t])


# テストクラス
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: Time Limit Exceeded

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

# 再帰処理上限(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)]
    ans[s] = 0
    que = deque()
    que.appendleft(s)

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

        # ケンケンパ
        ken = point_s[now]
        kenken = [point_s[k] for k in ken]
        kenkenpo = [[point_s[k] for k in ken] for ken in kenken]

        work_s = []
        for kenken in kenkenpo:
            for ken in kenken:
                work_s += ken

        work_s = set(work_s)
        for work in work_s:
            # 最短経路なら
            if ans[work] > ans[now] + 1:
                ans[work] = ans[now] + 1
                # キューに追加(先頭に追加するのでappendleft())
                que.appendleft(work)

    if ans[t] == 999999999:
        ans[t] = -1

    print(ans[t])


# テストクラス
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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra
    N = N + 1
    u = np.array(u, dtype=np.int32)
    v = np.array(v, dtype=np.int32)
    u = np.concatenate([u, u+N, u+2*N])
    v = np.concatenate([v+N, v+2*N, v])
    mat = dijkstra(csr_matrix((np.ones(3*M), (u, v)), shape=(3*N, 3*N), dtype=np.int32),
                   indices=S, directed=True)
    return -1 if np.isinf(mat[T]) else int(mat[T]) // 3

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]"
    v = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    print(solve(N, M, u, v, S, T))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix


def bfs(cnt, p, cn, row, col, data):
    cnt += 1
    if cnt < 3:
        for cg in graph[p]:
            d.appendleft([cnt, cg])
    if cnt == 3:
        for cg in graph[p]:
            if not cg in graph_k[cn]:
                graph_k[cn].append(cg)
                row = np.append(row, cn)
                col = np.append(col, cg)
                data = np.append(data, 1)
    return cnt, row, col, data

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

row = np.array([], dtype=int)
col = np.array([], dtype=int)
data = np.array([], dtype=int)

d = deque()
graph_k = [[] for i in range(n+1)]
for cn in range(1, n+1):
    for cg in graph[cn]:
        d.appendleft([1, cg])
    while d:
        cnt, p = d.pop()
        cnt, row, col, data = bfs(cnt, p, cn, row, col, data)
# print(graph_k)
csr = csr_matrix((data, (row, col)), shape=(n+1, n+1))
ans = shortest_path(csr, indices=s)
if np.isinf(ans[g]):
    print(-1)
else:
    print(int(ans[g]))

Submission status: Time Limit Exceeded

Solution code:
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 = [0]*self.n
        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
        if not save:
            self.visited = [0] * self.n
        p, t = start, time
        self.visited[p] = 1
        next_set = deque([(p, t)])
        i = 0
        while next_set:
            p, t = next_set.popleft()
            i += 1
            if i > 10**6:
                return -1
            for q in self.edges[p]:
                if (t+1)%3==0:
                    if self.visited[q] == 1:
                        continue
                    if q == goal:
                        return (t+1)//3
                    self.visited[q] = 1
                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: Time Limit Exceeded

Solution code:
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 = [0]*self.n
        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
        if not save:
            self.visited = [0] * self.n
        p, t = start, time
        self.visited[p] = 1
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            if t > 10**6:
                return -1
            for q in self.edges[p]:
                if (t+1)%3==0:
                    if self.visited[q] == 1:
                        continue
                    if q == goal:
                        return (t+1)//3
                    self.visited[q] = 1
                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: Time Limit Exceeded

Solution code:
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 = [0]*self.n
        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
        if not save:
            self.visited = [0] * self.n
        p, t = start, time
        self.visited[p] = 1
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if (t+1)%3==0:
                    if self.visited[q] == 1:
                        continue
                    if q == goal:
                        return (t+1)//3
                    self.visited[q] = 1
                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: Time Limit Exceeded

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

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = set(e[i])
        for _ in range(2):
            nxt = set()
            for __ in items:
                nxt |= set(e[__])
            items = nxt
        items -= {i}
        e3[i] = list(items)

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

    ans = -1
    crnt = set(e3[s])
    if t in crnt:
        print(1)
        exit()

    cnt = 1
    while crnt:
        cnt += 1
        nxt = set()
        for ci in crnt:
            for ti in e3[ci]:
                if visited[ti]:
                    visited[ti] = False
                    nxt.add(ti)
        crnt = nxt
        if t in crnt:
            print(cnt)
            exit()

    print(-1)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = set(e[i])
        for _ in range(2):
            nxt = set()
            for __ in items:
                for ei in e[__]:
                    nxt.add(ei)
            items = nxt
        items -= {i}
        e3[i] = list(items)

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

    ans = -1
    crnt = set(e3[s])
    if t in crnt:
        print(1)
        exit()

    cnt = 1
    while crnt:
        cnt += 1
        nxt = set()
        for ci in crnt:
            for ti in e3[ci]:
                if visited[ti]:
                    visited[ti] = False
                    nxt.add(ti)
        crnt = nxt
        if t in crnt:
            print(cnt)
            exit()

    print(-1)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = set(e[i])
        for _ in range(2):
            nxt = set()
            for __ in items:
                for ei in e[__]:
                    nxt.add(ei)
            items = nxt
        items -= {i}
        e3[i] = list(items)

    ans = -1

    crnt = set(e3[s])
    if t in crnt:
        print(1)
        exit()

    cnt = 1
    while crnt:
        cnt += 1
        nxt = set()
        for ci in crnt:
            nxt |= set(e3[ci])
        crnt = nxt
        if t in crnt:
            print(cnt)
            exit()

    print(-1)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 = [False for _ in range(n)]

    e3 = [[] for _ in range(n)]
    for i in range(n):
        que = collections.deque(e[i])
        for _ in range(2):
            for __ in range(len(que)):
                tmp = que.popleft()
                for ei in e[tmp]:
                    que.append(ei)
        tmp = set(que)
        tmp -= {i}
        e3[i] = list(tmp)

    ans = -1
    cnt = 1
    que = collections.deque(e3[s])

    visited[s] = True
    for ei in e3[s]:
        visited[ei] = True

    finflg = True

    while len(que) and finflg:
        cnt += 1
        for _ in range(len(que)):
            q = que.popleft()
            for ei in e3[q]:
                if not visited[ei]:
                    visited[ei] = True
                    que.append(ei)
                    if ei == t:
                        finflg = False
                        ans = cnt

    print(ans if ans != -1 else -1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    e3 = [[] for _ in range(n)]
    for i in range(n):
        que = collections.deque(e[i])
        for _ in range(2):
            for __ in range(len(que)):
                tmp = que.popleft()
                for ei in e[tmp]:
                    que.append(ei)
        tmp = set(que)
        tmp -= {i}
        e3[i] = list(tmp)

    ans = -1
    cnt = 1
    que = collections.deque(e3[s])
    finflg = True

    while len(que) and finflg and cnt < 10 ** 5+1:

        cnt += 1
        for _ in range(len(que)):
            q = que.popleft()
            for ei in e3[q]:
                que.append(ei)
                if ei == t:
                    finflg = False
                    ans = cnt

    print(ans if ans != -1 else -1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    ans = -1
    que = collections.deque(e[s])
    cnt = 0
    finflg = True
    while len(que) and cnt < 3*10 ** 5 and finflg:
        cnt += 1
        finflg = True

        for _ in range(3):
            for i in range(len(que)):
                nxt = que.popleft()
                if _ == 2 and nxt == t:
                    ans = cnt
                    finflg = False
                for tmp in e[nxt]:
                    que.append(tmp)

    print(-1 if ans == -1 else ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    ans = -1
    que = collections.deque(e[s])
    cnt = 0
    finflg = True
    while len(que) and cnt < 10 ** 6 and finflg:
        cnt += 1
        finflg = True

        for _ in range(3):
            for i in range(len(que)):
                nxt = que.popleft()
                if _ == 2 and nxt == t:
                    ans = cnt
                    finflg = False
                for tmp in e[nxt]:
                    que.append(tmp)

    print(-1 if ans == -1 else ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

#nodes will be (steps % 3) * N + node

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

    start.append(u)
    goal.append(N + v)

    start.append(N + u)
    goal.append(2*N + v)

    start.append(2*N + u)
    goal.append(v)

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

cost = [1] * len(start)
digraph = csr_matrix((cost, (start, goal)), (3*N, 3*N))
ans = dijkstra(digraph, unweighted = True, indices = S-1)[T-1]
if ans == float("inf"):
    print(-1)
else:
    print(int(ans) // 3)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    adj[u-1].append(v-1)
S, T = map(int, input().split())
    
#connect nodes which are 3 steps distant.
start = []
goal = []
for n0 in range(N):
    nodes_1_step  = set(adj[n0])
    nodes_2_steps = set()
    for n1 in nodes_1_step:
        nodes_2_steps |= set(adj[n1])
    nodes_3_steps = set()
    for n2 in nodes_2_steps:
        nodes_3_steps |= set(adj[n2])

    start += [n0] * len(nodes_3_steps)
    goal += list(nodes_3_steps)

cost = [1] * len(start)
digraph = csr_matrix((cost, (start, goal)), (N, N))

ans = dijkstra(digraph, unweighted = True, indices = S-1)[T-1]
    
if ans == float("inf"):
    print(-1)
else:
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:

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

INF = 10 ** 9 + 7
d = [[INF] * 3 for _ in range(N + 1)]
d[S][0] = 0
for _ in range(M):
    for u, v in X:
        for i in range(3):
            if d[u][i] < INF and d[v][(i + 1) % 3] > d[u][i] + 1:
                d[v][(i + 1) % 3] = d[u][i] + 1

if d[T][2] == INF:
    print(-1)
else:
    print(d[T][2])