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 fractions import gcd
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, m = LI()
    g = [set() for i in range(n+1)]
    new_g = [set() for i in range(n+1)]
    new_gg = [set() for i in range(n+1)]
    for i in range(m):
        u, v = LI()
        g[u].add(v)
    s, t = LI()
    for i in range(n+1):
        new = set()
        for j in g[i]:
            new = new | g[j]
        new_g[i] = new_g[i] | new

    for i in range(n+1):
        new = set()
        for j in new_g[i]:
            new = new | g[j]
        new_gg[i] = new_gg[i] | new

    last = [list(i) for i in new_gg]

    Q = deque([s])
    searched = [0 for i in range(n+1)]
    searched[s] = 1
    depth = [0 for i in range(n+1)]
    while len(Q) != 0:
        v = Q.popleft()
        for i in last[v]:
            if i == t:
                depth[i] = depth[v] + 1
                print(depth[i])
                return
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[set() for j in range(N)] for i in range(3)]
for u,v in UV:
    es[0][u].add(v)

nex = {}
for i in range(2):
    for j in range(N):
        if hash(tuple(es[i][j])) in nex:
            es[i+1][j] = nex[hash(tuple(es[i][j]))]
            continue
        for k in es[i][j]:
            es[i+1][j] |= es[0][k]
        nex[hash(tuple(es[i][j]))] = es[i+1][j]

INF = float('inf')
dist = [INF]*N
dist[S] = 0
q = deque([S])
while q:
    v = q.popleft()
    for to in es[2][v]:
        if dist[to] != INF: continue
        dist[to] = dist[v]+1
        if to == T:
            print(dist[to])
            exit()
        q.append(to)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i in visited:
            continue
        visited.add(i)
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        if t in b:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(b)]
    return -1


print(BC132_E())

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 = [-1 for i in range(N)]

# print(routes)
def skip(now,move_cnt):
    flag = True
    if move_cnt % 3 == 0:
        if used[now] == -1:
            used[now] = move_cnt//3
        elif used[now] > move_cnt//3:
            used[now] = move_cnt//3
        else:
            flag = False
    if flag:
        for route in routes[now]:
            skip(route,move_cnt+1)

skip(S,0)
try:
    ans = used[T]
except:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
link = {i: [] for i in range(1, N+1)}
for _ in range(M):
    u, v = map(int, input().split())
    link[u].append(v)
S, T = map(int, input().split())

''' dijkstra '''
INF = 10 ** 9
vstd = {i: False for i in range(1, N+1)}
dist = {i: INF for i in range(1, N+1)}  # distance
# prev = {i: -1 for i in range(1, N+1)}  # for extract min cost path
pq = []
# initialize
dist[S] = 0
heappush(pq, (0, S))
while pq:
    _, u = heappop(pq)
    vstd[u] = True
    for v in link[u]:
        # if vstd[v]:
        #     continue
        for w in link[v]:
            # if vstd[w]:
            #     continue
            for x in link[w]:
                if vstd[x]:
                    continue
                if dist[u] + 1 < dist[x]:
                    dist[x] = dist[u] + 1
                    # prev[v] = u
                    heappush(pq, (dist[x], x))

print(dist[T] if dist[T] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))

to = [[] for i in range(0, n)]
for i in range(0, m):
    u, v = list(map(int, input().split()))
    to[u-1].append(v-1)

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

dist = [[-1, -1, -1] for i in range(0, n)]
queue = []

dist[s][0] = 0
for v in to[s]:
    queue.append([v, 1])

while queue != []:
    x = queue.pop()
    if not 0 <= dist[x[0]][x[1]%3] <= x[1]:
        dist[x[0]][x[1]%3] = x[1]
        for v in to[x[0]]:
            queue.append([v, x[1]+1])

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

Submission status: Time Limit Exceeded

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

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

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = [St-1]
hoge = [0]*N
for i in range(1,N*3+3):
    l = 0
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > i:
                D[s][i%3] = i
                if not s in hoge[:l]:
                    hoge[l] = s
                    l += 1
    queue = hoge[:l]
    if D[T-1][0] != float('inf'):
        break
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

words = lambda t : list(map(t, input().split()))


def dfs(ns,s,t):
    n_steps = [[-1] * len(ns) for i in range(3)]
    def search(i, step):
        #print(i, step, n_steps)
        j = step % 3
        if n_steps[j][i] == -1 or (n_steps[j][i] > step):
            n_steps[j][i] = step
            for next in ns[i]:
                search(next, step+1)

    search(s, 0)
    if n_steps[0][t] == -1:
        print(-1)
    else:
        print(n_steps[0][t] // 3)

def main():
    n,v = words(int)
    ns = [[] for _ in range(n)]
    for _ in range(v):
        (st,end) = map(int,input().split())
        ns[st-1].append(end - 1)
    s,t = words(int)
    dfs(ns,s-1,t-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
import heapq
N, M = map(int, input().split())

edges1 = dd(dict)
edges3 = dd(dict)
for _ in range(M):
  f, t = map(int, input().split())
  edges1[f][t] = 1

S, T = map(int, input().split())
q = set([(S,S,0)])
while q:
  f, t, d = q.pop()
  if d < 2:
    for t2 in edges1[t].keys():
      q.add((f, t2, d+1))
  else:
    for t2 in edges1[t].keys():
      if t2 in edges3[f]:
        continue
      edges3[f][t2] = 1
      q.add((t2, t2, 0))

# 幅優先
end = set()
q = set([S])
ans = 0
while q:
  nq = set()
  for f in q:
    if f == T:
      print(ans)
      exit()
    end.add(f)
    for t in edges3[f].keys():
      if t not in end:
        nq.add(t)
  q = nq
  ans += 1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N,M=rl()
S1 = [set() for _ in range(N+1)]
S2 = [set() for _ in range(N+1)]
S3 = [set() for _ in range(N+1)]
for i in range(M):
    u,v=rl()
    S1[u].add(v)
S,T=rl()

for i in range(1,N+1):
    S_ = S1[i]
    if len(S_) != 0:
        for s in S_:
            S2[i] = S2[i] | S1[s]
for i in range(1,N+1):
    S_ = S2[i]
    if len(S_) != 0:
        for s in S_:
            S3[i] = S3[i] | S1[s]

ans = -1
R = [INF for _ in range(N+1)]
R[S] = 0
import heapq
Se = []
heapq.heappush(Se,(0,S))
Sel = 1
L = set()
while Sel>0:
    node_m, node = heapq.heappop(Se)
    Sel -= 1
    for node_s in S3[node]:
        if node_m+1 < R[node_s]:
            R[node_s] = node_m + 1
            heapq.heappush(Se,(node_m+1,node_s))
            Sel += 1

if R[T] != INF:
    ans = R[T]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
INF = 10 ** 12

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

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

vec_ = [[] for _ in range(N)]
for i in range(N) :
    queue = deque([(0, i)])
    while queue :
        step, q = queue.popleft()
        if step == 2 : 
            for j in vec[q] :
                vec_[i].append(j)
        else :
            for j in vec[q] :
                queue.append((step + 1, j))
      
visited = [False] * N
visited[S] = True
queue = deque([(0, S)])
while queue :
    step, q = queue.popleft()
    for i in vec_[q] :
        if i == T :
            print(step+1)
            exit()
        
        if not visited[i] :
            queue.append((step + 1, i))
            visited[i] = True

print(-1)

Submission status: Time Limit Exceeded

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

import sys
import numpy as np
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
UV = np.array([input().split() for _ in range(M)], dtype=np.int32)
U = UV[:,0] * 3
V = UV[:,1] * 3
S,T = map(int,input().split())

rows = np.zeros(3*M, dtype=np.int32)
cols = np.zeros(3*M, dtype=np.int32)

rows[:M] = U
rows[M:2*M] = U + 1
rows[2*M:] = U + 2
cols[:M] = V + 1
cols[M:2*M] = V + 2
cols[2*M:] = V

graph = csr_matrix((np.ones_like(rows), (rows, cols)), (3*N+3, 3*N+3))
dist = csgraph.dijkstra(graph, indices = 3*S, unweighted=True)

answer = -1 if dist[3*T] > 3*N else int(dist[3*T]//3)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

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

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

graph_ken = [None]*(N+1)
for i in range(1, N+1):
    now = i
    queue = graph[now][:]
    for _ in range(2):
        nextqueue = []
        for next in queue:
            nextqueue.extend(graph[next])
        queue = f7(nextqueue)
    graph_ken[i] = queue



queue = [S]
visit = [False]*(N+1)
ans = 0
while len(queue) > 0:
    nextqueue = set([])
    for now in queue:
        if visit[now]:
            continue
        visit[now] = True
        for next in graph_ken[now]:
            if not visit[next]:
                nextqueue.add(next)
    queue = f7(nextqueue)
    if visit[T]:
        break
    ans += 1

if visit[T]:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

inf = 10 ** 6

def main():
    n, m = [int(i) for i in sys.stdin.readline().strip().split()]
    edges = [tuple(int(i) for i in sys.stdin.readline().strip().split()) for j in range(m)]
    e_dict = {i: [] for i in range(1, n+1)}
    s, t = [int(i) for i in sys.stdin.readline().strip().split()]

    for a, b in edges:
        e_dict[a].append(b)

    ret = -1
    loop = 0
    log = [-1] + [10 ** 8] * n
    que = []
    que.append((s, 0))
    log[s] = 0
    while len(que):
        loop += 1
        if loop > inf:
            break
        nod, st = que.pop(0)
        log[nod] = st
        if nod == t and st % 3 == 0:
            ret = st // 3
            break
        for u in e_dict[nod]:
            if log[u] == 10**8 or log[u] % 3 != (st+1) % 3:
                que.append((u, st+1))
    return ret
    
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
d = [[] for i in range(n)]

for i in range(m):
    u,v = na()
    d[u-1].append(v-1)

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

g = [-1 for i in range(n)]
b = 10000000000

def dfs(a,k):
    global b
    if k+1 < b:
        for p in d[a]:
            for q in d[p]:
                for r in d[q]:
                    if g[r] >= 0 and g[r] < k+1:
                        break
                    g[r] = k+1
                    if r == t:
                        b = k+1
                        break
                    dfs(r,k+1)

dfs(s,0)
print(g[t])

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = [[] for _ in range(N)]
    for _ in range(M):
        u,v = MI_()
        edge[u].append(v)
    S, T = MI_()

    queue = [S]
    checked = set()
    for i in range(1,max(3*N,3*M+2)):
        tmp = set()
        while queue:
            s = queue.pop()
            for to in edge[s]:
                if to == T:
                    if i%3==0:
                        print(i//3)
                        exit()
                tmp.add(to)
        queue = tmp
    print(-1)
            

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue as q

N, M = list(map(int, input().split()))
D = {n: set() for n in range(N)}
for m in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    D[u].add(v)

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

def f():
    close = [set(), set(), set()]
    Q = q.Queue()
    Q.put((S, 0, 0))

    while not Q.empty():
        p, c, l = Q.get()
        if l % 3 == 0 and p == T:
            return c
        close[l].add(p)

        ns = D[p]
        l, c = (l + 1) % 3, c + (l + 1) // 3
        for n in ns:
            if n in close[l]:
                continue
            Q.put((n, c, l))

    return -1

print(f())

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict

from functools import lru_cache

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

graph = defaultdict(set)
for u, v in UV:
    graph[u].add(v)


@lru_cache(maxsize=None)
def dest(v, count):
    if count <= 1:
        return graph[v]
    ret = set()
    for u in graph[v]:
        ret |= dest(u, count - 1)
    return ret


checked = set()
vs = {S}
i = 0
prev = 0
while True:
    i += 1
    s = set()
    for v in vs:
        s |= dest(v, 3)
    checked |= vs
    if T in s:
        print(i)
        break
    if len(checked) == prev:
        print(-1)
        break
    vs = s - checked
    prev = len(checked)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N,M=rl()
S1 = [set() for _ in range(N+1)]
S2 = [set() for _ in range(N+1)]
S3 = [set() for _ in range(N+1)]
for i in range(M):
    u,v=rl()
    S1[u].add(v)
S,T=rl()

for i in range(1,N+1):
    S_ = S1[i]
    if len(S_) != 0:
        for s in S_:
            S2[i] = S2[i] | S1[s]
for i in range(1,N+1):
    S_ = S2[i]
    if len(S_) != 0:
        for s in S_:
            S3[i] = S3[i] | S1[s]

ans = -1
R = [INF for _ in range(N+1)]
R[S] = 0
import heapq
Se = []
heapq.heappush(Se,(0,S))
L = set()
while len(Se)>0:
    node_m, node = heapq.heappop(Se) 
    for node_s in S3[node]:
        if node_m+1 < R[node_s]:
            R[node_s] = node_m + 1
            heapq.heappush(Se,(node_m+1,node_s))

if R[T] != INF:
    ans = R[T]

print(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):
    routes[i] = []
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = {}
for i in range(N):
    used[i] = -1

# print(routes)
def skip(now,move_cnt):
    flag = True
    if move_cnt % 3 == 0:
        if used[now] == -1:
            used[now] = move_cnt//3
        elif used[now] > move_cnt//3:
            used[now] = move_cnt//3
        else:
            flag = False
    if flag:
        for route in routes[now]:
            skip(route,move_cnt+1)

skip(S,0)
try:
    ans = used[T]
except:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

path_list = [[] for _ in range(n)]

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

s, t = map(int, input().split())
s -= 1
t -= 1
i = 0
dp = [[] for _ in range(3*n)]
dp[0].append(s)
while i < 3*n-1:
  a = set()
  for dot in dp[i]:
    a |= set(path_list[dot])
  if not -~i%3 and t in a:
    print(-~i//3)
    exit()
  dp[i+1] = a
  i += 1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self, i):
        self.num = i
        self.goto = []
        self.kenken = set()

N, M = map(int, input().split())
nodes = [Node(i+1) for i in range(N)]

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

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

for i in range(N):
    for next in nodes[i].goto:
        for nextnext in next.goto:
            nodes[i].kenken = nodes[i].kenken | set(nextnext.goto)
    if nodes[i] in nodes[i].kenken:
        nodes[i].kenken.remove(nodes[i])

node = nodes[t]
step = 0
hist = [nodes[t].num]
check_list = [[node, step, hist]]
ok = False
while len(check_list) > 0:
    node, step, tmp = check_list.pop(0)
    hist = tmp
    if node == nodes[s]:
        print(step)
        ok = True
        break
    for next in node.kenken:
        if next.num not in hist:
            check_list.append([next, step+1, hist+[next.num]])
if not ok:
    print(-1)

Submission status: Time Limit Exceeded

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

import sys
import numpy as np
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
UV = np.array([input().split() for _ in range(M)], dtype=np.int32)
U = UV[:,0] * 3
V = UV[:,1] * 3
S,T = map(int,input().split())

rows = np.zeros(3*M, dtype=np.int32)
cols = np.zeros(3*M, dtype=np.int32)

rows[:M] = U
rows[M:2*M] = U + 1
rows[2*M:] = U + 2
cols[:M] = V + 1
cols[M:2*M] = V + 2
cols[2*M:] = V

graph = csr_matrix((np.ones_like(rows), (rows, cols)), (3*N+3, 3*N+3))
dist = csgraph.dijkstra(graph, indices = 3*S)

answer = -1 if dist[3*T] > 3*N else int(dist[3*T]//3)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

import sys

def getVertex(i,e):
    v= set()
    for v1 in e[i]:
        for v2 in e[v1]:
            for v3 in e[v2]: v.add( v3 )
    #
    return v
#
n,m = [ int(x) for x in sys.stdin.readline().split() ]
e = { i:[] for i in range(n) }
for _ in range(m):
    u,v = [ int(x) for x in sys.stdin.readline().split() ]
    e[u-1].append( v-1 )
s,t = [ int(x)-1 for x in sys.stdin.readline().split() ]
#
kkp= { i:[] for i in range(n) }
#
hop= 0
now = {s}
visit = {s}
while True:
    hop+= 1
    n= set()
    for i in now:
        n |= getVertex(i,e) - visit
    #
    if t in n: break
    if not n:
        hop= -1
        break
    now = n
#
print( hop )

Submission status: Time Limit Exceeded

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

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

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = [St-1]
hoge = [0]*N
for i in range(1,N*3+3):
    l = 0
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > i:
                D[s][i%3] = i
                if not s in hoge[:l]:
                    hoge[l] = s
                    l += 1
    queue = hoge[:l]
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


# 無向グラフを仮定する。
class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v1, w1 in g.E[u]:
            for v2, w2 in g.E[v1]:
                for v3, w3 in g.E[v2]:
                    if dist[v3] > dist[u]+1:
                        dist[v3] = dist[u]+1
                        prev[v3] = u
                        heapq.heappush(Q, (dist[v3], v3))
    return dist, prev


def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    # グラフを2つ作る。枝の向きが逆向き。
    g1 = Graph(N)
    for from_, to_ in zip(u, v):
        g1.add_edge((from_-1, to_-1, 1))

    dist1, prev1 = shortestPath(g1, S-1)
    # print(dist1)
    if dist1[T-1] == INF:
        print(-1)
    else:
        print(dist1[T-1])

    return


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
    solve(N, M, u, v, S, T)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[set() for j in range(N)] for i in range(3)]
for u,v in UV:
    es[0][u].add(v)

nex = {}
for i in range(2):
    for j in range(N):
        if hash(str(es[i][j])) in nex:
            es[i+1][j] = nex[hash(str(es[i][j]))]
            continue
        for k in es[i][j]:
            es[i+1][j] |= es[0][k]
        nex[hash(str(es[i][j]))] = es[i+1][j]

INF = float('inf')
dist = [INF]*N
dist[S] = 0
q = deque([S])
while q:
    v = q.popleft()
    for to in es[2][v]:
        if dist[to] != INF: continue
        dist[to] = dist[v]+1
        if to == T:
            print(dist[to])
            exit()
        q.append(to)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
N,M = map(int,input().split())
V = [[]for i in range(N+1)]
for i in range(M):
    u,v = map(int,input().split())
    V[u].append(v)
S,T = map(int,input().split())
A = set([S])
ans = 0
while True:
    ans += 1
    for i in range(3):
        B = set()
        for v in A:
            B = B | set(V[v])
        A = B
    if len(A)==0 or A == set([S]):
        ans = -1
        break
    elif T in A:
        break
print(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):
    routes[i] = []
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = {}
for i in range(N):
    used[i] = -1

# print(routes)
def skip(now,move_cnt):
    flag = True
    if move_cnt % 3 == 0:
        if used[now] == -1:
            used[now] = move_cnt//3
        elif used[now] > move_cnt//3:
            used[now] = move_cnt//3
        else:
            flag = False
    if flag:
        for route in routes[now]:
            skip(route,move_cnt+1)


skip(S,0)
# print(used)
try:
    ans = used[T]
except:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def sol(inp=input):
    n,m=map(int,inp().split())
    G={i+1:set() for i in range(n)}
    for _ in range(m):
        i,j=map(int,inp().split())
        G[i].add(j)
    s,t=map(int,inp().split())
    cache_kenken={}
    def kenken(v):
        if v not in cache_kenken:
            cache_kenken[v]=set(v2 for v1 in G[v] for v2 in G[v1])
        return cache_kenken[v]
    def kenkenpa(v):
        return set(v3 for v2 in kenken(v) for v3 in G[v2])
    visited={s}
    revisited=set()
    v_steps=[]
    visited_pa={s}
    que=[]
    heapq.heappush(que,(0,s))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in kenkenpa(u):
            if v not in visited:
                visited.add(v)
                v_steps.append((step+1,v))
                heapq.heappush(que,(step+1,v))
            if v==t:
                return step+1
            if v not in visited:
                visited.add(v)
    return -1
print(sol())

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int,input().split())
edge = [[] for i in range(N)]
double_edge = [[] for i in range(N)]
triple_edge = [[] for i in range(N)]

for i in range(M):
	u,v = map(int,input().split())
	u -= 1
	v -= 1
	edge[u].append(v)
S,T = map(int,input().split())
S -= 1
T -= 1
for i in range(N):
	e = edge[i]
	l = []
	for x in e:
		l += edge[x]
	double_edge[i] = list(set(l))
for i in range(N):
	e = edge[i]
	l = []
	for x in e:
		l += double_edge[x]
	l = list(set(l))
	if i in l:
		l.remove(i)
	triple_edge[i] = l

INF = 10**10
dist = [INF if i != S else 0 for i in range(N)]
search = []
searched = [False for i in range(N)]
heapq.heapify(search)
heapq.heappush(search, (0,S))
while len(search) > 0 and dist[T] == INF:
	x = heapq.heappop(search)
	d, node = x[0], x[1]
	if searched[node]:
		continue
	searched[S] = True
	dist[node] = d
	for i in triple_edge[node]:
		if not searched[i]:
			heapq.heappush(search, (min(d+1, dist[i]), i))
if dist[T] < INF:
	print(dist[T])
else:
	print(-1)