Problem:


Score : 500 points

Problem Statement

Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G.
G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.

First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.

Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq \min(10^5, N (N-1))

1 \leq u_i, v_i \leq N(1 \leq i \leq M)

u_i \neq v_i (1 \leq i \leq M)

If i \neq j, (u_i, v_i) \neq (u_j, v_j).

1 \leq S, T \leq N

S \neq T

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
:
u_M v_M
S T

Output

If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1.
If he can, print the minimum number of ken-ken-pa needed to reach vertex T.

Sample Input 1

4 4
1 2
2 3
3 4
4 1
1 3

Sample Output 1

2

Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.

Sample Input 2

3 3
1 2
2 3
3 1
1 2

Sample Output 2

-1

Any number of ken-ken-pa will bring Ken back to Vertex 1, so he cannot reach Vertex 2, though he can pass through it in the middle of a ken-ken-pa.

Sample Input 3

2 0
1 2

Sample Output 3

-1

Vertex S and Vertex T may be disconnected.

Sample Input 4

6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6

Sample Output 4

2



Sample input:
4 4
1 2
2 3
3 4
4 1
1 3


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(4100000)

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

already_reach = [-1]*(N+1)
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split(' '))
    graph[u].append(v)
S,T = map(int,input().split(' '))

def search(S_list,current_count=0):
    next_list = []
    for s in S_list:
        for i1 in graph[s]:
            for i2 in graph[i1]:
                for i3 in graph[i2]:
                    if already_reach[i3] == -1: #はじめての到達
                        already_reach[i3] = current_count+1
                        next_list.append(i3)
    if len(next_list) > 0:
        search(next_list,current_count+1)
search([S])
print(already_reach[T])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(4100000)

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

already_reach = [-1]*(N+1)
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split(' '))
    graph[u].append(v)
S,T = map(int,input().split(' '))

def search(S_list,current_count=0):
    for s in S_list:
        already_reach[s] = current_count
    #print(already_reach)
    next_list = []
    for s in S_list:
        for i1 in graph[s]:
            for i2 in graph[i1]:
                for i3 in graph[i2]:
                    if already_reach[i3] == -1: #はじめての到達
                        next_list.append(i3)
    if len(next_list) > 0:
        search(next_list,current_count+1)
search([S])
print(already_reach[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def reachable_by_3steps_from(node, edges):
    dist1 = edges[node]
    reachable = []
    for d1 in dist1:
        dist2 = edges[d1]
        for d2 in dist2:
            reachable += edges[d2]
    return reachable


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

start, goal = map(int, input().split())
skip_path = [[] for _ in range(n)]
for i in range(n):
    skip_path[i] = reachable_by_3steps_from(i, edges)

todo = deque([])
seen = [False] * n
seen[start-1] = True
for to in skip_path[start-1]:
    todo.append([to, 1])
    if to == goal-1:
        print(1)
        exit()

while todo:
    node, dist = todo.popleft()
    if seen[node]:
        continue
    seen[node] = True
    for to in skip_path[node]:
        if seen[to]:
            continue
        todo.append([to, dist+1])
        if to == goal-1:
            print(dist+1)
            exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def reachable_by_3steps_from(node, edges):
    dist1 = edges[node]
    dist2 = []
    for d1 in dist1:
        dist2 += edges[d1]
    reachable = []
    for d2 in dist2:
        reachable += edges[d2]
    return reachable


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

start, goal = map(int, input().split())
skip_path = [[] for _ in range(n)]
for i in range(n):
    skip_path[i] = reachable_by_3steps_from(i, edges)

todo = deque([])
seen = [False] * n
seen[start-1] = True
for to in skip_path[start-1]:
    todo.append([to, 1])
    if to == goal-1:
        print(1)
        exit()

while todo:
    node, dist = todo.popleft()
    if seen[node]:
        continue
    seen[node] = True
    for to in skip_path[node]:
        todo.append([to, dist+1])
        if to == goal-1:
            print(dist+1)
            exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
path=[[] for i in range(n+1)]
for i in range(m):
    u,v=map(int,input().split())
    path[u].append(v)
S,T=map(int,input().split())

que=[S]
flag=[0]*(n+1)
flag[S]=1
data=[[] for i in range(n+1)]

while que:
    h=que.pop()
    lst=[h]
    for i in range(3):
        u=[]
        for j in lst:
            for k in path[j]:
                u.append(k)
        lst=u
    lst=list(set(lst))
    for i in lst:
        if i==h:
            continue
        data[h].append(i)
        if flag[i]==0:
            flag[i]=1
            que.append(i)

que=[S]
flag=[0]*(n+1)
flag[S]=1
count=0
while que:
    count+=1
    H=[]
    for u in que:
        for v in data[u]:
            if flag[v]==0:
                H.append(v)
                flag[v]=1
            if v==T:
                print(count)
                break
        else:
            continue
        break
    else:
        que=H
        continue
    break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n,m=map(int,input().split())
path=[[] for i in range(n+1)]
for i in range(m):
    u,v=map(int,input().split())
    path[u].append(v)
S,T=map(int,input().split())


que=[S]
flag=[0]*(n+1)
flag[S]=1
list1=[]
list2=[]

while que:
    h=que.pop()
    lst=[h]
    for i in range(3):
        u=[]
        for j in lst:
            for k in path[j]:
                u.append(k)
        lst=u
    lst=list(set(lst))
    for i in lst:
        if i==h:
            continue
        list1.append(h)
        list2.append(i)
        if flag[i]==0:
            flag[i]=1
            que.append(i)
d=[1]*len(list1)

csr=csr_matrix((d,(list1,list2)),(n+1,n+1))
ans=dijkstra(csr,indices = S)
if ans[T]<n:
    print(int(ans[T]//1))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
gken=[[] for i in range(n)]
for i in range(n):
    for j in g[i]:
        for j2 in g[j]:
            for j3 in g[j2]:
                gken[i].append(j3)

s,t=map(int,input().split())
s-=1
t-=1
q=deque([[s,0]])
v=[0]*n
while q:
    p=q.popleft()
    v[p[0]]=1
    for j3 in gken[p[0]]:
        if j3==t:
            print(p[1]+1)
            exit()
        if v[j3]==0:
            v[j3]=1
            q.append([j3,p[1]+1])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
s,t=map(int,input().split())
s-=1
t-=1
q=deque([[s,0]])
v=[0]*n
while q:
    p=q.popleft()
    v[p[0]]=1
    for j in g[p[0]]:
        for j2 in g[j]:
            for j3 in g[j2]:
                if j3==t:
                    print(p[1]+1)
                    exit()
                if v[j3]==0:
                    v[j3]=1
                    q.append([j3,p[1]+1])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(3*n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[3*u].append(3*v+1)
        E[3*u+1].append(3*v+2)
        E[3*u+2].append(3*v)
    s,t=map(int,input().split())
    s-=1; t-=1

    # DFS
    from collections import deque
    d=[INF]*(3*n)
    d[3*s]=0

    def dfs(v):
        for nv in E[v]:
            if(d[nv]>d[v]+1):
                d[nv]=d[v]+1
                dfs(nv)

    dfs(3*s)
    ans=d[3*t]
    print(ans//3 if(ans!=INF) else -1)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(3*n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[3*u].append(3*v+1)
        E[3*u+1].append(3*v+2)
        E[3*u+2].append(3*v)
    s,t=map(int,input().split())
    s-=1; t-=1

    # DFS
    from collections import deque
    d=[INF]*(3*n)
    d[3*s]=0
    stack=[]
    stack.append(3*s)
    while(stack):
        v=stack.pop()
        for nv in E[v]:
            if(d[nv]>d[v]+1):
                d[nv]=d[v]+1
                stack.append(nv)
    ans=d[3*t]
    print(ans//3 if(ans!=INF) else -1)
resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
E - Hopscotch Addict
https://atcoder.jp/contests/abc132/tasks/abc132_e

"""
import sys
from collections import deque


def solve(n, m, graph, s, t):
    kkp =  dict()
    for i in range(1, n+1):
        kk = []
        for k in set(graph[i]):
            kk.extend(graph[k])
        res = []
        for x in set(kk):
            res.extend(graph[x])
        kkp[i] = set(res)

    q = deque([(t, 0)])
    visited = set([t])
    while q:
        cp, step = q.popleft()
        for np in kkp[cp]:
            if np == s:
                return step + 1
            if np not in visited:
                q.append((np, step+1))
                visited.add(np)
    return -1


def main(args):
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[v].append(u)
    s, t = map(int, input().split())
    ans = solve(n, m, graph, s, t)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
E - Hopscotch Addict
https://atcoder.jp/contests/abc132/tasks/abc132_e

"""
import sys
from collections import deque


def solve(n, m, graph, s, t):
    kkp =  dict()
    for i in range(1, n+1):
        kk = []
        for k in graph[i]:
            kk.extend(graph[k])
        res = []
        for x in set(kk):
            res.extend(graph[x])
        kkp[i] = set(res)

    q = deque([(t, 0)])
    visited = set([t])
    while q:
        cp, step = q.popleft()
        for np in kkp[cp]:
            if np == s:
                return step + 1
            if np not in visited:
                q.append((np, step+1))
                visited.add(np)
    return -1


def main(args):
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[v].append(u)
    s, t = map(int, input().split())
    ans = solve(n, m, graph, s, t)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
E - Hopscotch Addict
https://atcoder.jp/contests/abc132/tasks/abc132_e

"""
import sys
from collections import deque


def solve(n, m, graph, s, t):
    kkp =  dict()
    for i in range(1, n+1):
        kk = []
        for k in graph[i]:
            kk.extend(graph[k])
        res = []
        for x in kk:
            res.extend(graph[x])
        kkp[i] = set(res)

    q = deque([(t, 0)])
    visited = set([t])
    while q:
        cp, step = q.popleft()
        for np in kkp[cp]:
            if np == s:
                return step + 1
            if np not in visited:
                q.append((np, step+1))
                visited.add(np)
    return -1


def main(args):
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[v].append(u)
    s, t = map(int, input().split())
    ans = solve(n, m, graph, s, t)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
E - Hopscotch Addict
https://atcoder.jp/contests/abc132/tasks/abc132_e

"""
import sys
from collections import deque

def solve(n, m, graph, s, t):
    kkp =  dict()
    for i in range(1, n+1):
        kk = []
        for k in graph[i]:
            kk.extend(graph[k])
        res = []
        for x in kk:
            res.extend(graph[x])
        kkp[i] = set(res)

    q = deque([(t, 0)])
    visited = set([t])
    while q:
        cp, step = q.popleft()
        if cp == s:
            return step
        for np in kkp[cp]:
            if np not in visited:
                q.append((np, step+1))
                visited.add(np)
    return -1


def main(args):
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[v].append(u)
    s, t = map(int, input().split())
    ans = solve(n, m, graph, s, t)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M=map(int,input().split())
# 頂点の番号は0-initialのまま扱う
E=set() # 辺から成るset
for i in range(M):
    u,v=map(int,input().split())
    E.add((u,v))
S,T=map(int,input().split())

d1=[set() for i in range(N+1)] # d1[i]=頂点iからの距離が1であるような頂点vから成るset
for e in E:
    u=e[0];v=e[1]
    d1[u].add(v)

d2=[set() for i in range(N+1)] # d2[i]=頂点iからの距離が2であるような頂点vから成るset
for e in E:
    u=e[0];v=e[1]
    d2[u].update(d1[v])

d3=[set() for i in range(N+1)]
for e in E:
    u=e[0];v=e[1]
    d3[u].update(d2[v])
'''
print(e)
print(d1)
print(d2)
print(d3)
'''
dis=[-1 for i in range(N+1)];dis[S]=0 # 頂点Sからの距離
# WFS
q=deque() # 遅ければlistで実装
q.append(S)
while q:
#    print(q) #DB
#    print(dis) #DB
    u=q.popleft()
    vs=[v for v in d3[u] if dis[v]==-1]
    for v in vs:
        dis[v]=dis[u]+1
    q.extend(vs)

print(dis[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M=map(int,input().split())
Out=[set() for i in range(N+1)]  # 頂点の番号は0-initialのまま扱う
for i in range(M):
    u,v=map(int,input().split())
    Out[u].add(v)
S,T=map(int,input().split())

Out2=[set() for i in range(N+1)]
for i in range(1,N+1):
    for j in Out[i]:
        Out2[i].update(Out[j])

Out3=[set() for i in range(N+1)]
for i in range(1,N+1):
    for j in Out[i]:
        Out3[i].update(Out2[j])

#print(Out)
#print(Out2)
#print(Out3)

dis=[-1 for i in range(N+1)];dis[S]=0 # 頂点Sからの距離
# WFS
q=deque() # 遅ければlistで実装
q.append(S)
while q:
#    print(q) #DB
#    print(dis) #DB
    u=q.popleft()
    vs=[v for v in Out3[u] if dis[v]==-1]
    for v in vs:
        dis[v]=dis[u]+1
    q.extend(vs)

print(dis[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M=map(int,input().split())
Out=[set() for i in range(N+1)]  # 頂点の番号は0-initialのまま扱う
for i in range(M):
    u,v=map(int,input().split())
    Out[u].add(v)
S,T=map(int,input().split())

Out2=[set() for i in range(N+1)]
for i in range(1,N+1):
    for j in Out[i]:
        Out2[i].update(Out[j])

Out3=[set() for i in range(N+1)]
for i in range(1,N+1):
    for j in Out[i]:
        Out3[i].update(Out2[j])

#print(Out)
#print(Out2)
#print(Out3)

dis=[-1 for i in range(N+1)];dis[S]=0 # 頂点Sからの距離
# WFS
q=deque() # 遅ければlistで実装
q.append(S)
while q:
#    print(q) #DB
#    print(dis) #DB
    u=q.popleft()
    vs=[v for v in Out3[u] if dis[v]==-1]
    for v in vs:
        dis[v]=dis[u]+1
    q.extend(vs)

print(dis[T])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input=sys.stdin.readline

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

D=defaultdict(int)
L=[s]
LL,LLL,LLLL,l=[],[],[],[]
cnt=0

while L:
    if t in L:
        print(cnt)
        exit()
    for i in L:
        for j in G[i]:
            LL.append(j)
    for ii in LL:
        for jj in G[ii]:
            LLL.append(jj)
    for iii in LLL:
        for jjj in G[iii]:
            LLLL.append(jjj)
    for iiii in LLLL:
        if D[iiii]==0:
            D[iiii]=1
            l.append(iiii)
    L,LL,LLL,LLLL=l,[],[],[]
    l=[]
    cnt+=1

print(-1)

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
# N-1辺表示をグラフ表示に
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
S, T = map(lambda x:int(x)-1, input().split())


q = [S]
checked = [False]*N
checked[S] = True

ok = False
c = 0
while q:
    c += 1
    qq = []
    if c % 3 == 0:
        for p in q:
            for np in graph[p]:
                if np == T:
                    ok = True
                    break
                if not checked[np]:
                    qq.append(np)
                    checked[np] = True
    else:
        for p in q:
            for np in graph[p]:
                qq.append(np)
    if ok:
        break
    q = qq

if ok:
    print(c//3)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N,M = map(int,readline().split())
UVST = np.array(read().split(),np.int32)
S,T = UVST[-2:]
UV = UVST[:-2]; U = UV[::2]; V = UV[1::2]

rows = []
cols = []
U1 = U+N; U2 = U1+N
V1 = V+N; V2 = V1+N
# ken
rows.append(U); cols.append(V1)
# ken
rows.append(U1); cols.append(V2)
# pa
rows.append(U2); cols.append(V)
row = np.concatenate(rows)
col = np.concatenate(cols)
graph = csr_matrix((np.ones(len(row)),(row,col)),(N+N+N+1,N+N+N+1))

dist = dijkstra(graph,directed=True,indices=S)[T]

answer = -1 if dist == np.inf else int(dist)//3
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(i) for i in input().split()]
v = [[] for i in range(n)]
for i in range(m):
	uu, vv = [int(j) for j in input().split()]
	v[uu - 1].append(vv - 1)
s, t = [int(i) for i in input().split()]

def three_steps(s0, v):
	firsts = v[s0]
	seconds = []
	for i in firsts:
		seconds += v[i]
	thrids = []
	for i in seconds:
		thrids += v[i]
	return list(set(thrids))

v3 = [three_steps(v0, v) for v0 in range(n)]

visited = [-1 for i in range(n)]
visited[s - 1] = 0
que = [s - 1]
while len(que) > 0:
	goal = False
	p = que[0]
	que = que[1:]
	for i in v3[p]:
		if visited[i] == -1:
			visited[i] = visited[p] + 1
			if i == t - 1:
				goal = True
				break
			else:
				que.append(i)
	if goal:
		break
print(visited[t - 1])

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]

vs = set()
def dfs_w(v, d, t):
    # dfs while版 
    r = -1
    stack = [v]
    path = []
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            path.pop()
        else:
            path.append(v)
            vs.add(v)
            for u in d[v]:
                if u == t:
                    #print(r,path)
                    if r != -1:
                        r = min(len(path)//3, r)
                    else:
                        r = len(path)//3
                    #continue
                if u in vs:
                    continue
                stack += [-v, u]
    return r

from collections import deque
def bfs(v,d,t,N):
    queue=deque([v])
    dist = [0] * (N+1)
    while True:
        if len(queue) == 0:
            break
        v = queue.popleft()
        vs.add(v)
        for u in d[v]:
            if u in vs:
                continue
            dist[u] = dist[v] + 1
            if u == t:
                return dist[u]//3
            queue.append(u)
    return -1

d = [set() for _ in range(3*N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(N+b)
    d[N+a].add(2*N+b)
    d[2*N+a].add(b)

s, t = [int(x) for x in input().strip().split(" ")]
print(bfs(s, d, t, 3*N+1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    a,e=map(int,input().split())
    graph[a-1].append(e+n-1)
    graph[a+n-1].append(e+2*n-1)
    graph[a+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
visited=[False]*(3*n)
dfs_alpha_memory = [3*n]*(3*n)
dfs_skipped = [set() for _ in range(3*n)]
dfs_whether_precise = [False]*(3*n)

def dfs(checking, alpha=3*n):
    if dfs_alpha_memory[checking] < alpha:
        return dfs_alpha_memory[checking]
    elif dfs_whether_precise[checking]:
        moves = dfs_skipped[checking]
    else:
        moves = graph[checking]
    pr_flag = True
    looped = set()
    visited[checking]=True
    initial_alpha = alpha
    for next in moves:
        if t==next:
            alpha=1
            looped = set()
            dfs_whether_precise[checking] = True
            break
        if visited[next]:
            looped.add(next)
            continue
        alpha=min(alpha, dfs(next, alpha-1)+1)
        pr_flag &= dfs_whether_precise[next]
    else:
        if alpha >= initial_alpha:
            alpha = 3*n
    dfs_skipped[checking] &= looped
    dfs_alpha_memory[checking] = min(alpha, dfs_alpha_memory[checking])
    dfs_whether_precise[checking] &= pr_flag
    visited[checking] = False
    return alpha

ans = dfs(s)//3
if ans >= n:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    a,e=map(int,input().split())
    graph[a-1].append(e+n-1)
    graph[a+n-1].append(e+2*n-1)
    graph[a+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
visited=[False]*(3*n)
dfs_alpha_memory = [3*n]*(3*n)
skipped = [set() for _ in range(3*n) ]

def dfs(checking, alpha=3*n):
    if dfs_alpha_memory[checking] < alpha:
        return dfs_alpha_memory[checking]
    looped = set()
    visited[checking]=True
    initial_alpha = alpha
    for next in graph[checking]:
        if t==next:
            alpha=1
            break
        if visited[next]:
            looped.add(next)
            continue
        alpha=min(alpha, dfs(next, alpha-1)+1)
    else:
        if alpha >= initial_alpha:
            alpha = 3*n
    skipped[checking] &= looped
    dfs_alpha_memory[checking] = min(alpha, dfs_alpha_memory[checking])
    visited[checking] = False
    return alpha

ans = dfs(s)//3
if ans >= n:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    a,e=map(int,input().split())
    graph[a-1].append(e+n-1)
    graph[a+n-1].append(e+2*n-1)
    graph[a+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
visited=[False]*(3*n)

def dfs(checking,length=0):
    visited[checking]=True
    ret=3*n
    for next in graph[checking]:
        if t==next:
            ret=length+1
            break
        if visited[next]:
            continue
        ret=min(ret,dfs(next,length+1))
    visited[checking]=False
    return ret

ans = dfs(s,0)//3
if ans >= n:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
graph = [[] for _ in range(n)]
for u, v in LIR(m):
    graph[u - 1] += [v - 1]


s, t = LI()
dist = [[INF for _ in range(3)] for _ in range(n)]
dist[s - 1][0] = 0
que = deque([(s - 1, 0)])
while que:
    cur, cost = que.pop()
    for nxt in graph[cur]:
        if cost + 1 < dist[nxt][(cost + 1) % 3]:
            dist[nxt][(cost + 1) % 3] = cost + 1
            que += [(nxt, cost + 1)]



if dist[t - 1][0] == INF:
    print(-1)
else:
    print(dist[t - 1][0] // 3)

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

g = [[] for _ in range(3 * n)]

for u, v in uv:
    a = u - 1
    b = v - 1
    g[a].append(n + b)
    g[n+a].append(n*2 + b)
    g[n*2+a].append(b)

#print(g)

s -= 1
t -= 1
ans = 0
temp = [s]
while 1:
    ans += 1
    next = []
    for x in temp:
        next = next + g[x]
        g[x] = []
    if len(next) == 0:
        print(-1)
        exit()
    if t in next:
        print(ans // 3)
        exit()
    temp = [] + list(set(next))

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

g = [[] for _ in range(3 * n)]

for u, v in uv:
    a = u - 1
    b = v - 1
    g[a].append(n + b)
    g[n+a].append(n*2 + b)
    g[n*2+a].append(b)

#print(g)

s -= 1
t -= 1
ans = 0
temp = [s]
while 1:
    ans += 1
    next = []
    for x in temp:
        next = next + g[x]
        g[x] = []
    if len(next) == 0:
        print(-1)
        exit()
    if t in next:
        print(ans // 3)
        exit()
    temp = [] + next

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
INFTY = 10**10
def ken(x):
    if x not in K:
        K[x] = []
    for y in G[x]:
        for z in G[y]:
            for w in G[z]:
                K[x].append(w)

N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    u,v = map(int,input().split())
    G[u].append(v)
S,T = map(int,input().split())
K = {}
hist = [0 for _ in range(N+1)]
front = deque([S])
while front:
    cur = front.popleft()
    ken(cur)
    hist[cur]=1
    for x in K[cur]:
        if hist[x]==0:
            front.append(x)
d = [INFTY for _ in range(N+1)]
d[S] = 0
hist = [0 for _ in range(N+1)]
heap = [(0,S)]
cur = (0,S)
while heap:
    while heap:
        cur = heapq.heappop(heap)
        if hist[cur[1]]==0:
            hist[cur[1]] = 1
            break
    for x in K[cur[1]]:
        if hist[x]==0 and d[cur[1]]+1<d[x]:
            d[x]=d[cur[1]]+1
            heapq.heappush(heap,(d[x],x))

if d[T]>=INFTY:
    print(-1)
else:
    print(d[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy, sys

n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())
con = [None]*(n+1)
q = deque([s])
pre_q = deque()
dejab = []
depth = 0

for i in range(m):
    a, b = edges[i][0], edges[i][1]
    if con[a] == None:
        con[a] = [b]
    else:
        con[a] += [b]

count = 1
while not len(q) == 0:
    depth += 1
    pre_q = copy.copy(q)
    if list(q) in dejab and count == 1:
        print(-1)
        sys.exit()
    elif count == 1:
        dejab.append(list(q))
    q.clear()
    for p in pre_q:
        if con[p] == None:
            continue
        for c in con[p]:
            if c == t and count == 3:
                print(int(depth / 3))
                sys.exit()
            q.append(c)
    if count < 3:
        count += 1
    else:
        count = 1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
g = {}
for v in range(1,N*3+1):
    g[v] = []

for _ in range(M):
    u,v = map(int, input().split())
    g[u + N*0].append(v + N*1)
    g[u + N*1].append(v + N*2)
    g[u + N*2].append(v + N*0)

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

visiting = [(S,0)]
visited = {}
while visiting:
    v,d = visiting.pop(0)
    if v in visited:
        continue
    visited[v] = d
    if v == T:
        break

    for v2 in g[v]:
        if v2 in visiting or v2 in visited:
            continue
        visiting.append((v2,d+1))

if T in visited:
    print(visited[T] // 3)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

g = {}
steps = 3
for v in range(1,N*steps+1):
    g[v] = []

for _ in range(M):
    u,v = map(int, input().split())
    g[u + N*0].append(v + N*1)
    g[u + N*1].append(v + N*2)
    g[u + N*2].append(v + N*0)

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

visiting = [(S,0)]
visited = {}
while visiting:
    v,d = visiting.pop(0)
    if v in visited:
        continue
    visited[v] = d
    if v == T:
        break

    for v2 in g.get(v,()):
        if v2 in visiting or v2 in visited:
            continue
        visiting.append((v2,d+1))
if T in visited:
    print(visited[T] // steps)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

g = {}
steps = 3
for v in range(1,N*steps+1):
    g[v] = []

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

    for idx in range(steps):
        g[u + N*idx].append(v + N*((idx+1) % steps))

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

visiting = [(S,0)]
visited = {}
while visiting:
    v,d = visiting.pop(0)
    if v in visited:
        continue
    visited[v] = d
    if v == T:
        break

    for v2 in g.get(v,()):
        if v2 in visiting or v2 in visited:
            continue
        visiting.append((v2,d+1))
if T in visited:
    print(visited[T] // steps)
else:
    print(-1)