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
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
Se = set([S])
L = set()
while len(Se)>0:
    node = 0
    node_m = INF
    for Se_ in Se:
        if node_m > R[Se_]:
            node = Se_
            node_m = R[Se_]
    Se.discard(node)
    for node_s in S3[node]:
        if node_m+1 < R[node_s]:
            R[node_s] = node_m + 1
            Se.add(node_s)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,M = (int(x) for x in input().split())
v_dict = {}
for _ in range(M):
    u,v = (int(x) for x in input().split())
    v_dict.setdefault(u, set())
    v_dict[u].add(v)
S,T = (int(x) for x in input().split())

v2_dict = {}
for n in v_dict.keys():
    tmp = set()
    for v in v_dict[n]:
        tmp |= v_dict.get(v, set())
    v2_dict[n] = tmp
v3_dict = {}
for n in v_dict.keys():
    tmp = set()
    for v in v_dict[n]:
        tmp |= v2_dict.get(v, set())
    v3_dict[n] = tmp

visited = set()
found = set()

if S == T:
    print("0")
    exit()

nsteps = 1
current_node = [S]
next_node = []
while(True):
    if len(current_node) == 0:
        print("-1")
        exit()
    for n in current_node:
        neighs = v3_dict.get(n, set())
        for neigh in neighs:
            if neigh == T:
                print(nsteps)
                exit()
            if neigh in found:
                continue
            next_node.append(neigh)
            found.add(neigh)
    nsteps += 1
    current_node = next_node
    next_node = []

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)

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

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

INF = float('inf')
memo = [[INF for _ in range(n)] for i in range(3)]

def dfs(v, mod, dist):
    if dist < memo[mod][v]:
        memo[mod][v] = dist
        for nv in g[v]:
            if dist >= memo[(mod+1)%3][nv]:
                continue
            dfs(nv, (mod+1)%3, dist+1)


dfs(s, 0, 0)
if memo[0][t] == INF:
    print(-1)
else:
    print(memo[0][t]//3)

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

graph_ken = [[]]
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 = list(set(nextqueue))
    graph_ken.append(queue)



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

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    G[u].add(v)
S,T=map(int,input().split())
A=[set() for i in range(N)]
for i in range(N):
    for v in G[i]:
        A[i]=A[i] | G[v]
B=[set() for i in range(N)]
for i in range(N):
    for v in G[i]:
        B[i]=B[i] | A[v]
C=[[] for i in range(N)]
for i in range(N):
    for j in B[i]:
        C[i].append([j,1])
INF=10**9+7
def dijkstra(G,s):

  d=[INF]*N
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d
d=dijkstra(C,S-1)
if d[T-1]==INF:
  print(-1)
else:
  print(d[T-1])

Submission status: Time Limit Exceeded

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

import sys
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
U,V = [],[]
for _ in range(M):
  u,v = map(int,input().split())
  U.append(u)
  V.append(v)
S,T = map(int,input().split())


# ken
rows = [3*u for u in U]
cols = [3*v+1 for v in V]
# ken
rows += [3*u+1 for u in U]
cols += [3*v+2 for v in V]
# pa
rows += [3*u+2 for u in U]
cols += [3*v for v in V]

graph = csr_matrix(([1] * len(rows), (rows, cols)), (3*N+3, 3*N+3))
dist = csgraph.dijkstra(graph, indices = 3*S)

# 着地地点に制限
dist = dist[::3]

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

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] > D[q][(i-1)%3]:
                D[s][i%3] = D[q][(i-1)%3]+1
                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:
import sys, collections

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    son = [[] for i in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        son[u-1].append(v-1)
    S, T = map(int, input().split())

    graphB = [[] for i in range(N)] 
    for i in range(N):
        for s1 in son[i]:
            for s2 in son[s1]:
                for s3 in son[s2]: graphB[i].append(s3)
    
    q = collections.deque()
    visited = [-1] * N
    q.append((0, S-1))
    while q:
        cost, now = q.popleft()
        if visited[now] == -1:
            visited[now] = cost
            for s in graphB[now]:
                if visited[s] == -1: q.append((cost + 1, s))

    print(visited[T-1])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10000000)

readline = sys.stdin.readline

N, M = map(int, readline().split())
uv = [list(map(int, readline().split())) for i in range(M)]
S, T = map(int, readline().split())

S, T = S - 1, T - 1

nodes = [{} for i in range(N)]
for u, v in uv:
    nodes[u - 1][v - 1] = 1

visited = [False] * N

def kenken(u, rem):
    if rem > 0:
        a = []
        for v in nodes[u]:
            a += kenken(v, rem - 1)
        return a
    else:
        return [u]
    

q = deque()

q.append([S, 0])

_count = -1
while len(q) != 0:
    u, count = q.popleft()
    if not visited[u]:
        visited[u] = True

        ret = kenken(u, 3)
        if any(T == r for r in ret):
            _count = count + 1
            break
        q.extend([r, count + 1] for r in ret)


print(_count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


conn = {}
N, M = map(int, input().split())
for _ in range(M):
    u, v = map(int, input().split())
    if u not in conn:
        conn[u] = set()
    conn[u].add(v)
S, T = map(int, input().split())


def get(dic, key):
    return dic[key] if key in dic else []


def hop3(n):
    ans = set()
    n1 = n
    for n2 in get(conn, n1):
        for n3 in get(conn, n2):
            for n4 in get(conn, n3):
                ans.add(n4)
    return ans


q = deque()
q.append(S)
dp = [-1] * (N + 1)
dp[S] = 0


while len(q) > 0:
    n = q.popleft()
    for m in hop3(n):
        if dp[m] < 0:
            dp[m] = dp[n] + 1
            if m == T:
                print(dp[m])
                exit()
            q.append(m)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.getrecursionlimit()

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

graph1 = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]

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


def dfs(v0, v, k):
    if k == 0:
        graph2[v0].append((1, v))
        return

    for i in range(len(graph1[v])):
        dfs(v0, graph1[v][i][1], k-1)

for i in range(n):
    dfs(i, i, 3)
    # print(graph1[i])

for i in range(n):
    graph2[i] = list(set(graph2[i]))
# print()
# for i in range(n):
#     print(graph2[i])


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


from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

inf = float('inf')
dist = dijkstra(graph2, n, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict

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

# 3 つ先の頂点同士を結んだグラフを作って最短距離

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

v1 = graph.copy()
# 2回で行ける
v2 = defaultdict(set)
for u, vs in graph.items():
    for v in vs:
        v2[u] |= v1[v]
# 3回
v3 = defaultdict(set)
for u, vs in v2.items():
    for v in vs:
        v3[u] |= v1[v]

fixed = {S}
vs = {S}
i = 0
prev = 1
while True:
    i += 1
    s = set()
    for v in vs:
        s |= v3[v]
    if T in s:
        print(i)
        break
    fixed |= s
    if len(fixed) == prev:
        print(-1)
        break
    vs = s
    prev = len(fixed)

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

    def dfs(now, cnt,ends):
        if cnt == 3:
            ends.append(now)
            return 
        for to in edge[now]:
            #print(cnt,now,to)
            dfs(to, cnt + 1,ends)
            


    edge2 = [[] for _ in range(N)]
    for sor in range(N):
        end = []
        dfs(sor, 0,end)
        edge2[sor] = end

    queue = [S]
    checked = set()
    for i in range(1,M+2):
        tmp = set()
        while queue:
            s = queue.pop()
            for to in edge2[s]:
                if to == T:
                    print(i)
                    exit()
                else:
                    if to not in checked:
                        tmp.add(to)
                        checked.add(to)
        queue = tmp
    print(-1)
            

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.getrecursionlimit()

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

graph1 = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]

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


def dfs(v0, v, k):
    if k == 0:
        graph2[v0].append((1, v))
        return

    for i in range(len(graph1[v])):
        dfs(v0, graph1[v][i][1], k-1)

for i in range(n):
    dfs(i, i, 3)
    # print(graph1[i])

# print()
# for i in range(n):
#     print(graph2[i])


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


from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

inf = float('inf')
dist = dijkstra(graph2, n, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys

# main
N, M = [int(i) for i in input().split(' ')]
matrix = np.matrix([ [0 for i in range(N)] for i in range(N) ])

for i in range(M):
    (u, v) = [int(i) for i in input().split(' ')]
    matrix[u - 1, v - 1] = 1

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

start = np.matrix([1 if i == S - 1 else 0 for i in range(N)])

def matrix_eval_three_steps(matrix, vector):
    return np.dot(np.dot(np.dot(vector, matrix), matrix), matrix)

for i in range(N):
    start = matrix_eval_three_steps(matrix, start)
    if start[0, T - 1] > 0:
        print(i + 1)
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def expands(Vs, s):
    dist1 = set(n for n in Vs[s])
    dist2 = set(n for d1 in dist1 for n in Vs[d1])
    return list(n for d2 in dist2 for n in Vs[d2] if n != s)


def solve(N, M, UVs, S, T):
    Vs = [[] for _ in range(N + 1)]
    for u, v in UVs:
        Vs[u].append(v)

    MAX = 10 ** 6
    dist = [MAX for _ in range(N + 1)]
    dist[S] = 0
    q = deque()
    q.append(S)
    while q:
        s = q.popleft()
        for n in expands(Vs, s):
            if dist[n] == MAX:
                dist[n] = dist[s] + 1
                q.append(n)

    if dist[T] == MAX:
        return -1
    return dist[T]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    UVs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    S, T = tuple(map(int, input().split(" ")))
    print(solve(N, M, UVs, S, T))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from heapq import heappush, heappop


def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF] * n
    visited = [False] * n

    dist[start] = 0
    que = [(0, start)]

    while que:
        cost, cur = heappop(que)
        if visited[cur]:
            continue

        visited[cur] = True

        for edgecost, nextnode in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))

    return dist

n, m = li()

edges = []
ins = [[] for _ in range(n)]
ots = [[] for _ in range(n)]

for _ in range(m):
    u,v = li_()
    ins[v].append(u)
    ots[u].append(v)
    edges.append((u, v))

graph = [set() for _ in range(n)]

for ui, vi in edges:
    for st in ins[ui]:
        for to in ots[vi]:
            graph[st].add((1,to))

s, t = li_()
INF = 10**8+1

dist = dijkstra(graph, s, INF)

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

Submission status: Time Limit Exceeded

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

adjucent_dict={u:set() for u in range(1,N+1)}
for u,v in UV:
  adjucent_dict.setdefault(u,set()).add(v)
  #adjucent_dict.setdefault(v,set()).add(u)
  
two_adjucent_dict={u:set.union(*[adjucent_dict[v] for v in adjucent_dict[u]]) if adjucent_dict[u] else set() for u in range(1,N+1)}
three_adjucent_dict={u:set.union(*[adjucent_dict[v] for v in two_adjucent_dict[u]]) if two_adjucent_dict[u] else set() for u in range(1,N+1)}

visited=set([S])
just_visited=set([S])
n=1
while True:
  three_step = set.union(*[three_adjucent_dict[u] for u in just_visited])
  just_visited = three_step - visited
  if T in just_visited:
    print(n)
    break
  if len(just_visited)==0:
    print(-1)
    break
    
  visited = visited & just_visited
  n+=1

Submission status: Time Limit Exceeded

Solution code:
# 最大でも3Nしか頂点には回らない
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())

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

dist = [[False]*3 for i in range(n)]
cnt = [[0]*3 for i in range(n)]
s, t = map(int, input().split())
s -= 1
t -= 1
q = deque()
# now, dist(mod3), cnt
q.append((s, 0, 0))
while q:
    now, d, c = q.popleft()
    if dist[now][d] and cnt[now][d] < c:
        continue
    dist[now][d] = True
    cnt[now][d] = c
    next_d = (d+1)%3
    next_c = c+1
    for to in edges[now]:
        if not dist[to][next_d] or cnt[to][next_d] > c:
            q.appendleft((to, next_d,next_c))
if dist[t][0]:
    print(cnt[t][0]//3)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    # power_funcを用いて(nCk) mod p を求める 
    # nCk = n!/((n-k)!k!)を使用

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    # a^b mod p を求める
    # bを2進数分解して高速累乗

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

#D
def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge):

    dist = [inf for i in range(num)]
    dist[start] = 0
    q = [(dist[start], start)]
    while q:
        du, u = heappop(q)
        for j in edge[u]:
            if dist[j] > du + 1:
                dist[j] = du + 1
                heappush(q, [dist[j], j])
    return dist
#E
def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = [[] for i in range(n)]
    for x,y in v:
        edge[x].append((y))
    newedge = [[] for i in range(n)]
    for num, i in enumerate(edge):
        for j in i:
            for k in edge[j]:
                for l in edge[k]:
                    if l == num:
                        continue
                    newedge[num].append(l)
    d = dijkstra(n, s, newedge)
    if d[t] == inf:
        print(-1)
    else:
        print(d[t])
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())

edges = [set() for _ in range(N)]

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

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


step2 = [set() for _ in range(N)]

for u in range(N):
    for v in edges[u]:
        step2[u] |= edges[v]

step3 = [set() for _ in range(N)]

for u in range(N):
    for v in edges[u]:
        step3[u] |= step2[v]

cost = [-1 for _ in range(N)]
cost[S] = 0

q = []

for v in step3[S]:
    heapq.heappush(q, (1, v))

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for v in step3[u]:
        heapq.heappush(q, (c+1, v))

print(cost[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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())
q = deque([S])
ans = 0
while True:
    ans += 1
    for _ in range(3):
        A = []
        while len(q)!=0:
            v = q.pop()
            A += V[v]
        q = deque(set(A))
    if q==deque([S]) or len(q)==0:
        ans = -1
        break
    elif q.count(T)>0:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 最大でも3Nしか頂点には回らない
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())

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

dist = [[False]*3 for i in range(n)]
cnt = [[0]*3 for i in range(n)]
s, t = map(int, input().split())
s -= 1
t -= 1
q = deque()
# now, dist(mod3), cnt
q.append((s, 0, 0))
while q:
    now, d, c = q.popleft()
    if dist[now][d] and cnt[now][d] < c:
        continue
    dist[now][d] = True
    cnt[now][d] = c
    next_d = (d+1)%3
    next_c = c+1
    for to in edges[now]:
        if not dist[to][next_d] or cnt[to][next_d] > c:
            q.append((to, next_d,next_c))
if dist[t][0]:
    print(cnt[t][0]//3)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
input=sys.stdin.readline

N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    G[u].add(v)
S,T=map(int,input().split())
A=[set() for i in range(N)]
for i in range(N):
    for v in G[i]:
        A[i]=A[i] | G[v]
B=[set() for i in range(N)]
for i in range(N):
    for v in A[i]:
        B[i]=B[i] | G[v]
C=[[] for i in range(N)]
for i in range(N):
    for j in B[i]:
        C[i].append([j,1])
INF=10**9+7
def dijkstra(G,s):

  d=[INF]*N
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d
d=dijkstra(C,S-1)
if d[T-1]==INF:
  print(-1)
else:
  print(d[T-1])

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 = [[]]
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.append(queue)



queue = [S]
visit = [False for _ in range(N+1)]
visit[S] = True
ans = 0
while len(queue) > 0:
    nextqueue = []
    for now in queue:
        visit[now] = True
        for next in graph_ken[now]:
            if not visit[next]:
                nextqueue.append(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 itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def next_kenp(node, edges, dones):
    nodes = set()
    nodes2 = set()
    if node not in edges:
        return nodes

    for n1 in edges[node]:
        if n1 not in edges:
            continue
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)

    for nn in nodes2:
        if nn not in edges:
            continue
        for n3 in edges[nn]:
            if n3 in dones or n3 in nodes:
                continue
            nodes.add(n3)
    return nodes


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

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

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

    dones = set()
    que = deque()
    que.append((s, 0))
    while que:
        node, step = que.popleft()
        next_nodes = next_kenp(node, edges, dones)
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

            if n not in dones:
                que.append((n, step + 1))
                dones.add(n)
    print(-1)


if __name__ == '__main__':
    main()