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:
# -*- coding: utf-8 -*-
import sys
# 12:55~
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
uv = [list(map(int,input().split())) for _ in range(M)]
S,T = map(int,input().split())

S -= 1
T -= 1
#%%
adj_list = [[] for _ in range(N)]
for u,v in uv:
    adj_list[u-1].append(v-1)

INF = 10**9+7
dist = [[INF]*3 for _ in range(N)]
dist[S][2] = 0

stack = [[S,0]]
while stack:
    v,count = stack.pop()
    nxt_v = adj_list[v]
    cnt = count%3
    for nv in nxt_v:
        if dist[nv][cnt]>(count+1)//3:
            dist[nv][cnt] = min(dist[nv][cnt],(count+1)//3)
            stack.append([nv,count+1])
            
            
if dist[T][2]==INF:
    ans = -1
else:
    ans = dist[T][2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# 12:55~
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
uv = [list(map(int,input().split())) for _ in range(M)]
S,T = map(int,input().split())

S -= 1
T -= 1
#%%
adj_list = [[] for _ in range(N)]
for u,v in uv:
    adj_list[u-1].append(v-1)

INF = 10**9+7
dist = [INF]*N
dist[S] = 0

def dfs(vartex, count):
    nxt_v = adj_list[vartex]
    if count%3==2:
        for nv in nxt_v:
            if dist[nv]>(count+1)//3:
                dist[nv] = min(dist[nv],(count+1)//3)
                dfs(nv,count+1)                
    else:
        for nv in nxt_v:
            dfs(nv,count+1)
    
dfs(S,0)
if dist[T]==INF:
    ans = -1
else:
    ans = dist[T]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline


def BFS():
    n,m=map(int,input().split())
    color=["white" for _ in range(n+1)]
    D=[-1]*(n+1)
    M=[[] for _ in range(n+1)]

    for u,v in [list(map(int,input().split())) for _ in range(m)]:
        M[u].append(v)
    s,t=map(int,input().split())
    queue=deque([[s,0,0]])

    while len(queue)!=0:
        num,cnt,point=queue.popleft()
        if cnt==3:
            if color[num]=="white":
                cnt=0
                point +=1
                D[num]=point
                color[num]="black"
                for i in M[num]:
                    queue.append([i,cnt+1,point])
        else:
            for i in M[num]:
                queue.append([i,cnt+1,point])
    return D[t]


print(BFS())

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


def BFS(s):
    color=["white" for _ in range(n+1)]
    D=[-1]*(n+1)
    M=[[] for _ in range(n+1)]

    for u,v in UV:M[u].append(v)
    queue=deque([[s,0,0]])

    while len(queue)!=0:
        num,cnt,point=queue.popleft()
        if cnt==3:
            if color[num]=="white":
                cnt=0
                point +=1
                D[num]=point
                color[num]="black"
                for i in M[num]:
                    queue.append([i,cnt+1,point])
        else:
            for i in M[num]:
                queue.append([i,cnt+1,point])
    return D


n,m=map(int,input().split())
UV=[list(map(int,input().split())) for _ in range(m)]
s,t=map(int,input().split())
print(BFS(s)[t])

Submission status: Time Limit Exceeded

Solution code:
def o(): return map(int,input().split())
n,m = o()
g=[[] for i in range(3*n)]
for i in range(m):
  u,v = o()
  u-=1
  v-=1
  g[u] += [v+n]
  g[u+n] += [v+2*n]
  g[u+2*n] += [v]
s,t = o()
s-=1
t-=1
p=[s]
a=[4*n]*(3*n)
a[s]=0
ans = -1
if s==t:
  ans = 0
  p = []
while p:
  x = p.pop()
  for y in g[x]:
    if a[y] > a[x] + 1:
      a[y] = a[x] + 1
      p = [y] + p
  if a[t] < 4*n:
    ans = a[t]//3
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def o(): return map(int,input().split())
n,m = o()
g=[[] for i in range(n+1)]
for i in range(m):
  u,v = o()
  g[u] += [v]
s,t = o()
a = [[-3,-3,-3] for i in range(n+1)]
a[s][0] = 0
p = [[s,1]]
while p:
  x,i = p.pop()
  for y in g[x]:
    if a[y][i%3]<0:
      a[y][i%3]=i
      p = [[y,i+1]] + p
  if a[t][0] >= 0:
    break
print(a[t][0]//3)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [set([]) for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].add(v)


graph3 = [set([]) for _ in range(n+1)]
for i, g in enumerate(graph):
    if i == 0:
        continue
        
    graph2 = set([])
    for r in g:
        graph2 |= graph[r]

    for r in graph2:
        graph3[i] |= graph[r]


s, t = map(int, input().split())
q = deque([s])
visited = [False] * (n+1)
visited[s] = True
dist = [-1] * (n+1)
dist[s] = 0
while q:
    now = q.popleft()
    for i in graph3[now]:
        if visited[i]:
            continue
        if i == now:
            continue
        q.append(i)
        visited[i] = True
        dist[i] = dist[now] + 1

print(dist[t])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [set([]) for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].add(v)

graph2 = [set([]) for _ in range(n+1)]
graph3 = [set([]) for _ in range(n+1)]
for i, g in enumerate(graph):
    if i == 0:
        continue

    for r in g:
        for w in graph[r]:
            graph3[i] |= graph[w]


s, t = map(int, input().split())
q = deque([s])
visited = [False] * (n+1)
visited[s] = True
dist = [-1] * (n+1)
dist[s] = 0
while q:
    now = q.popleft()
    for i in graph3[now]:
        if visited[i]:
            continue
        if i == now:
            continue
        q.append(i)
        visited[i] = True
        dist[i] = dist[now] + 1

print(dist[t])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [set([]) for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].add(v)

graph2 = [set([]) for _ in range(n+1)]
graph3 = [set([]) for _ in range(n+1)]
for i, g in enumerate(graph):
    if i == 0:
        continue

    for r in g:
        graph2[i] |= graph[r]
    
    for r in graph2[i]:
        graph3[i] |= graph[r]


s, t = map(int, input().split())
q = deque([s])
visited = [False] * (n+1)
visited[s] = True
dist = [-1] * (n+1)
dist[s] = 0
while q:
    now = q.popleft()
    for i in graph3[now]:
        if visited[i]:
            continue
        if i == now:
            continue
        q.append(i)
        visited[i] = True
        dist[i] = dist[now] + 1

print(dist[t])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [set([]) for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].add(v)

graph2 = [set([]) for _ in range(n+1)]
for i, g in enumerate(graph):
    if i == 0:
        continue

    for r in g:
        graph2[i] |= graph[r]

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

for i, g in enumerate(graph2):
    if i == 0:
        continue

    for r in g:
        graph3[i] |= graph[r]


s, t = map(int, input().split())
q = deque([s])
visited = [False] * (n+1)
visited[s] = True
dist = [-1] * (n+1)
dist[s] = 0
while q:
    now = q.popleft()
    for i in graph3[now]:
        if visited[i]:
            continue
        if i == now:
            continue
        q.append(i)
        visited[i] = True
        dist[i] = dist[now] + 1

print(dist[t])

Submission status: Time Limit Exceeded

Solution code:
import heapq as h
import sys

input=sys.stdin.readline

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

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

triplehen=[[] for i in range(0,N)]
for i in range(0,N):
    q=[i]
    h.heapify(q)
    sub=[]
    h.heapify(sub)
    count=0
    while 3>count:
        while q!=[]:
            x=h.heappop(q)
            for p in hen[x]:
                h.heappush(sub,p)
            if q==[]:
                count+=1
                if count==3:
                    for j in sub:
                        triplehen[i].append(j)
                else:
                    if sub==[]:
                        count=3
                q=sub
                sub=[]
                h.heapify(sub)
                break
triplehen=[list(set(triplehen[i])) for i in range(0,N)]

ans=[-1 for i in range(0,N)]
ans[S-1]=0

q=[]
q.append(S-1)
h.heapify(q)
sub=[]
h.heapify(sub)
count=0
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in triplehen[x]:
            if ans[p]==-1:
                h.heappush(sub,p)
        if q==[]:
            count+=1
            for j in sub:
                ans[j]=count
            q=sub
            sub=[]
            h.heapify(sub)
            break

print(ans[T-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq as h
import sys

input=sys.stdin.readline

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

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

ans=[-1 for i in range(0,N)]
ans[S-1]=0

q=[]
q.append(S-1)
h.heapify(q)
sub=[]
h.heapify(sub)
count=0
flag=1
while flag==1:
    flag=0
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
                h.heappush(sub,p)
        if q==[]:
            count+=1
            if count%3==0:
                for j in sub:
                    if ans[j]==-1:
                        ans[j]=count//3
                        flag=1
            else:
                flag=1
            q=sub
            sub=[]
            h.heapify(sub)
            break

print(ans[T-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq as h

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

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

ans=[-1 for i in range(0,N)]
ans[S-1]=0

q=[]
q.append(S-1)
h.heapify(q)
sub=[]
h.heapify(sub)
count=0
flag=1
while flag==1:
    flag=0
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
                h.heappush(sub,p)
        if q==[]:
            count+=1
            if count%3==0:
                for j in sub:
                    if ans[j]==-1:
                        ans[j]=count//3
                        flag=1
            else:
                flag=1
            q=sub
            sub=[]
            h.heapify(sub)
            break

print(ans[T-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
n,m = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)

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

G = defaultdict(list)
def dfs(p, s, l):
    if l == 3:
        if s != p:
            G[s].append(p)
    else:
        for i in dic[p]:
            dfs(i, s, l+1)

for i in range(n):
    dfs(i, i, 0)
s,t = map(int,input().split())

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*n
que = deque([s-1])
dist[s-1] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
print(dist[t-1])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)

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

G = defaultdict(list)
def dfs(p, s, l):
    if l == 3:
        if s != p:
            G[s].append(p)
    else:
        for i in dic[p]:
            dfs(i, s, l+1)

for i in range(n):
    dfs(i, i, 0)
s,t = map(int,input().split())

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*n
que = deque([s-1])
dist[s-1] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
print(dist[t-1])

Submission status: Time Limit Exceeded

Solution code:
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, ipti().split()))
    node_next = [set() for _ in range(n)]

    for i in range(m):
        u, v = list(map(int, ipti().split()))
        node_next[u-1].add(v-1)

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

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

    que = deque()
    que.append((s, 0, 0))

    while que:
        cnode, cstate, dist = que.popleft()
        seen[cstate][cnode] = 1
        dist += 1
        nstate = (cstate + 1) % 3
        for nnode in node_next[cnode]:
            if seen[nstate][nnode] == 0:
                if nstate == 0 and nnode == t:
                    print(dist // 3)
                    sys.exit()
                else:
                    que.append((nnode, nstate, dist))

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, ipti().split()))
    node_next = [set() for _ in range(n)]

    for i in range(m):
        u, v = list(map(int, ipti().split()))
        u, v = u - 1, v - 1
        node_next[u].add(v)

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

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

    que = deque()
    que.append((s, 0, 0))

    while que:
        cnode, cstate, dist = que.popleft()
        seen[cnode][cstate] = 1
        dist += 1
        nstate = (cstate + 1) % 3
        for nnode in node_next[cnode]:
            if nstate == 0 and nnode == t:
                print(dist // 3)
                sys.exit()
            else:
                if seen[nnode][nstate] == 0:
                    que.append((nnode, nstate, dist))

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, ipti().split()))
    node_next = [[[] for __ in range(3)] for _ in range(n)]

    for i in range(m):
        u, v = list(map(int, ipti().split()))
        u, v = u - 1, v - 1
        node_next[u][0].append((v, 1))
        node_next[u][1].append((v, 2))
        node_next[u][2].append((v, 0))

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

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

    que = deque()
    que.append((s, 0, 0))

    while que:
        cnode, cstate, dist = que.popleft()
        seen[cnode][cstate] = 1
        dist += 1
        for nnode, nstate in node_next[cnode][cstate]:
            if nnode == t and nstate == 0:
                print(dist // 3)
                sys.exit()
            else:
                if seen[nnode][nstate] == 0:
                    que.append((nnode, nstate, dist))

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

#1回ずつ数えて答えを3で割る
N, M = lr()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(M):
    u, v = lr()
    graph[u].append(v)

S, T = lr()
que = deque([(S, 0)])
time_set = [set() for _ in range(N+1)] # 1-indexed
while que:
    q, time = que.popleft()
    if time > M * 3:
        break
    for next in graph[q]:
        if time_set[next] == (time+1) % 3:
            continue
        if next == T and (time+1) % 3 == 0:
            print((time+1)//3); exit()
        que.append((next, time+1))
        time_set[next].add((time+1)%3)

print(-1); exit()
# 52

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve():
    N, M = map(int, input().split())
    V = {i:[] for i in range(1, N+1)}
    for _ in range(M):
        u, v = map(int, input().split())
        V[u].append(v)

    S, T = map(int, input().split())
    q = deque([(S, 0)])
    used = [[False]*3 for _ in range(N+1)]
    while q:
        a, dist = q.popleft()
        used[a][dist%3] = True
        if a==T and dist%3==0:
            break
        for b in V[a]:
            if used[b][(dist+1)%3]:continue
            q.append((b, dist+1))

    if a==T and dist%3==0:
        print(dist//3)
    else:
        print(-1)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(s, t, n, V):
    q = deque([(s, 0)])
    used = [False] * (n+1)
    while q:
        a, dist = q.popleft()
        used[a] = True
        if a==t:
            break
        for b in V[a]:
            if used[b]:continue
            q.append((b, dist+1))
    if a!=t:
        return -1
    else:
        return -1 if dist%3 else dist//3


def solve():
    INF = 10**25
    N, M = map(int, input().split())
    V = {i:[] for i in range(1, 3*N+1)}
    for _ in range(M):
        u, v = map(int, input().split())
        V[u].append(v+(N))
        V[u+(N)].append(v+(2*N))
        V[u+(2*N)].append(v)

    S, T = map(int, input().split())
    dist = bfs(S, T, 3*N, V)
    print(dist)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import queue 
MOD = 10**9 +7
INF = 10**9
def main():
    n,m = map(int,input().split())
    V0 = [[] for _ in range(n)]
    V1 = [[] for _ in range(n)]
    V2 = [[] for _ in range(n)]
    for _ in range(m):
        u,v = map(int,input().split())
        u -= 1
        v -= 1
        V0[u].append(v)
        V1[u].append(v)
        V2[u].append(v)
    
    s,t = map(int,input().split())
    s -= 1
    t -= 1
    
    d0 = [-1]*n
    d1 = [-1]*n
    d2 = [-1]*n
    d0[s] = 0

    q = queue.Queue()
    q.put([s,0])
    while q.qsize():
        p = q.get()
        mod = p[1]
        v = p[0]
        if mod == 0:
            for e in V0[v]:
                if d1[e] == -1:
                    d1[e] = d0[v] + 1
                    q.put([e,1])

        elif mod == 1:
            for e in V1[v]:
                if d2[e] == -1:
                    d2[e] = d1[v] + 1
                    q.put([e,2])
        
        else:
            for e in V2[v]:
                if e == t:
                    print((d2[v] + 1)//3)
                    exit()           
                if d0[e] == -1:
                    d0[e] = d2[v] + 1
                    q.put([e,0])
    
    if d0[t] == -1:
        print(-1)
   
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue 
MOD = 10**9 +7
INF = 10**9
def main():
    n,m = map(int,input().split())
    V0 = [[] for _ in range(n)]
    V1 = [[] for _ in range(n)]
    V2 = [[] for _ in range(n)]
    for _ in range(m):
        u,v = map(int,input().split())
        u -= 1
        v -= 1
        V0[u].append(v)
        V1[u].append(v)
        V2[u].append(v)
    
    s,t = map(int,input().split())
    s -= 1
    t -= 1
    
    d0 = [-1]*n
    d1 = [-1]*n
    d2 = [-1]*n
    d0[s] = 0

    q = queue.Queue()
    q.put([s,0])
    while q.qsize() != 0:
        p = q.get()
        mod = p[1]
        v = p[0]
        if mod == 0:
            for e in V0[v]:
                if d1[e] == -1:
                    d1[e] = d0[v] + 1
                    q.put([e,1])

        elif mod == 1:
            for e in V1[v]:
                if d2[e] == -1:
                    d2[e] = d1[v] + 1
                    q.put([e,2])
        
        else:
            for e in V2[v]:
                if d0[e] == -1:
                    d0[e] = d2[v] + 1
                    q.put([e,0])
    
    if d0[t] == -1:
        print(-1)
    else:
        print(d0[t]//3)
   
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque


def bfs(V, s, t):
    q = deque([(0, s)])
    used = set()
    
    while q:
        dist, a = q.popleft()
        used.add(a)
        if a == t:
            break
        for b in V[a]:
            if b in used: continue
            q.append((dist+1, b))
    
    if a != t:
        dist = -1
    else:
        dist = -1 if dist%3 else dist//3
    return dist


if __name__ == "__main__":
    V = defaultdict(list)
    N, M = map(int, input().split())
    for _ in range(M):
        u, v = map(int, input().split())
        V[u].append(v*(N+1))
        V[u*(N+1)].append(v*(2*N+1))
        V[u*(2*N+1)].append(v)

    S, T = map(int, input().split())
    dist = bfs(V, S, T)
    print(dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy

N,M=map(int,input().split())
UV=[list(map(int,input().split())) for i in range(M)]
S,T=map(int,input().split())

data=[[] for i in range(N+1)]
for u,v in UV:
    data[u].append(v)

visited={S}
visited1=set()
visited2=set()
stack=deque([[S,0]])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        z=(m+1)

        if z%3==0:
            if p in visited:
                continue
            elif p == T:
                print(z//3)
                exit()
        if z%3==1:
            if p in visited1:
                continue
            else:
                visited1.add(p)
        if z%3==2:
            if p in visited2:
                continue
            else:
                visited2.add(p)
        stack.append([p,z])

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy

N,M=map(int,input().split())
UV=[list(map(int,input().split())) for i in range(M)]
S,T=map(int,input().split())

data=[[] for i in range(N+1)]
for u,v in UV:
    data[u].append(v)

visited={S}
visited1=set()
visited2=set()
stack=deque([[S,0]])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        z=(m+1)

        if z%3==0:
            if p in visited:
                continue
            elif p == T:
                print(z//3)
                exit()
        if z%3==1:
            if p in visited1:
                continue
            else:
                visited1.add(p)
        if z%3==2:
            if p in visited2:
                continue
            else:
                visited1.add(2)
        stack.append([p,z])

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy

N,M=map(int,input().split())
UV=[list(map(int,input().split())) for i in range(M)]
S,T=map(int,input().split())

data=[[] for i in range(N+1)]
for u,v in UV:
    data[u].append(v)

visited={S}
stack=deque([[S,0]])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        z=(m+1)
        if z%3==0:
            if p in visited:
                continue
            elif p == T:
                print(z//3)
                exit()
        stack.append([p,z])

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque

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

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

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

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

# dist[S] = 0


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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque

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

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

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

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

# dist[S] = 0


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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque

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

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

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

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

# dist[S] = 0


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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque

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

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

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

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

# dist[S] = 0


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

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