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:
from sys import stdin
from collections import defaultdict
from collections import deque

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

INF = 10 ** 15
# visit = [False] * ( (N + 1) * 3 )
dist  = [-1] * ( (N) * 3 + 1 )
graph_connection = defaultdict(lambda :[])
graph_cost = defaultdict(lambda :defaultdict(lambda :INF))
#
# def dfs(v,dist_before):
#
#     dist[v] = dist_before + 1
#     next_vertexs = graph_connection[v]
#     for next_v  in next_vertexs :
#         if dist[next_v] == -1:
#             dfs(next_v,dist[v])
#     return 0
#

for cost in  Cs:
    a,b= cost
    for i in range(0,3):
        from_v = a + (i) * N
        to_v = b + (i + 1) % 3 * N
        graph_connection[from_v].append(to_v )

        # from_v = b + (i) * N
        # to_v = a + (i + 1) % 3 * N
        # graph_connection[from_v].append(to_v )

# dist[S] = 0


que = deque()
#(from_v,to_v)
que.append((S,S))

while que:
    from_v, to_v = que.popleft()
    dist[to_v] = dist[from_v] + 1
    for next_v in graph_connection[to_v]:
        if dist[next_v] == -1:
            que.append((to_v,next_v))
if dist[T] < 0:
    print(dist[T] )
else:
    print(dist[T]//3)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
l = [[] for i in range(n+1)]
rl = [0 for i in range(n+1)]
for i in range(m):
    u,v = map(int,input().split())
    l[u].append(v)
s,t = map(int,input().split())
d = deque()
d.append([s,0])
rl[s] = 1
ans = -1
def kkp(l,rl,now,d,c,t):
    for i in l[now]:
        for j in l[i]:
            for k in l[j]:
                #print(k,now,c)
                if k == t:
                    return c+1
                else:
                    if rl[k] == 0:
                        d.append([k,c+1])
                        rl[k] = 1
    return 0
while len(d):
    now,c = d.popleft()
    if m == 0:
        break
    else:
        if kkp(l,rl,now,d,c,t) > 0:
            ans =  kkp(l,rl,now,d,c,t)
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#### 132_E

import queue
import sys
sys.setrecursionlimit(300000)
 
n,m=map(int,input().split())

edges=[[] for i in range(3*n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    u0,u1,u2=u,u+n,u+2*n
    v0,v1,v2=v,v+n,v+2*n
    edges[u0].append(v1)
    edges[u1].append(v2)
    edges[u2].append(v0)
    
s,t=map(int,input().split())
s,t=s-1,t-1
    
def bfs(s,t):
    que=queue.Queue()
    que.put(s)
    d[s]=0
    visit[s]=True
    while not que.empty():
        q=que.get()
        if q==t:
            return d[t]
        for z in edges[q]:
            if visit[z]==False:
                que.put(z)
                d[z]=d[q]+1
                visit[z]=True
    return d[t]
                
visit=[False for _ in range(3*n)]
d=[-1 for _ in range(3*n)]

print(bfs(s,t)//3)

Submission status: Time Limit Exceeded

Solution code:
#132_E

import queue
import sys
sys.setrecursionlimit(300000)
 
n,m=map(int,input().split())

edges=[[] for i in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    edges[u-1].append(v-1)
edges_3=[[] for i in range(n)]
for i in range(n):
    for x in edges[i]:
        for y in edges[x]:
            for z in edges[y]:
                edges_3[i].append(z)
    
s,t=map(int,input().split())
s,t=s-1,t-1
    
def bfs(s,t):
    que=queue.Queue()
    que.put(s)
    d[s]=0
    visit[s]=True
    while not que.empty():
        q=que.get()
        if q==t:
            return d[t]
        for z in edges_3[q]:
            if visit[z]==False:
                que.put(z)
                d[z]=d[q]+1
                visit[z]=True
    return d[t]
                
visit=[False for _ in range(n)]
d=[-1 for _ in range(n)]

print(bfs(s,t))

Submission status: Time Limit Exceeded

Solution code:
#132_E

import queue
import sys
sys.setrecursionlimit(300000)
INF=10**9
 
n,m=map(int,input().split())

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

s,t=map(int,input().split())
s,t=s-1,t-1
    
def bfs(s,t):
    que=queue.Queue()
    que.put(s)
    d[s]=0
    visit[s]=True
    while not que.empty():
        q=que.get()
        if q==t:
            return d[t]
        for x in edges[q]:
            for y in edges[x]:
                for z in edges[y]:
                    if visit[z]==False:
                        que.put(z)
                        d[z]=d[q]+1
                        visit[z]=True
    return d[t]
                
visit=[False for _ in range(n)]
d=[INF for _ in range(n)]

ans=bfs(s,t)
print(ans if ans!=INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import queue
def dist(s, t, g):
    q = queue.Queue()
    dists = [-1]*len(g)
    dists[s] = 0
    q.put(s)
    f = False
    while not q.empty():
        target = q.get()
        for v in g[target]:
            if dists[v] == -1:
                dists[v] = dists[target] + 1
                if v == t:
                    f = True
                    break
                q.put(v)
        if f:
            break
    return dists[t]

def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n*3)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append(v+n)
        g[u+n].append(v+2*n)
        g[u+2*n].append(v)
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    print(dist(s, t, g)//3)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def dist(s, t, g):
    q = queue.Queue()
    dists = [-1]*len(g)
    dists[s] = 0
    q.put(s)
    while not q.empty():
        target = q.get()
        for v in g[target]:
            if dists[v] == -1:
                dists[v] = dists[target] + 1
                q.put(v)
    return dists[t]

def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n*3)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append(v+n)
        g[u+n].append(v+2*n)
        g[u+2*n].append(v)
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    print(dist(s, t, g)//3)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

l = [[] for u in range(n + 1)]
for u, v in uv:
    l[u].append(v)

def bfs(v):
    q = [(x, 0) for x in list(v)]
    visited = set(q)
    while len(q) > 0:
        x, step = q.pop(0)
        if step == 3:
            v.add(x)
            continue
        for y in l[x]:
            next = (y, step + 1)
            if next not in visited:
                visited.add(next)
                q.append(next)
    return v

v = set([s])
ret = 0
while True:
    olen = len(v)
    v = bfs(v)
    ret += 1
    if t in v:
        break
    if len(v) == olen:
        ret = -1
        break

print(ret)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())
G2 = [[] for _ in range(N+1)]

for i in range(1, N+1):
    stack = []
    stack.append((i, 0))
    while stack:
        v, d = stack.pop()
        if d == 3:
            G2[i].append((v, 1))
        if d < 3:
            for u in G[v]:
                stack.append((u, d+1))

dist = dijkstra(G2, N+1, S)
print(dist[T] if dist[T] != float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())
G2 = [[] for _ in range(N+1)]


def dfs(s, v, depth):
    if depth == 3:
        G2[s].append((v, 1))
        return
    if depth < 3:
        for u in G[v]:
            dfs(s, u, depth+1)


for i in range(1, N+1):
    dfs(i, i, 0)
dist = dijkstra(G2, N+1, S)
print(dist[T] if dist[T] != float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())
G2 = [[] for _ in range(N+1)]


def dfs(nodes, v):
    if nodes[0] != -1:
        if (v, 1) in G2[nodes[0]]:
            return
        G2[nodes[0]].append((v, 1))
    for u in G[v]:
        dfs(nodes[1:] + [v], u)


dfs([-1] * 3, S)
dist = dijkstra(G2, N+1, S)
print(dist[T] if dist[T] != float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,m=map(int,input().split())
u=[list(map(int,input().split())) for i in range(m)]
s,t=map(int,input().split())
dic=[[] for i in range(n+1)]
for i in range(m):
    a,b=u[i]
    dic[a].append(b)
# print(dic)
itta=[0]*(n+1)
d=deque([[s,0]])
itta[s]=1
itta[t]=2
while d:
    tmp=d.popleft()
    # print(tmp)

    for i in dic[tmp[0]]:
        if (tmp[1]+1)%3==0:
            if itta[i]==1:
                continue
            elif itta[i]==2:
                print((tmp[1]+1)//3)
                quit()
            else:
               itta[i]=1 
        d.append([i,tmp[1]+1])
    # print(itta)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import queue
N,M = map(int,input().split())
Edges = [[] for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    Edges[u-1].append(v-1)
S,T = map(int,input().split())
S,T = S-1,T-1
Q = [S]
visited = [False for i in range(N)]
D = [float('inf') for i in range(N)]
visited[S] = True
D[S] = 0
while Q:
    current_pos = Q.pop()
    for e1 in Edges[current_pos]:
        for e2 in Edges[e1]:
            for e3 in Edges[e2]:
                if not visited[e3]:
                    D[e3] = min(D[current_pos]+1,D[e3])
                    Q.append(e3)
                if e3 == T:
                    print(D[e3])
                    exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import dijkstra
n, m = map(int, input().split())
graph = lil_matrix((n+1,n+1), dtype=int)
for i in range(m):
    u, v = map(int, input().split())
    graph[u, v] = 1
start, goal = map(int, input().split())
graph = graph * graph * graph
k = dijkstra(graph, indices=start)
if k[goal] != float('inf'):
    print(int(k[goal]))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M = map(int,input().split())

data = [[] for _ in range(3*N)]

for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    data[3*u].append(3*v+1)
    data[3*u+1].append(3*v+2)
    data[3*u+2].append(3*v)

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

inf = 10**6
stack = deque([[3*S,0]])
time = [inf] * (3*N)

while stack:
    x = stack.pop()
    for y in data[x[0]]:
        if time[y] > x[1] + 1:
            time[y] = x[1] + 1
            stack.append([y,x[1] + 1])

if time[3*T] == inf:
    print(-1)
else:
    print(time[3*T]//3)

Submission status: Time Limit Exceeded

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

data = [[] for _ in range(3*N)]

for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    data[3*u].append(3*v+1)
    data[3*u+1].append(3*v+2)
    data[3*u+2].append(3*v)

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

inf = 10**6
stack = [[3*S,0]]
time = [inf] * (3*N)

while stack:
    x = stack.pop()
    for y in data[x[0]]:
        if time[y] > x[1] + 1:
            time[y] = x[1] + 1
            stack.append([y,x[1] + 1])

if time[3*T] == inf:
    print(-1)
else:
    print(time[3*T]//3)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)

s, t = map(int, sys.stdin.readline().split())

g2 = [[] for _ in range(n + 1)]
e = set()
hq = []
for u in range(1, n+1):
    for v in g[u]:
        heappush(hq, (1, u, v))

while hq:
    dux = heappop(hq)
    if dux in e:
        continue
    e.add(dux)
    d, u, x = dux
    if d == 3:
        g2[u].append(x)
        continue
    for y in g[x]:
        heappush(hq, (d+1, u, y))

def main():
    hq = [(0, s)]
    dist = [inf] * (n + 1)
    while hq:
        d, x = heappop(hq)
        if dist[x] != inf:
            continue
        dist[x] = d
        for y in g2[x]:
            if dist[y] == inf:
                heappush(hq, (d+1, y))
    
    return dist[t] if dist[t] != inf else -1

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)

s, t = map(int, sys.stdin.readline().split())

g2 = [[] for _ in range(n + 1)]
def after_cand(u):
    hq = [(0, u)]
    visited = set()
    dist = [inf] * (n + 1)
    while hq:
        d, x = heappop(hq)
        if x in visited and d == dist[x]:
            continue
        dist[x] = d
        visited.add(x)
        if d == 3:
            g2[u].append(x)
            continue
        for y in g[x]:
            heappush(hq, (d+1, y)) 

def main():
    for u in range(1, n+1):
        after_cand(u)

    hq = [(0, s)]
    dist = [inf] * (n + 1)
    while hq:
        d, x = heappop(hq)
        if dist[x] != inf:
            continue
        dist[x] = d
        for y in g2[x]:
            if dist[y] == inf:
                heappush(hq, (d+1, y))
    
    return dist[t] if dist[t] != inf else -1

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
for i in range(M):
  u, v = map(int, input().split())
  dic[u-1] += [v-1]
S, T = map(int, input().split())
S -= 1
T -= 1
dist = [[float('inf')]*3 for i in range(N)]
dist[S][0] = 0
q = deque([(S,0)])
flag = False
cnt = 0
while q:
  cnt += 1
  e, m = q.pop()
  n = (m+1)%3
  for p in dic[e]:
    if p==T:
      flag = True
    if dist[p][n]>dist[e][m]+1:
      dist[p][n] = dist[e][m]+1
      q += [(p,n)]
if flag:
  ans = dist[T][0] if dist[T][0]!=float('inf') else -1
  print(ans//3)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
dic = defaultdict(list)
for i in range(M):
  u, v = map(int, input().split())
  dic[u-1] += [v-1]
S, T = map(int, input().split())
S -= 1
T -= 1
dist = [[float('inf')]*3 for i in range(N)]
ls = [float('inf')]*3
dist[S][0] = 0
q = [(S,0)]
flag = False
while q:
  e, m = q.pop()
  n = (m+1)%3
  for p in dic[e]:
    if p==T:
      flag = True
    if dist[p][n]>dist[e][m]+1:
      dist[p][n] = dist[e][m]+1
      q += [(p,n)]
if flag:
  ans = dist[T][0] if dist[T][0]!=float('inf') else -1
  print(ans//3)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


data = sys.stdin.readlines()
N, M = map(int, data[0].split())
edge = [[[] for _ in range(N)] for _ in range(3)]
for i in range(1, M + 1):
    u, v = map(int, data[i].split())
    u -= 1
    v -= 1
    edge[0][u].append(v)
    edge[1][u].append(v)
    edge[2][u].append(v)
S, T = map(lambda x: int(x) - 1, data[M + 1].split())


def dfs(n, step):
    global T, ans
    rst = False
    if n == T and step % 3 == 0:
        rst |= True
    else:
        d = step % 3
        for e in edge[d][n]:
            if status[(d + 1) % 3][e] > step + 1:
                status[(d + 1) % 3][e] = step + 1
                rst |= dfs(e, step + 1)
    return rst


INF = float('inf')
status = [[INF] * N for _ in range(3)]
ans = 10 ** 10
if dfs(S, 0):
    print(status[0][T] // 3)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


data = sys.stdin.readlines()
N, M = map(int, data[0].split())
edge = [[] for _ in range(N)]
for i in range(1, M + 1):
    u, v = map(int, data[i].split())
    u -= 1
    v -= 1
    edge[u].append(v)
S, T = map(lambda x: int(x) - 1, data[M + 1].split())


def bfs1(s):
    q = deque()
    q.append((s, 0))

    while len(q) > 0:
        v, step = q.popleft()
        if step == 3:
            edge3[s].append(v)
        else:
            for nv in edge[v]:
                q.append((nv, step + 1))


def bfs2(n):
    global T
    q = deque()
    status[n] = 0
    q.append(n)

    while len(q) > 0:
        v = q.popleft()
        for nv in edge3[v]:
            if status[nv] == -1:
                status[nv] = status[v] + 1
                q.append(nv)


edge3 = [[] for _ in range(N)]
for i in range(N):
    bfs1(i)


status = [-1] * N
status[S] = 0
bfs2(S)
print(status[T])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)


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


def bfs1(s):
    q = deque()
    q.append((s, 0))

    while len(q) > 0:
        v, step = q.popleft()
        if step == 3:
            edge3[s].add(v)
        else:
            for nv in edge[v]:
                q.append((nv, step + 1))


def bfs2(n):
    global T
    q = deque()
    status[n] = 0
    q.append(n)

    while len(q) > 0:
        v = q.popleft()
        for nv in edge3[v]:
            if status[nv] == -1:
                status[nv] = status[v] + 1
                q.append(nv)


edge3 = [set() for _ in range(N)]
for i in range(N):
    bfs1(i)


status = [-1] * N
status[S] = 0
bfs2(S)
print(status[T])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)


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


def dfs1(s, n, step):
    if step == 3:
        edge3[s].add(n)
    else:
        for e in edge[n]:
            dfs1(s, e, step + 1)


def bfs2(n):
    global T
    q = deque()
    status[n] = 0
    q.append(n)

    while len(q) > 0:
        v = q.popleft()
        for nv in edge3[v]:
            if status[nv] == -1:
                status[nv] = status[v] + 1
                q.append(nv)


edge3 = [set() for _ in range(N)]
for i in range(N):
    dfs1(i, i, 0)


status = [-1] * N
status[S] = 0
bfs2(S)
print(status[T])

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])
 
def main():
    n,m = inpm()
    g = [[] for _ in range(n)]
    for _ in range(m):
        u,v = inpm()
        u -= 1
        v -= 1
        g[u].append(v)
    visited = [0 for _ in range(n)]
    s,t = inpm()
    s -= 1
    t -= 1
    que = deque()
    que.append(s)
    visited[s] = 1
    cnt = 1
    while True:
        key = 1
        for _ in range(3):
            tank = deque()
            while que:
                start = que.pop()
                for go in g[start]:
                    tank.append(go)
            que = tank
        tank = deque()
        for e in que:
            if not visited[e]:
                visited[e] = 1
                tank.append(e)
                key = 0
            if e == t:
                print(cnt)
                return
        que = tank
        cnt += 1
        if key:
            break
    print(-1)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])
 
def main():
    n,m = inpm()
    g = [[] for _ in range(n)]
    for _ in range(m):
        u,v = inpm()
        u -= 1
        v -= 1
        g[u].append(v)
    visited = [0 for _ in range(n)]
    s,t = inpm()
    s -= 1
    t -= 1
    que = deque()
    que.append(s)
    visited[s] = 1
    cnt = 1
    while True:
        key = 1
        for _ in range(3):
            tank = deque()
            while que:
                start = que.pop()
                for go in g[start]:
                    tank.append(go)
            que = tank
        check = [0 for _ in range(n)]
        tank = deque()
        for e in que:
            if not check[e]:
                check[e] = 1
                tank.append(e)
            if not visited[e]:
                visited[e] = 1
                key = 0
            if e == t:
                print(cnt)
                return
        que = tank
        cnt += 1
        if key:
            break
    print(-1)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])
 
def main():
    n,m = inpm()
    g = [[] for _ in range(n)]
    for _ in range(m):
        u,v = inpm()
        u -= 1
        v -= 1
        g[u].append(v)
    visited = [0 for _ in range(n)]
    s,t = inpm()
    s -= 1
    t -= 1
    que = deque()
    que.append(s)
    visited[s] = 1
    cnt = 1
    while True:
        key = 1
        for _ in range(3):
            tank = deque()
            while que:
                start = que.pop()
                for go in g[start]:
                    tank.append(go)
            que = tank
        for e in que:
            if not visited[e]:
                visited[e] = 1
                key = 0
            if e == t:
                print(cnt)
                return
        cnt += 1
        if key:
            break
    print(-1)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 11:55-

from collections import deque

def main():
  n, m = map(int, input().split()) 
  orig_graph = {i: [] for i in range(1, n+1)}
  for _ in range(m):
    ui, vi = map(int, input().split()) 
    orig_graph[ui].append(vi) 
  s, t = map(int, input().split()) 

  hopscotch_graph = {}
  for i in range(1, n+1):
    ken1 = set(orig_graph[i])
    ken2 = set(sum([orig_graph[k] for k in ken1], []))
    pa = set(sum([orig_graph[k] for k in ken2], []))
    hopscotch_graph[i] = pa


  dist = {i: -1 for i in range(1, n+1)}
  q = deque()
  dist[s] = 0
  q.append(s)
  for _ in range(n):
    i = q.popleft()
    for j in hopscotch_graph[i]:
      if dist[j] == -1:
        dist[j] = dist[i] + 1
        q.append(j)
    if len(q) == 0:
      break;

  print(dist[t])

 
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# 11:55-

from collections import deque

def main():
  n, m = map(int, input().split()) 
  orig_graph = {i: [] for i in range(1, n+1)}
  for _ in range(m):
    ui, vi = map(int, input().split()) 
    orig_graph[ui].append(vi) 
  s, t = map(int, input().split()) 

  hopscotch_graph = {}
  for i in range(1, n+1):
    ken1 = set(orig_graph[i])
    ken2 = set(sum([orig_graph[k] for k in ken1], []))
    pa = set(sum([orig_graph[k] for k in ken2], []))
    hopscotch_graph[i] = pa


  dist = {i: -1 for i in range(1, n+1)}
  q = deque()
  dist[s] = 0
  q.append(s)
  while len(q) > 0:
    i = q.popleft()
    for j in hopscotch_graph[i]:
      if dist[j] == -1:
        dist[j] = dist[i] + 1
        q.append(j)

  print(dist[t])

 
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline

def dijkstra_heap(s,edge,n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

def main():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]
    U = set()
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        U.add(u)
        edge[u].append(v)

    S, T = map(int, input().split())
    S -= 1
    T -= 1
    search = [False] * N
    can = [[] for _ in range(N)]
    def dfs(s,p,d):
        if d == 3:
            can[s].append((1,p))
            search[s] = True
            return
        for e in edge[p]:
            dfs(s,e,d+1)

        return

    for u in U:
        if search[u]:
            continue
        dfs(u,u,0)
    d = dijkstra_heap(S,can,N)
    if d[T] == 10**20:
        print(-1)
    else:
        print(d[T])




if __name__ == "__main__":
    main()