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 collections import defaultdict
n, m = list(map(int, input().split()))
d1 = defaultdict(list)
for i in range(m):
  u, v = list(map(int, input().split()))
  d1[u].append(v)
s, t = list(map(int, input().split()))
d2 = defaultdict(set)

def dfs (x, nx, cnt):
  if cnt==3:
    d2[x].add(nx)
  elif cnt>3:
    return

  for nnx in d1[nx]:
    dfs(x, nnx, cnt+1)

for i in range(1, n+1):
  dfs(i, i, 0)

from heapq import heappop, heappush
prev = [-1 for _ in range(n+1)]
def dijkstra(s, graph):
  d = [float("INF") for _ in range(n+1)]
  d[s] = 0
  q = []
  heappush(q, [0, s])

  while q:
    dt, v = heappop(q)
    if d[v] < dt:
      continue
    for to in graph[v]:
      if d[to] > dt+1:
        d[to] = dt+1
        prev[to] = v
        heappush(q, [d[to], to])
  return d
dd = dijkstra(s, d2)
if dd[t]==float("INF"):
  print(-1)
else:
  print(dd[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() ]
#
kkp= { i:[] for i in range(n) }
#
hop= 0
now = {s}
visit = {s}
while True:
    hop+= 1
    n= set()
    for i in now:
        n |= getVertex(i,e) - visit
    #
    if t in n: break
    if not n:
        hop= -1
        break
    now = n
    visit|= n
#
print( hop )

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict


def solve(N: int, M: int, U: "List[int]", V: "List[int]", S: int, T: int):
    S -= 1
    T -= 1
    adj = [[] for i in range(N)]
    for u, v in zip(U, V):
        adj[u-1].append(v-1)
    color = [[] for i in range(N)]
    color[S] = [0]
    Q = [(0, S)]

    while len(Q) > 0:
        d, u = heapq.heappop(Q)
        if u == T and d % 3 == 0:
            print(d // 3)
            return
        for v in adj[u]:
            if (d+1) % 3 in color[v]:
                continue
            heapq.heappush(Q, (d+1, v))
            color[v].append(d+1 % 3)

    print(-1)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]" 
    v = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, u, v, S, T)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- 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:
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[v-1].append(u-1)
T,St = map(int,input().split())

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(2):
    for j in range(N):
        for k in es[i][j]:
            es[i+1][j] |= es[0][k]

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

print(-1)

Submission status: Time Limit Exceeded

Solution code:
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:
from collections import deque

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

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

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

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

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

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

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

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((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):
    q = [(i, 3)]
    idx = 0
    while True:
        if idx == len(q):
            break
        v, c = q[idx]
        idx += 1
        if c == 0:
            graph2[i].append((1, 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)]
    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:
from collections import defaultdict
from queue import Queue
n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
kenedge = defaultdict(set)
dist = [MX for i in range(n)]
reached = [False for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

for i in range(n):
    step1 = set()
    for ii in edge[i]:
        step1 |= edge[ii]
    step2 = set()
    for iii in step1:
        step2 |= edge[iii]
    step3 = set()
    for iiii in step2:
        kenedge[i].add(iiii)

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s] = 0

q = Queue()
q.put(s)
while not q.empty():
    node = q.get()
    reached[node] = True
    for next_node in kenedge[node]:
        if not reached[next_node]: q.put(next_node)
        dist[next_node] = min(dist[next_node], dist[node] + 1)

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

Submission status: Time Limit Exceeded

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

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

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

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

print(-1)

Submission status: Time Limit Exceeded

Solution code:
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):
    q = [(i, 3)]
    idx = 0
    while True:
        if idx == len(q):
            break
        v, c = q[idx]
        idx += 1
        if c == 0:
            graph2[i].append((1, 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)]
    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 sys
N,M=map(int,input().split())

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)

vlist=graph[S]
t=0
while(True):
  t+=1
  if t>10**6:
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      for vv in graph[v]:
        nlist.append(vv)
      
  #print((t,nlist))
  vlist = nlist

Submission status: Time Limit Exceeded

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


print(BC132_E())

Submission status: Time Limit Exceeded

Solution code:
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
i = 0
while queue != []:
    i += 1
    l = 0
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > i:
                D[s][i%3] = i
                if not s in hoge[:l]:
                    hoge[l] = s
                    l += 1
    queue = hoge[:l]
    if D[T-1][0] != float('inf'):
        break
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)

Submission status: Time Limit Exceeded

Solution code:
#
from collections import deque

import sys
input = sys.stdin.readline


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

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

    for _ in range(m):
        u, v = map(int, input().split())
        edges[u].append(v)
    # 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 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 % 3 == 0 and p == T:
            return c
        close[l].add(p)

        if not p in D:
            continue

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

if __name__ == "__main__":
    main()

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):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        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)

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

Submission status: Time Limit Exceeded

Solution code:
import queue

n,m = map(int, input().split())
a = [[] for i in range(n)]

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

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

inf = float('inf')
d = [[inf, inf, inf] for i in range(n)]
d[s][0]=0

q = queue.Queue()
for i in range(len(a[s])):
    q.put(a[s][i])
    d[a[s][i]][1]=1


while not q.empty():
    p = q.get()
    for i in range(len(a[p])):
        r = a[p][i]
        c = []
        if d[r][0]==inf:
            c.append(0)
        if d[r][1]==inf:
            c.append(1)
        if d[r][2]==inf:
            c.append(2)
        if not c:
            continue

        flag = False
        for j in range(len(c)):
            if c[j]==0:
                if d[p][2]!=inf:
                    break
            elif c[j]==1:
                if d[p][0]!=inf:
                    break
            elif c[j]==2:
                if d[p][1]!=inf:
                    break
            if j==len(c)-1:
                flag=True
        if flag:
            continue

        q.put(r)
        if d[r][0]==inf:
            d[r][0]=d[p][2]+1
        if d[r][1]==inf:
            d[r][1]=d[p][0]+1
        if d[r][2]==inf:
            d[r][2]=d[p][1]+1
        if r==t and d[r][0]!=inf:
            print(d[r][0]//3)
            exit()
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 = 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)
    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:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


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

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

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

        pass


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

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

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u]+w:
                dist[v] = dist[u]+w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


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

    for i in range(N):
        for v1 in E[i]:
            for v2 in E[v1]:
                for v3 in E[v2]:
                    g1.add_edge((i, v3, 1))

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]"
    v = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, u, v, S, T)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict

from functools import lru_cache

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

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

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

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

memo = [[None] * (N+1) for _ in range(3)]


def dest(v, count):
    if memo[count - 1][v] is not None:
        return memo[count - 1][v]

    if count <= 1:
        memo[count - 1][v] = graph[v]
        return graph[v]
    ret = set()
    for u in graph[v]:
        ret |= dest(u, count - 1)
    memo[count - 1][v] = ret
    return ret


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from heapq import heappop, heappush

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点)
def dijkstra(N: int, nodes: list, src: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    # スタート位置
    que = [(0, src)]
    res[src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # srcからの距離, 現在のノード
        dist, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxt in nodes[cur]:
            # 今回の経路のが短い時
            if res[cur] + 1 < res[nxt]:
                res[nxt] = res[cur] + 1
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (res[nxt], nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1

edges2=[]
def rec(org, u, cnt):
    if visited[u][cnt]:
        return
    visited[u][cnt]=True
    if cnt==3:
        edges2.append((org, u))
        return
    for v in nodes[u]:
        rec(org, v, cnt+1)
    return

for i in range(N):
    visited=list2d(N, 4, False)
    rec(i, i, 0)

nodes2=[[] for i in range(N)]
for u, v in edges2:
    nodes2[u].append(v)

res=dijkstra(N, nodes2, S)
if res[T]==INF:
    print(-1)
else:
    print(res[T])

Submission status: Time Limit Exceeded

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

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)

vlist=graph[S]
t=0
while(True):
  t+=1
  if t>10**7:
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      for vv in graph[v]:
        nlist.append(vv)
      
  #print((t,nlist))
  vlist = nlist