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

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]:
                cand = 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:
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(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):
    q = [(i, 3)]
    idx = 0
    while True:
        if idx == len(q):
            break
        v, c = q[idx]
        idx += 1
        if c == 0:
            graph2[i].append(v)
            continue
        for j in graph1[v]:
            q.append((j, c-1))



# for i in range(n):
#     print(i)
#     for _, v in graph1[i]:
#         print(" ->", v)
#
#
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)]
    NextCost = 1
    while heap:
        cost,thisNode = heappop(heap)
        for 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:
N, M = map(int,input().split())
uv = [[] for i in range(N+1)]
vu = [[] for i in range(N+1)]
for i in range(M):
    u, v = map(int,input().split())
    uv[u].append(v)
    vu[v].append(u)
S, T = map(int,input().split())
 
pa = [True]*(N+1)
cnt = 0
 
nowS = [S]
nowT = [T]
 
flag = False
 
while True:
    cnt += 1
    a = []
    for i in nowS:
        for j in uv[i]:
            a.append(j)
    b = []
    for i in a:
        for j in uv[i]:
            b.append(j)
    nowS = []
    for i in b:
        for j in uv[i]:
            if pa[j]:
                nowS.append(j)
                pa[j] = False
    
    for i in nowS:
        if i in nowT:
            flag = True
    
    if flag:
        print(cnt)
        break
 
    if len(nowS) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m=map(int,input().split())
G = np.array([[0]*n]*n)
for _ in range(m):
    u,v=map(int,input().split())
    G[u-1,v-1]=1
G3 = np.dot(np.dot(G,G),G)

Gn = G3
s,t=map(int,input().split())
for i in range(1,n):
    if Gn[s-1,t-1] > 0:
        print(i)
        break
    elif i==n-1:
        print(-1)
        break
    else:
        Gn=np.dot(Gn,G3)

Submission status: Time Limit Exceeded

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

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

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


par = [i for i in range(3*N)]
rank = [0 for i in range(3*N)]

def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def same(x, y):
    return find(x) == find(y)

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

ans = 0
start = [S-1]
frag = 1
g = -1
while frag:
    frag = 0
    ans += 1
    g += 1
    g %= 3
    l = len(start)
    for i in range(l):
        s = start.pop(0)
        for j in range(len(G[s])):
            start.append(G[s][j])
            if g == 2:
                if same(s + 2 * N, G[s][j]):
                    continue
                else:
                    frag = 1
                    unite(s + 2 * N, G[s][j])

            else:
                if same(s + g * N, G[s][j] + (g+1) * N):
                    continue
                else:
                    frag = 1
                unite(s+ g * N, G[s][j] + (g+1) * N)

        if same(S-1, T-1) and par[S-1] != -1:
            print(ans//3)
            sys.exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy

N,M = map(int,input().split())
G = [set() for i in range(N)]
for _ in range(M):
    s,t = map(int,input().split())
    G[s-1].add(t)
S,T = map(int,input().split())

pque = set()
que = set([S])
nque = set()
ans = 0

while T not in que and len(que) != 0:
    que -= pque
    pque |= que
    for _ in range(3):
    
        for s in que:
            nque |= G[s-1]

        que = copy.copy(nque)
        nque.clear()
    ans += 1

if len(que) == 0: ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from copy import copy
N, M = map(int, input().split())

dict = {}
for i in range(M):
    u, v = map(int, input().split())
    if u in dict.keys():
        dict[u].add(v)
    else:
        dict[u] = set([v])

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

current = set([s])

while True:
    next1 = set([])
    for node in current:
        if node in dict.keys():
            next1 = next1 | dict[node]
    # print(next1)
    next2 = set([])
    for node in next1:
        if node in dict.keys():
            next2 = next2 | dict[node]
    # print(next2)
    next3 = set([])
    for node in next2:
        if node in dict.keys():
            next3 = next3 | dict[node]

    next3 = next3 | current
    # print(next3)
    #
    # print("judge: {}".format(next3))

    if t in next3:
        reachable = True
        break
    elif current == next3:
        reachable = False
        break

    current = next3


def fun():
    if not reachable:
        return -1

    cnt = 0

    current = set([s])
    while True:
        next1 = set([])
        for node in current:
            if node in dict.keys():
                next1 = next1 | dict[node]
        next2 = set([])
        for node in next1:
            if node in dict.keys():
                next2 = next2 | dict[node]
        next3 = set([])
        for node in next2:
            if node in dict.keys():
                next3 = next3 | dict[node]

        cnt += 1

        if t in next3:
            return cnt
        # input()
        # print("reach: {}".format(next3))

        current = next3


if __name__ == "__main__":
    output = fun()

    print(output)

Submission status: Time Limit Exceeded

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

from heapq import heappush, heappop

INF = float('inf')

# 単一始点最短経路を求める（Dijkstra法）
def Dijkstra(adjList, vSt, vEn):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if vNow == vEn: break
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2, wt in adjList[vNow]:
            c2 = cNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))
    return costs


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

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

adjL = [[] for _ in range(N)]
for u, v in edges:
    for v0 in v0s[u]:
        for v2 in v2s[v]:
            adjL[v0].append((v2, 1))

costs = Dijkstra(adjL, S, T)

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

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() ]
#
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
    visit|= n
#
print( hop )

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


def main():
    n, m = get_li()
    if m > 0:
        U, V = gets(m, [int, int])
    else:
        U, V = [], []
    s, t = get_li()
    edges = defaultdict(list)
    for u, v in zip(U, V):
        edges[u].append(v)
    kkpedges = defaultdict(set)
    [kkpedges[i].add(l) for i in range(1, n + 1) for j in edges[i] for k in edges[j] for l in edges[k]]
    q = deque()
    known = [False] * (n + 1)
    for v in kkpedges[s]:
        q.append((v, 1))
        known[v] = True
    while len(q) > 0:
        v, d = q.popleft()
        if v == t:
            print(d)
            return
        for u in kkpedges[v]:
            if known[u]:
                continue
            q.append((u, d + 1))
            known[u] = True
    print(-1)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue as q

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

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

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

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

        ns = D.setdefault(p, set())
        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

if __name__ == "__main__":
    main()

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, g):

    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])
            if j == g:
                return dist
    return dist
#E
def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = defaultdict(list)
    for x,y in v:
        edge[x].append(y)
    newedge = defaultdict(list)
    for key, i in edge.items():
        b = []
        for j in i:
            for k in edge[j]:
                b.append(k)
            if edge[j] == []:
                a = edge.pop(j)
        b = list(set(b))
        newedge[key] = b
    nnewedge = defaultdict(list)
    for key, i in newedge.items():
        b = []
        for j in i:
            for k in edge[j]:
                if key == k:
                    continue
                b.append(k)
        b = list(set(b))
        nnewedge[key] = b
    d = dijkstra(n, s, nnewedge, t)
    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 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)]

ans = 0
queue = [S]
visit = [False]*(N+1)
while len(queue) > 0:
    queuetemp = []
    for now in queue:
        if visit[now]:
            continue
        visit[now] = True
        queuenext = graph[now][:]
        for _ in range(2):
            nextqueue = []
            for next in queuenext:
                nextqueue.extend(graph[next])
            queuenext = f7(nextqueue)
        queuetemp.extend(queuenext)
    queue = f7(queuetemp)
    if visit[T]:
        break
    ans += 1



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

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,-1,-1] for i in range(n)]
b = 10000000000

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
from collections import deque

INF = -1

nVertices, nEdges = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nEdges):
    u, v = map(int, input().split())
    edges[u].append(v)
s, t = map(int, input().split())

def getNextMoves(from_, v, depth):
    if depth == 3:
        if dist[v] == INF:
            dist[v] = dist[from_] + 1
            q.append(v)
        return
    for child in edges[v]:
        getNextMoves(from_, child, depth + 1)

dist = [INF] * (nVertices + 1)
dist[s] = 0
q = deque()
q.append(s)
while q:
    cur = q.popleft()
    getNextMoves(cur, cur, 0)
print(dist[t])

Submission status: Time Limit Exceeded

Solution code:
import sys
#色々とメモリ使用量には気をつける
from collections import deque

n, m=map(int, input().split())
u_list=[]
v_list=[]
for i in range(m):
    u, v=map(int, input().split())
    u_list.append(u)
    v_list.append(v)
s, t=map(int, input().split())
queue=deque()
kenken=[]
for i in range(1, n+1):
    queue.append((i, 0))
    while(len(queue))!=0:
        target=queue.popleft()
        target_pos=target[0]
        target_val=target[1]
        for j in range(m):
            if u_list[j]==target_pos:
                if target_val+1==3:
                    kenken.append((i, v_list[j]))
                else:
                    queue.append((v_list[j], target_val+1))

use_edge=[1 for i in range(len(kenken))]

queue.append((s, 0))
while(len(queue)!=0):
    target=queue.popleft()
    target_pos=target[0]
    target_val=target[1]
    for j in range(m):
        if use_edge[j]:

            if kenken[j][0]==target_pos:
                if kenken[j][1]==t:
                    print(target_val+1)
                    sys.exit()
                else:
                    queue.append((kenken[j][1], target_val+1))
                    use_edge[j]=0
print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 22 20:48:47 2019
ABC132E
@author: maezawa
"""

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]:
                continue
            v[u] = True

            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


n, m = list(map(int, input().split()))
vnext = [[] for _ in range(n+1)]
for i in range(m):
    ui, vi = list(map(int, input().split()))
    vnext[ui].append(vi)
s, t = list(map(int, input().split()))
graph = Dijkstra()
for i in range(1,n+1):
    pos3 = []
    for nexv1 in vnext[i]:
        for nexv2 in vnext[nexv1]:
            for nexv3 in vnext[nexv2]:
                graph.add(i, nexv3, 1, directed=True)
result = graph.Dijkstra_search(s)
ans = result[t]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#
from collections import deque

import sys

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

    edges = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        edges[u].append(v)
    # print(edges)

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

    def next_kenp(node):
        nodes = set()
        nodes2 = set()

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

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

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

            que.append((n, step + 1))
            dones.add(n)

    print(-1)


if __name__ == '__main__':
    main()

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 = 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:
import heapq
n, m = map(int, input().split())
G = [[] for _ in range(n)]
G2 = [set() for _ in range(n)]
G3 = [set() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    G[u-1].append(v-1)
s, t = map(int, input().split())
s -= 1
t -= 1
for i in range(n):
    G2[i] = G2[i].union(*(G[v] for v in G[i]))
for i in range(n):
    G3[i] = G3[i].union(*(G[v] for v in G2[i]))
d = [float("inf")]*n
d[s] = 0
h = []
heapq.heappush(h, (0, s))
while h:
    x, v = heapq.heappop(h)
    if d[v] < x:
        continue
    for u in G3[v]:
        if d[v] + 1 < d[u]:
            d[u] = d[v] + 1
            heapq.heappush(h, (d[u], u))
if d[t] == float("inf"):
    print(-1)
else:
    print(d[t])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    dp = [[set() for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        dp[0][v-1].add(u-1)
    S, T = map(int, input().split())
    for i in range(1, 3):
        for j in range(N):
            for nxt in dp[i-1][j]:
                dp[i][j] = dp[i][j].union(dp[0][nxt])
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in dp[2][i]:
            adj[j].add(i)
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()

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)]
visited = [False] * N
visited[S] = True
queue_ = [S]

while queue_ :
    i = queue_.pop()
    queue = deque([(0, i)])
    while queue :
        step, q = queue.popleft()
        if step == 2 : 
            for j in vec[q] :
                vec_[i].append(j)
                if not visited[j] :
                    visited[j] = True
                    queue_.append(j)
        else :
            for j in vec[q] :
                queue.append((step + 1, j))
                if not visited[j] :
                    visited[j] = True
                    queue_.append(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:
#
from collections import deque

import sys

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

    edges = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        edges[u].append(v)
    # print(edges)

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

    def next_kenp(node, edges, dones):
        nodes = set()
        nodes2 = set()

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

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

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

            que.append((n, step + 1))
            dones.add(n)

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, V):
    color = [WHITE for i in range(N+1)]
    d = [INFTY for i in range(N+1)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v in V[u]:
            if color[v] != BLACK:
                if d[u] + 1 < d[v]:
                    d[v] = d[u] + 1
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

def rec(s, i, depth):
    if depth == 3:
        kkpgraph[s].append(i)
        return
    if not graph[i]:
        return
    for node in graph[i]:
        rec(s, node, depth+1)
    return

N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
kkpgraph = [[] for i in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
S, T = map(int, input().split())
for i in range(1, N+1):
    rec(i, i, 0)
d = dijkstra(S, kkpgraph)
if d[T] == INFTY:
    print(-1)
else:
    print(d[T])