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 numpy as np

def kkp(array: np.ndarray, s):
    dst = array[array[:,0]==s,1]
    return list(dst)

def kkp3(steplist, idx):
    dst = []
    state = idx

    state = steplist[state]
    temp = []
    for s1 in state:
        temp.extend(steplist[s1-1])
    state = list(set(temp))
    temp = []
    for s1 in state:
        temp.extend(steplist[s1-1])
    state = list(set(temp))
    return state


n, m = map(int, input().split())
uv = [] * m
uv = [list(map(int, input().split())) for i in range(m)]
s, t = map(int, input().split())

uv_np = np.asarray(uv)

if m == 0:
    flag = False
else:

    steplist = []*n

    steplist = [kkp(uv_np, i+1) for i in range(n)]

    cnt = 0
    flag = True
    state = [s]
    check = [s]

while flag:
    cnt += 1
    temp = []
    for s in state:
        temp.extend(kkp3(steplist, s-1))
    state = list(set(temp))
    if t in state:
        print(cnt)
        break
    else:
        flag2 = True
        for s in state:
            if not(s in check):

                check.extend(state)
                check = list(set(check))
                flag2 = False
                break
        if flag2 is True:
            flag = False
if flag is False:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self, i):
        self.num = i
        self.ken = set()
        self.kenken = set()
        self.kenkenpa = set()

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

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

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

for i in range(N):
    for pre in nodes[i].ken:
        nodes[i].kenken = nodes[i].kenken | pre.ken

for i in range(N):
    for prepre in nodes[i].kenken:
        nodes[i].kenkenpa = nodes[i].kenkenpa | prepre.ken

num = t
step = 0
check_list = [[num, step]]
check = [False] * N
ok = False
while len(check_list) > 0:
    num, step = check_list.pop(0)
    for pre in nodes[num].kenkenpa:
        if pre.num == s:
            print(step+1)
            ok = True
            break
        if not check[pre.num]:
            check[pre.num] = True
            check_list.append([pre.num, step+1])
    if ok:
        break
if not ok:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy

N,M = map(int,input().split())
G = [set() for i in range(N)]
G3 = [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])
que1, nque = set(), set()
ans = 0

for i in range(N):
    for s in G[i]:
        que1 |= G[s-1]
    for s in que1:
        G3[i] |= G[s-1]
    G3[i] -= {S}
    que1 = set()

while T not in que and len(que) != 0:
    for s in que:
        nque |= G3[s-1]
    
    pque |= que
    que = copy.copy(nque) - pque
    nque = set()
    ans += 1

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

Submission status: Time Limit Exceeded

Solution code:
import queue
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
    q = queue.Queue()
    q.put(s)

    while not q.empty():
        u = q.get()
        color[u] = BLACK

        for v in V[u]:
            if color[v] != BLACK and d[v] == INFTY:
                d[v] = d[u] + 1
                q.put(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])

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if u not in s[v]:
        s[v].append(u)

st,g = m()
st -= 1
g -= 1
co = Max
def dfs(x,nn,now,coun):
    global sss,st,co
    if min(sss[now][nn],coun) == coun:
        if now == st and nn == 0:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                dfs(x,nn,i,coun)
    else:
        if now == st and nn == 0:
            co = min(co,coun)
eee = [[s,0,g,0]]
def bfs(x,nn,now,coun):
    global eee,sss,st,co
    if nn == 0 and st == now:
        co = min(co,coun)
    else:
        sss[now][nn] = coun
        if nn == 2:
            nn = 0
            coun += 1
        else:
            nn += 1
        for i in x[now]:
            eee.append([x,nn,i,coun])
'''
while eee:
    op = eee.pop()
    bfs(op[0],op[1],op[2],op[3])
'''
dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)

Submission status: Time Limit Exceeded

Solution code:
import copy

N,M = map(int,input().split())
G = [set() for i in range(N)]
G3 = [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])
que1, nque = set(), set()
ans = 0

for i in range(N):
    for s in G[i]:
        que1 |= G[s-1]
    for s in que1:
        G3[i] |= G[s-1]
    que1.clear()

while T not in que and len(que) != 0:
    que -= pque
    
    for s in que:
        nque |= G3[s-1]
    
    pque |= que
    que = copy.copy(nque)
    nque.clear()
    ans += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
E = [[] for _ in range(N + 1)]

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

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

cost = [[float('inf') for i in range(N + 1)] for _ in range(3)]

stack = deque(maxlen=N * M)

stack.append((S, 0))

while len(stack):
    now = stack.pop()
    u = now[0]
    c = now[1]
    for v in E[u]:
        nc = c + 1

        if cost[nc % 3][v] > nc:
            cost[nc % 3][v] = nc
            stack.append((v, nc))

if cost[0][T] != float('inf'):
    print(cost[0][T] // 3)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
E = [[] for _ in range(N + 1)]

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

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

cost = [[float('inf') for i in range(N + 1)] for _ in range(3)]

stack = deque()

stack.append((S, 0))

while len(stack):
    now = stack.pop()
    u = now[0]
    c = now[1]
    for v in E[u]:
        nc = c + 1

        if cost[nc % 3][v] > nc:
            cost[nc % 3][v] = nc
            stack.append((v, nc))

if cost[0][T] != float('inf'):
    print(cost[0][T] // 3)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
edge_to = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    edge_to[u-1].append(v-1)
S, T = map(int,input().split())
S -= 1
T -= 1
dest = [set() for i in range(N)]
def find_dest(i, j, cnt): #けんけんぱで行けるところ
    if cnt == 3:
        dest[i].add(j)
        return
    for k in edge_to[j]:
        find_dest(i, k, cnt+1)
for i in range(N):
    find_dest(i, i, 0)
q = [(S, 0)]
visited = [False for i in range(N)]
visited[S] = True
while q != []:
    now, cnt = q.pop(0)
    for j in dest[now]:
        if j == T:
            print(cnt+1)
            exit(0)
        if not visited[j]:
            q.append((j, cnt+1))
            visited[j] = True
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))
# print('hoge', file=sys.stderr)

N, M = [int(x) for x in input().split()]

# T = [[0] * N for _ in range(N)]
E = [set() for _ in range(N + 1)]

for i in range(M):
    u, v = [int(x) for x in input().split()]
    E[u].add(v)

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


def f(startSet, n):
    if n == 0:
        return startSet
    ret = set()
    for s in startSet:
        for t in E[s]:
            ret.add(t)
    return f(ret, n - 1)


# print(f({1}, 3))
# print(f({2}, 3))
# print(f({3}, 3))
# print(f({4}, 3))

E2 = [f({i}, 3) for i in range(N + 1)]

openNodes = {S}
closeedNodes = {}
mi = [INF] * (N + 1)
mi[S] = 0

while len(openNodes) != 0:
    curNode = -1
    curW = INF
    for on in openNodes:
        if mi[on] < curW:
            curNode = on
    openNodes.remove(curNode)

    for nn in E2[curNode]:
        if mi[nn] == INF:
            openNodes.add(nn)
            mi[nn] = mi[on] + 1

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

Submission status: Time Limit Exceeded

Solution code:
import queue

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

dist = [0] * N
q = queue.Queue()
q.put(S)
while not q.empty():
    u = q.get()
    nodeset = set([u])
    for _ in range(3):
        neigh_set = set()
        for v in nodeset:
            neigh_set |= set(adj_list[v])
        nodeset = neigh_set
    nodeset -= set([u])
    for v in nodeset:
        if v == T:
            print(dist[u] + 1)
            exit()
        if dist[v] == 0:
            dist[v] = dist[u] + 1
            q.put(v)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

visited = [False] * N
visited[S] = True
queue1 = deque([(0, S)])

while queue1 :
    cost, i = queue1.popleft()
    queue2 = deque([(0, i)])
    
    while queue2 :
        step, q = queue2.popleft()
        if step == 2 : 
            for j in vec[q] :
                if j == T :
                    print(cost + 1)
                    exit()
                if not visited[j] :
                    visited[j] = True
                    queue1.append((cost + 1, j))
        else :
            for j in vec[q] :
                queue2.append((step + 1, j))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, M = LI()
    graph = []
    from collections import defaultdict
    reversed_graph_dict = defaultdict(list)
    for _ in range(M):
        u, v = LI()
        graph.append([u,v])
        reversed_graph_dict[v].append(u)
    S, T = LI()

    # print(reversed_graph_dict)

    import collections
    def bfs(graph, root):
        seen, queue = set([root]), collections.deque([[root, 0],])
        while queue:
            vertex, tries = queue.popleft()
            tries += 1

            # 三段先を見に行く。
            first_step = graph[vertex]
            second_step = []
            for x in first_step:
                second_step += graph[x]
            third_step = []
            for x in set(second_step):
                third_step += graph[x]

            for node in set(third_step):
                if node == S:
                    print(tries)
                    return
                if node not in seen:
                    seen.add(node)
                    queue.append([node, tries])
        print(-1)
        return

    bfs(reversed_graph_dict, T)


main()

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)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  if t>300003:
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          nlist.append(vv)          
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  vlist = nlist
  if len(vlist) == 0:
    print(-1)
    break

Submission status: Time Limit Exceeded

Solution code:
#
import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def next_kenp(node, edges):
    nodes = set()
    nodes2 = set()
    for n1 in edges[node]:
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)
    for n2 in nodes2:
        for n3 in edges[n2]:
            nodes.add(n3)
    return nodes


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

    edges = defaultdict(list)

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

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

    new_edges = defaultdict(list)
    for i in range(1, n + 1):
        nodes = next_kenp(i, edges)
        new_edges[i] = list(nodes)

    # print(new_edges)

    dones = set()
    que = [(s, 0)]
    while que:
        node, step = que.pop(0)

        next_nodes = new_edges[node]
        # print(next_nodes)
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w={s}
    n*=3
    ans=0
    while n:
        tmp=set()
        p=w
        n-=1
        ans+=1
        for i in p:
            if i in d:
                for j in d[i]:
                    tmp.add(j)
        if t in tmp and ans%3==0:
            print(ans//3)
            exit()
        w=tmp
    print(-1)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
import collections
n,m = map(int,input().split())
L = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    L[a-1].append(b-1)
s,t = map(int,input().split())
T = []
for i in range(n):
    next = L[i]
    for j in range(2):
        p = []
        for k in range(len(next)):
            f = next[k]
            for l in range(len(L[f])):
                p.append(L[f][l])
        next = list(set(p))
    T.append(next)
D = [-1 for i in range(n)]
D[s-1] = 0
Q = collections.deque()
Q.append(s-1)
while len(Q) > 0:
    cur = Q.popleft()
    for i in range(len(T[cur])):
        if D[T[cur][i]] == -1:
            Q.append(T[cur][i])
            D[T[cur][i]] = D[cur]+1
print(D[t-1])

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)

vs = {S}
checked = set()
i = 0
prev = 0
while True:
    i += 1
    checked |= vs
    for _ in range(3):
        ss = set()
        for v in vs:
            ss |= graph[v]
        vs = ss
    if T in vs:
        print(i)
        break
    if len(checked) == prev:
        print(-1)
        break
    prev = len(checked)

Submission status: Time Limit Exceeded

Solution code:
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect
import sys
import random
import time
inf = 10**9


def main():
    n, m = map(int, input().split())
    connectTo = [[] for i in range(n+1)]
    for i in range(m):
        u, v = map(int, input().split())
        connectTo[u].append(v)

    s, t = map(int, input().split())
    connect3To = [set() for i in range(n+1)]
    for i in range(1, n+1):
        for l in connectTo[i]:
            for k in connectTo[l]:
                for j in connectTo[k]:
                    connect3To[i].add(j)

    d = [100000000000 for i in range(n+1)]
    a = []
    d[s] = 0
    a.append(s)
    while(True):
        if a == []:
            print(-1)
            return
        v = a.pop(0)
        if v == t:
            break
        for w in connect3To[v]:
            if d[w] == 100000000000:
                d[w] = d[v]+1
                a.append(w)
                a.sort(key=lambda x: d[x])
            elif d[w] > d[v]+1:
                d[w] = d[v]+1
    print(d[t])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
n,m = map(int,input().split())
L = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    L[a-1].append(b-1)
s,t = map(int,input().split())
T = []
for i in range(n):
    next = L[i]
    for j in range(2):
        p = []
        for k in range(len(next)):
            g = int(k)
            f = next[g]
            for l in range(len(L[f])):
                p.append(L[f][l])
        next = list(set(p))
    T.append(next)
D = [-1 for i in range(n)]
D[s-1] = 0
Q = collections.deque()
Q.append(s-1)
while len(Q) > 0:
    cur = Q.popleft()
    for i in range(len(T[cur])):
        if D[T[cur][i]] == -1:
            Q.append(T[cur][i])
            D[T[cur][i]] = D[cur]+1
print(D[t-1])

Submission status: Time Limit Exceeded

Solution code:
def mv(nodes,mvinfo):
    dists=set()
    for node in nodes:
        dists=dists | set(mvinfo[node-1])
    return list(dists)


N,M=[int(e) for e in input().split(' ')]

# 1step
mv1=[[] for n in range(N)]

for i in range(M):
    u,v=[int(e) for e in input().split(' ')]
    mv1[u-1].append(v)
S,T=[int(e) for e in input().split(' ')]

# 1step to 3steps
mv3=[]
for i in range(N):
    mv3.append(mv(mv(mv1[i],mv1),mv1))

# search
for i in range(1,1+N):
    if i==1:
        dists=mv3[S-1]
    else:
        dists=mv(dists,mv3)
    
    if T in dists:
        break
else:
    i=-1
print(i)

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)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  if t>300003:
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          nlist.append(vv)          
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  vlist = nlist

Submission status: Time Limit Exceeded

Solution code:
import collections
n,m = map(int,input().split())
L = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    L[a-1].append(b-1)
s,t = map(int,input().split())
T = []
for i in range(n):
    next = L[i]
    for j in range(2):
        p = []
        for k in range(len(next)):
            g = int(k)
            f = next[g]
            for l in range(len(L[f])):
                p.append(L[f][l])
        next = list(set(p))
    T.append(next)
D = [-1 for i in range(n)]
D[s-1] = 0
Q = collections.deque()
Q.append(s-1)
while len(Q) > 0:
    cur = Q.popleft()
    for i in range(len(T[cur])):
        if D[T[cur][i]] == -1:
            Q.append(T[cur][i])
            D[T[cur][i]] = D[cur]+1
print(D[t-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, m = [ int(v) for v in input().split() ]
connect_list = [[] for j in range(n)]

for i in range(m):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append(b)
s, t = [ int(v)-1 for v in input().split() ]
terminal_time = []
reverse_time = []

point_list = [s]

for i in range(m*3):

    new_point_list = []
    for j in point_list:
        new_point_list += connect_list[j]
    new_point_list = list(set(new_point_list))
    if t in new_point_list:
        terminal_time.append(i)
    if s in new_point_list:
        reverse_time.append(i)

    point_list = new_point_list


ans = -1
for i in terminal_time:
    if i % 3 == 2:
        ans = (i+1)//3
        break
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())

dict3 = {}
for k, next1 in dict.items():
    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]

    dict3[k] = next3

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 = set([])
    for node in current:
        if node in dict3.keys():
            next3 = next3 | dict3[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 queue
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
    q = queue.Queue()
    q.put(s)

    while not q.empty():
        u = q.get()
        color[u] = BLACK

        for v in V[u]:
            if color[v] != BLACK and d[v] == INFTY:
                d[v] = d[u] + 1
                color[v] = GRAY
                q.put(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)
    kkpgraph[i] = list(set(kkpgraph[i]))
d = dijkstra(S, kkpgraph)
if d[T] == INFTY:
    print(-1)
else:
    print(d[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = list(map(int, input().split()))
d1 = defaultdict(set)
for i in range(m):
  u, v = list(map(int, input().split()))
  d1[u].add(v)
s, t = list(map(int, input().split()))
d2 = defaultdict(set)

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

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

for i in range(1, n+1):
  visited = set()
  dfs(i, i, 0, visited)
  visited.add(i)

def bfs():
  que = [(s, 0)]
  visited = set()

  while len(que) > 0:
    p = que.pop(0)
    if p[0]==t:
      return p[1]
    for nx in d2[p[0]]:
      if nx in visited:
        continue
      visited.add(nx)
      que.append((nx, p[1]+1))
  return -1

print(bfs())

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)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
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:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          nlist.append(vv)          
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  vlist = nlist

Submission status: Time Limit Exceeded

Solution code:
import queue

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

for i in range(N):
    nodeset = set([i])
    for _ in range(3):
        neigh_set = set()
        for v in nodeset:
            neigh_set |= set(adj_list[v])
        nodeset = neigh_set
    hop3_list[i] = list(nodeset - set([i]))

dist = [0] * N
q = queue.Queue()
q.put(S)
while not q.empty():
    u = q.get()
    for v in hop3_list[u]:
        if v == T:
            print(dist[u] + 1)
            exit()
        if dist[v] == 0:
            dist[v] = dist[u] + 1
            q.put(v)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import re
import numpy as np
from scipy.sparse import lil_matrix, csr_matrix

N, M = [int(i) for i in re.split(" ", input())]
G = lil_matrix((N, N), dtype=np.bool)

for i in range(M):
    u, v = [int(i) for i in re.split(" ", input())]
    G[u-1, v-1] = True
G = G.tocsr()
G = G.dot(G).dot(G)

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

count = -1
G_tmp = G
for i in range(1, N+1):
    if i == 1:
        pass
    else:
        G_tmp = G_tmp.dot(G)
    if G_tmp[S-1, T-1]:
        count = i
        break

print(count)

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 == t: return d
        if i in visited:
            continue
        visited.add(i)
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        if t in b:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(b)]
    return -1


print(BC132_E())