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:
# coding: utf-8
# Your code here!

N, M = map(int,input().split())
hen = [list(map(int,input().split())) for i in range(M)]
S, T = map(int,input().split())
hen2 = []
for i in range(N):
    a = []
    for j in hen:
        if j[0]==i+1:
            a.append(j[1])
    hen2.append(a)
    
l0 = []
l1 = []
l2 = []
queue = [[S,0,0]]
check = []

while True:
    if queue == []:
        print(-1)
        break
    Now = queue.pop(0)
    if Now[2]>10**3:
        print(-1)
        break
    if Now[0]==T and Now[1]==0:
        print(int(Now[2]/3))
        break
    
    check.append(Now)
    for i in hen2[Now[0]-1]:
        if [i,(Now[1]+1)%3] not in check:
            queue.append([i,(Now[1]+1)%3,Now[2]+1])

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
e=[[] for i in range(10**5)]
ee=[[] for i in range(10**5)]
[n,m]=i2()
for i in range(m):
 [u,v]=i2()
 e[u-1].append(v-1)
 
[s,t]=i2()

d=[-1 for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
d=[-1 for i in range(n)]
def dfs(v,u,uv):
   d[v]=u
   if u==3:
      ee[uv].append(v)
      return 0
   for i in e[v]:
         dfs(i,u+1,uv)
for i in range(n):
 d=[-1 for j in range(n)]
 dfs(i,0,i)
for i in range(n):
   ee[i]=list(set(ee[i]))

d=[-1 for i in range(n)]
def bfs(v):
   d[v]=0
   q=[v]
   while len(q):
    v=q.pop(0)
    for i in ee[v]:
      if d[i]<0:
         d[i]=d[v]+1
         q.append(i)
   print(d[t-1])
bfs(s-1)

Submission status: Time Limit Exceeded

Solution code:
import re

def triple_graph(graph):
    graph_ = dict()
    for i in range(1, N+1):
        graph_[i] = []
        for j in graph[i]:
            for k in graph[j]:
                graph_[i].extend(graph[k])
    return graph_


def bfs(G, S, T): 
    route = [[S]]
    searched = {S}
    count = 0
    searched_pre = {}
    while len(searched_pre) < len(searched):
        searched_pre = searched.copy()
        tmp = []
        for ls in route:
            for i in G[ls[-1]]:
                if i == T:
                    return len(ls)
                else:
                    tmp.append(ls + [i])
                    searched.add(i)
        route = tmp
        count += 1
    return -1

N, M = [int(i) for i in re.split(" ", input())]
G = dict()

for i in range(1, N+1):
    G[i] = []

for i in range(M):
    u, v = [int(i) for i in re.split(" ", input())]
    G[u].append(v)

G = triple_graph(G)

S, T = [int(i) for i in re.split(" ", input())]

print(bfs(G, S, T))

Submission status: Time Limit Exceeded

Solution code:
import re

def triple_graph(graph):
    graph_ = dict()
    for i in range(1, N+1):
        graph_[i] = []
        for j in graph[i]:
            for k in graph[j]:
                graph_[i].extend(graph[k])
    return graph_


def bfs(G, S, T): 
    searched = [[S]]
    count = 0
    while count < len(G):
        tmp = []
        for ls in searched:
            for i in G[ls[-1]]:
                if i == T:
                    return len(ls)
                else:
                    tmp.append(ls + [i])
        searched = tmp
        count += 1
    return -1

N, M = [int(i) for i in re.split(" ", input())]
G = dict()

for i in range(1, N+1):
    G[i] = []

for i in range(M):
    u, v = [int(i) for i in re.split(" ", input())]
    G[u].append(v)

G = triple_graph(G)

S, T = [int(i) for i in re.split(" ", input())]

print(bfs(G, S, T))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import chain


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

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

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

def find_next(pos, e):
    c1 = e[pos]
    c2 = chain.from_iterable([e[c]for c in c1])
    return list(chain.from_iterable([e[c] for c in c2]))

visited = [0 for _ in range(n + 1)]
cost = 0
st = deque([(s, 0)])
ans = -1
pre = None
while len(st):
    pos, cost = st.popleft()
    if pos == t:
        ans = cost
        break
    for n in find_next(pos, edges):
        if visited[n] == 0:
            st.append((n, cost + 1))
            visited[n] = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import chain


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

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


def find_next(pos, e):
    c1 = e[pos]
    c2 = chain.from_iterable([e[c]for c in c1])
    return list(chain.from_iterable([e[c] for c in c2]))


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

visited = [0 for _ in range(n + 1)]
cost = 0
st = deque([(s, 0)])
ans = -1
pre = None
while len(st):
    pos, cost = st.popleft()
    if pos == t:
        ans = cost
        break
    for n in find_next(pos, edges):
        if visited[n] == 0:
            st.append((n, cost + 1))
            visited[n] = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import chain


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

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


def find_next(pos, e):
    c1 = e[pos]
    c2 = list(chain.from_iterable([e[c]for c in c1]))
    return list(chain.from_iterable([e[c] for c in c2]))


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

visited = [0 for _ in range(n + 1)]
cost = 0
st = deque([(s, 0)])
ans = -1
pre = None
while len(st):
    pos, cost = st.popleft()
    visited[pos] = 1
    if pos == t:
        ans = cost
        break
    for n in find_next(pos, edges):
        if visited[n] == 0:
            st.append((n, cost + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mv(nodes,mvinfo):
    dists=set()
    for node in nodes:
        dists=dists | set(mvinfo[node-1])
    return dists


N,M=[int(e) for e in input().split(' ')]

# 1step
mv1=[[] for n in range(N)]

for i in range(M):
    u,v=[int(e) for e in input().split(' ')]
    mv1[u-1].append(v)
S,T=[int(e) for e in input().split(' ')]

# 1step to 3steps
mv3=[]
for i in range(N):
    mv3.append(list(mv(mv(mv1[i],mv1),mv1)))


# search
reached=set()
for i in range(1,1+N):
    if i==1:
        dists=set(mv3[S-1])
    else:
        dists=mv(dists,mv3)

    if T in dists:
        break

else:
    i=-1
print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

N, M = inpl()
uv = [ set() for _ in range(N) ]
for _ in range(M):
    u, v = inpl()
    uv[u-1].add(v-1)
S, T = inpl()
S -= 1
T -= 1

cur = set({S})
for i in range(3*N-2):
    if i % 3 == 0 and T in cur:
        print(i//3)
        break
    prev = cur
    cur = set()
    for p in prev:
        cur |= uv[p]
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

q = queue.Queue()
q.put((S,0))
# Deep First Serch
while q.empty() == False:
    now, cost = q.get()
    for route in routes[now]:
        n_state = (cost + 1) % 3
        if used[route][n_state] == mod:
            used[route][n_state] = cost + 1
            q.put((route,cost+1))
    # state = cost % 3
    # if used[now][state] == mod:
    #     used[now][state] = cost
    #     for route in routes[now]:
    #         q.put((route,cost+1))

# print(used)
try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

q = queue.Queue()
q.put((S,0))
# Deep First Serch
while q.empty() == False:
    now, cost = q.get()
    state = cost % 3
    if used[now,state] == mod:
        used[now,state] = cost
        for route in routes[now]:
            q.put((route,cost+1))

# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = {}
for i in range(N):
    routes[i] = []
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

# def skip(now,move_cnt):
#     flag = True
#     if used[now] != mod:
#         if used[now] % 3 == 0 and move_cnt > used[now]:
#             flag = False
#     if used[now] > move_cnt:
#         if used[now] % 3 == 0 and move_cnt % 3 != 0:
#             pass
#         else:
#             used[now] = move_cnt
#     if flag:
#         for route in routes[now]:
#             skip(route,move_cnt+1)
def move2next(now,move_cnt):
    state = move_cnt % 3
    if used[now][state] == mod:
        used[now][state] = move_cnt
        for route in routes[now]:
            move2next(route,move_cnt+1)
    # if used[now, state] <= move_cnt:
    #     flag = False # この条件だと前より遅いので探索ストップ
    # else:
    #     used[now, state] = move_cnt
    #     for route in routes[now]:
    #         move2next(route, move_cnt+1)


q = queue.Queue()
q.put((S,0))
# Deep First Serch
while q.empty() == False:
    now, cost = q.get()
    state = cost % 3
    if used[now,state] == mod:
        used[now,state] = cost
        for route in routes[now]:
            q.put((route,cost+1))

# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = {}
for i in range(N):
    routes[i] = []
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

# print(routes)
# def skip(now,move_cnt):
#     flag = True
#     if used[now] != mod:
#         if used[now] % 3 == 0 and move_cnt > used[now]:
#             flag = False
#     if used[now] > move_cnt:
#         if used[now] % 3 == 0 and move_cnt % 3 != 0:
#             pass
#         else:
#             used[now] = move_cnt
#     if flag:
#         for route in routes[now]:
#             skip(route,move_cnt+1)
# def move2next(now,move_cnt):
#     state = move_cnt % 3
#     if used[now, state] <= move_cnt:
#         flag = False # この条件だと前より遅いので探索ストップ
#     else:
#         used[now, state] = move_cnt
#         for route in routes[now]:
#             move2next(route, move_cnt+1)


q = queue.Queue()
q.put((S,0))
# Deep First Serch
def move2next(q):
    while q.qsize() > 0:
        now,cost = q.get()
        state = cost % 3
        if used[now, state] <= cost:
            pass
        else:
            used[now, state] = cost
            for route in routes[now]:
                q.put((route,cost+1))



move2next(q)
# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7



import collections
import heapq

class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)


    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])


    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]


    def Dijkstra_search(self, s):
        """
        0-indexedでなくてもよいことに注意
        s = 始点
        return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:  # DefaulfではFalseとなる
                continue


            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))


        return d



def main(): 
    # ダイクストラ法を用いて回答する。
    N, M = LI()
    graph = []
    from collections import defaultdict
    reversed_graph_dict = defaultdict(list)
    for _ in range(M):
        u, v = LI()
        graph.append([u,v])
        reversed_graph_dict[v].append(u)
    S, T = LI()

    dij = Dijkstra()

    # 三段先のグラフを先に作っておく。
    three_steps_dict = defaultdict(list)
    for i in range(1, N+1):
        added = set()
        first_step = reversed_graph_dict[i]
        second_step = []
        for x in first_step:
            second_step += reversed_graph_dict[x]
        third_step = []
        for x in set(second_step):
            for y in reversed_graph_dict[x]:
                if (i,y) not in added:
                    dij.add(i,y,1,directed=True)
                    added.add((i,y))

    ans = dij.Dijkstra_search(s=T)[S]
    print(ans if ans != float('inf') else -1)



main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7



import collections
import heapq

class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)


    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])


    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]


    def Dijkstra_search(self, s):
        """
        0-indexedでなくてもよいことに注意
        s = 始点
        return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:  # DefaulfではFalseとなる
                continue


            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))


        return d



def main(): 
    # ダイクストラ法を用いて回答する。
    N, M = LI()
    graph = []
    from collections import defaultdict
    reversed_graph_dict = defaultdict(list)
    for _ in range(M):
        u, v = LI()
        graph.append([u,v])
        reversed_graph_dict[v].append(u)
    S, T = LI()

    dij = Dijkstra()

    # 三段先のグラフを先に作っておく。
    three_steps_dict = defaultdict(list)
    for i in range(1, N+1):
        added = set()
        first_step = reversed_graph_dict[i]
        second_step = []
        for x in first_step:
            second_step += reversed_graph_dict[x]
        third_step = []
        for x in set(second_step):
            for y in set(reversed_graph_dict[x]):
                if (i,y) not in added:
                    dij.add(i,y,1,directed=True)
                    added.add((i,y))

    ans = dij.Dijkstra_search(s=T)[S]
    print(ans if ans != float('inf') else -1)



main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7



import collections
import heapq

class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)


    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])


    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]


    def Dijkstra_search(self, s):
        """
        0-indexedでなくてもよいことに注意
        s = 始点
        return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:  # DefaulfではFalseとなる
                continue


            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))


        return d



def main(): 
    # ダイクストラ法を用いて回答する。
    N, M = LI()
    graph = []
    from collections import defaultdict
    reversed_graph_dict = defaultdict(list)
    for _ in range(M):
        u, v = LI()
        graph.append([u,v])
        reversed_graph_dict[v].append(u)
    S, T = LI()

    dij = Dijkstra()

    # 三段先のグラフを先に作っておく。
    three_steps_dict = defaultdict(list)
    for i in range(1, N+1):
        first_step = reversed_graph_dict[i]
        second_step = []
        for x in first_step:
            second_step += reversed_graph_dict[x]
        third_step = []
        for x in set(second_step):
            for y in set(reversed_graph_dict[x]):
                dij.add(i,y,1,directed=True)

    ans = dij.Dijkstra_search(s=T)[S]
    print(ans if ans != float('inf') else -1)



main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if sss[now][nn] == Max:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

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

U = []
V = []
for u, v in UV:
    U.extend([u, u + N, u + N * 2])
    V.extend([v + N, v + N * 2, v])

graph = csr_matrix(([1] * (M * 3), (U, V)), shape=(N * 3 + 1, N * 3 + 1))
dist = dijkstra(graph, indices=S)[T]
if dist < np.inf:
    print(int(dist // 3))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = {}
for i in range(N):
    routes[i] = []
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

# print(routes)
# def skip(now,move_cnt):
#     flag = True
#     if used[now] != mod:
#         if used[now] % 3 == 0 and move_cnt > used[now]:
#             flag = False
#     if used[now] > move_cnt:
#         if used[now] % 3 == 0 and move_cnt % 3 != 0:
#             pass
#         else:
#             used[now] = move_cnt
#     if flag:
#         for route in routes[now]:
#             skip(route,move_cnt+1)
def move2next(now,move_cnt):
    state = move_cnt % 3
    if used[now, state] <= move_cnt:
        flag = False # この条件だと前より遅いので探索ストップ
    else:
        used[now, state] = move_cnt
        for route in routes[now]:
            move2next(route, move_cnt+1)

move2next(S,0)
# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

# print(routes)
# def skip(now,move_cnt):
#     flag = True
#     if used[now] != mod:
#         if used[now] % 3 == 0 and move_cnt > used[now]:
#             flag = False
#     if used[now] > move_cnt:
#         if used[now] % 3 == 0 and move_cnt % 3 != 0:
#             pass
#         else:
#             used[now] = move_cnt
#     if flag:
#         for route in routes[now]:
#             skip(route,move_cnt+1)
def move2next(now,move_cnt):
    state = move_cnt % 3
    if used[now, state] <= move_cnt:
        flag = False # この条件だと前より遅いので探索ストップ
    else:
        used[now, state] = move_cnt
        for route in routes[now]:
            move2next(route, move_cnt+1)

move2next(S,0)
# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()
S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

# print(routes)
# def skip(now,move_cnt):
#     flag = True
#     if used[now] != mod:
#         if used[now] % 3 == 0 and move_cnt > used[now]:
#             flag = False
#     if used[now] > move_cnt:
#         if used[now] % 3 == 0 and move_cnt % 3 != 0:
#             pass
#         else:
#             used[now] = move_cnt
#     if flag:
#         for route in routes[now]:
#             skip(route,move_cnt+1)
def move2next(now,move_cnt):
    flag = True
    if used[now, move_cnt % 3] == mod:
        used[now, move_cnt % 3] = move_cnt
    elif used[now, move_cnt % 3] <= move_cnt:
        flag = False # この条件だと前より遅いので探索ストップ
    else:
        used[now, move_cnt % 3] = move_cnt
    if flag:
        for route in routes[now]:
            move2next(route, move_cnt+1)

move2next(S,0)
# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()
S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

# print(routes)
# def skip(now,move_cnt):
#     flag = True
#     if used[now] != mod:
#         if used[now] % 3 == 0 and move_cnt > used[now]:
#             flag = False
#     if used[now] > move_cnt:
#         if used[now] % 3 == 0 and move_cnt % 3 != 0:
#             pass
#         else:
#             used[now] = move_cnt
#     if flag:
#         for route in routes[now]:
#             skip(route,move_cnt+1)
def move2next(now,move_cnt):
    flag = True
    if used[now][move_cnt % 3] == mod:
        used[now][move_cnt % 3] = move_cnt
    elif used[now][move_cnt % 3] <= move_cnt:
        flag = False # この条件だと前より遅いので探索ストップ
    else:
        used[now][move_cnt % 3] = move_cnt
    if flag:
        for route in routes[now]:
            move2next(route, move_cnt+1)

move2next(S,0)
# print(used)
try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))