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:
N,M = map(int, input().split())

# N is the number of vertices
# M is the number of edges

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

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

S,T = map(int, input().split())
# S is start
# T is target


def move(start, steps):
    current_locations = set()
    next_locations = set()
    current_locations.add(start)

    for _ in range(steps):
        nxt = set()
        for v in current_locations:
            for v2 in g.get(v, ()):
                nxt.add(v2)
        current_locations = nxt

    return current_locations

visiting = [(S,0)]
visited = {}

while visiting:
    v,kkp = visiting.pop(0)
    if v in visited:
        continue

    visited[v] = kkp
    if v == T:
        break

    for v2 in move(v,3):
        if v2 in visiting or v2 in visited:
            continue
        visiting.append((v2,kkp+1))

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

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(s) for s in input().split()]
lst=[]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  lst.append([a,b+N])
  lst.append([a+N,b+N+N])
  lst.append([a+N+N,b])

#########深さ優先探索DFS
#########辺がソートされていなくてもよいとする
#########到達可能なもののうち新しく追加されたものを見る
#########訪れた順番を出力
def dfs(vertex_list,edge_list,start,goal):
  reach=[[start,1,0]]
  e_list=[[e[0],e[1],0] for e in edge_list]
  vertex=start
  endflag=0
  depth=1
  while True :
    ###まずvertexから到達可能なものをすべてreachに入れる
    #辺の始点がvertexであるもの
    for e in e_list:
      if (e[0]==vertex and e[2]==0):
        reach.append([e[1],0,depth])
        e[2]=1
      elif (e[1]==vertex and e[2]==0):
        reach.append([e[0],0,depth])
        e[2]=1
    ###起点になっていないもののうち最後にreachに入ったものを、次の起点とする
    for i in range(len(reach)+1):
      if reach[-i][1]==0 :
        vertex=reach[-i][0]
        if vertex==goal:    ####goalにたどり着けば終了
          return reach[-i][2]
          break
        depth=reach[-i][2]+1
        #####ここでprint(vertex)などを入れる
        reach[-i][1]=1
        break
      if i==len(reach):  ####全ての場所に行っていれば終了
        return -3
        break

print(dfs([],lst,1,3)//3)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
UV = np.array([input().split() for _ in range(M)], dtype=np.int32)
U = UV[:,0] * 3
V = UV[:,1] * 3
S,T = map(int,input().split())
 
rows = np.zeros(3*M, dtype=np.int32)
cols = np.zeros(3*M, dtype=np.int32)
 
rows[:M] = U
rows[M:2*M] = U + 1
rows[2*M:] = U + 2
cols[:M] = V + 1
cols[M:2*M] = V + 2
cols[2*M:] = V
 
dist = dijkstra(csr_matrix((np.ones_like(rows), (rows, cols)), (3*N+3, 3*N+3)), indices = 3*S, unweighted=True)
 
answer = -1 if dist[3*T] > 3*N else int(dist[3*T]//3)
print(answer)

Submission status: Time Limit Exceeded

Solution code:


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

N, M = list(map(int, input().split()))
uv = []
for i in range(M):
	uv.append(list(map(int, input().split())))
S, T = list(map(int, input().split()))
G = [dict() for i in range(N+1)]
for i in range(N + 1):
	G[i]["eda"] = []
	G[i]["second"] = set()
	G[i]["third"] = set()
	G[i]["num"] = -1
for i in range(M):
	G[uv[i][0]]["eda"].append(uv[i][1])
for i in range(N + 1):
	for node in G[i]["eda"]:
		G[i]["second"] = G[i]["second"] | set(G[node]["eda"])
for i in range(N + 1):
	for node in G[i]["eda"]:
		G[i]["third"] = G[i]["third"] | G[node]["second"]

node_set = [S]
G[S]["num"] = 0
times = 1
while True:
	node_set2 = []
	for node in node_set:
		if T in G[node]["third"]:
			print(times)
			exit()
		for node2 in G[node]["third"]:
			if G[node2]["num"] == -1:
				G[node2]["num"] = times
				node_set2.append(node2)

	if len(node_set2) == 0:
		print(-1)
		exit()
	node_set = copy.deepcopy(node_set2)
	times += 1

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

N, M = list(map(int, input().split()))
uv = []
for i in range(M):
	uv.append(list(map(int, input().split())))
S, T = list(map(int, input().split()))
G = [dict() for i in range(N+1)]
for i in range(N + 1):
	G[i]["eda"] = []
	G[i]["num"] = -1
for i in range(M):
	G[uv[i][0]]["eda"].append(uv[i][1])
node_set = [S]
G[S]["num"] = 0
time = 1
while True:
	judge = 0
	first = []
	second = []
	for node in node_set:
		first.extend(G[node]["eda"])
	for node in first:
		second.extend(G[node]["eda"])
	node_set = []
	for node in second:
		if len(G[node]["eda"]) > 0:
			for eda in G[node]["eda"]:
				if eda == T:
					print(time)
					exit()
				if G[eda]["num"] == -1:
					node_set.append(eda)
					G[eda]["num"] == time
					judge = 1
	if judge == 0:
		print(-1)
		exit()
	time += 1

Submission status: Time Limit Exceeded

Solution code:
def add_edge(s, d, edges):
    if s in edges:
        edges[s].append(d)
    else:
        edges[s] = [d]


N, M = [int(x) for x in input().split()]
edges = {}
for _ in range(M):
    s, d = [int(x) for x in input().split()]
    add_edge(s*3 + 0, d*3 + 1, edges)
    add_edge(s*3 + 1, d*3 + 2, edges)
    add_edge(s*3 + 2, d*3 + 0, edges)
S, T = [int(x)*3 + 0 for x in input().split()]

mmax = 3*M
news={S}
count = 0
z = False
once=set()

while news != set():
    if T in news:
        z = True
        break
    olds = news
    news=set()
    for c in olds:
        if c not in edges: continue
        new = set(edges[c])
        new = new - (new & once)
        news = news|new
        once = once|new
    count += 1
    #print(news)
    #print(once)

if z:
    ans = int(count//3)
else:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def add_edge(s, d, edges):
    if s in edges:
        edges[s].append(d)
    else:
        edges[s] = [d]


N, M = [int(x) for x in input().split()]
edges = {}
for _ in range(M):
    s, d = [int(x) for x in input().split()]
    add_edge(s*3 + 0, d*3 + 1, edges)
    add_edge(s*3 + 1, d*3 + 2, edges)
    add_edge(s*3 + 2, d*3 + 0, edges)
S, T = [int(x)*3 + 0 for x in input().split()]

mmax = 3*M
news={S}
count = 0
z = False

while True:
    if T in news:
        z = True
        break
    olds = news
    news=set()
    for c in olds:
        if c not in edges: continue
        new = set(edges[c])
        news = news|new
    count += 1
    if count > mmax:
        break

if z:
    ans = int(count//3)
else:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys
sys.setrecursionlimit(10**8)

N, M = map(int, input().split())
e = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    e[(a, 0)].append((b, 1))
    e[(a, 1)].append((b, 2))
    e[(a, 2)].append((b, 0))

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

d = deque()
d.appendleft((S, 0))

inf = float('inf')
dist = defaultdict(lambda: inf)
dist[(S, 0)] = 0

def BFS(now):
    for v in e[now]:
        if(dist[v] > dist[now] + 1):
            dist[v] = dist[now] + 1
            if(v == (T, 0)):
                return
            BFS(v)
    return

BFS((S, 0))

ans = dist[(T, 0)]
if(ans == inf):
    print(-1)
else:
    print(ans//3)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
e = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    e[(a, 0)].append((b, 1))
    e[(a, 1)].append((b, 2))
    e[(a, 2)].append((b, 0))

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

d = deque()
d.appendleft((S, 0))

inf = float('inf')
dist = defaultdict(lambda: inf)
dist[(S, 0)] = 0

while d:
    next_node = d.pop()
    for v in e[next_node]:
        if(dist[v] > dist[next_node] + 1):
            dist[v] = dist[next_node] + 1
            if(v == (T, 0)):
                break
            d.append(v)

ans = dist[(T, 0)]
if(ans == inf):
    print(-1)
else:
    print(ans//3)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dq = deque()
dq.append((S,0))
while dq:
    v,d = dq.popleft()
    nd = d + 1
    for nv in ad[v]:
        if nv == T and nd % 3 == 0:
            print(nd//3)
            exit()
        if d == 3*10**5:
            print(-1)
            exit()
        dq.append((nv,nd))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dq = deque()
dq.append((S,0))
while dq:
    v,d = dq.popleft()
    nd = d + 1
    for nv in ad[v]:
        if nv == T and nd % 3 == 0:
            print(nd//3)
            exit()
        if d == 10**6:
            print(-1)
            exit()
        dq.append((nv,nd))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from collections import deque
from copy import deepcopy as dc
N, M = map(int, input().split())
e = dd(list)
inf = 10 ** 9
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
S, T = map(int, input().split())

stopped = [inf] * (N + 1)
Q = deque()
Q.append(S)
stopped[S] = 0
saw2 = {i: 0 for i in range(1, N + 1)}
#saw3 = {i: 0 for i in range(1, N + 1)}
while len(Q) != 0:
  s2 = dc(saw2)
  #s3 = dc(saw3)
  p = Q.popleft()
  if stopped[p] >= stopped[T]:
    break
  for q in e[p]:
    for r in e[q]:
      if s2[r] == 1:
        continue
      else:
        s2[r] = 1
      for s in e[r]:
        #if s3[s] == 1:
        #  continue
        #else:
        #  s3[s] = 1
        if stopped[s] > stopped[p] + 1:
          Q.append(s)
          stopped[s] = stopped[p] + 1
if stopped[T] == inf:
  print(-1)
else:
  print(stopped[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from collections import deque
from copy import deepcopy as dc
N, M = map(int, input().split())
e = dd(list)
inf = 10 ** 9
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
S, T = map(int, input().split())

stopped = [inf] * (N + 1)
Q = deque()
Q.append(S)
stopped[S] = 0
saw2 = {i: 0 for i in range(1, N + 1)}
saw3 = {i: 0 for i in range(1, N + 1)}
while len(Q) != 0:
  s2 = dc(saw2)
  s3 = dc(saw3)
  p = Q.popleft()
  if stopped[p] >= stopped[T]:
    break
  for q in e[p]:
    for r in e[q]:
      if s2[r] == 1:
        continue
      else:
        s2[r] = 1
      for s in e[r]:
        if s3[s] == 1:
          continue
        else:
          s3[s] = 1
        if stopped[s] > stopped[p] + 1:
          Q.append(s)
          stopped[s] = stopped[p] + 1
if stopped[T] == inf:
  print(-1)
else:
  print(stopped[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from collections import deque
N, M = map(int, input().split())
e = dd(list)
inf = 10 ** 9
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
S, T = map(int, input().split())

stopped = [inf] * (N + 1)
Q = deque()
Q.append(S)
stopped[S] = 0
while len(Q) != 0:
  p = Q.popleft()
  if stopped[p] >= stopped[T]:
    break
  for q in e[p]:
    for r in e[q]:
      for s in e[r]:
        if stopped[s] > stopped[p] + 1:
          Q.append(s)
          stopped[s] = stopped[p] + 1
if stopped[T] == inf:
  print(-1)
else:
  print(stopped[T])

Submission status: Time Limit Exceeded

Solution code:
import copy
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(b)]
s,t=map(int,input().split())
s=3*s
t=3*t
dd=[[]for i in range(a+1)]
for i in range(b):
  da=c[i][0]
  db=c[i][1]
  dd[da].append(db)
  

d=[[]for i in range(3*(a+1))]
for i in range(len(dd)):
  for j in dd[i]:
      d[3*i].append(3*j+1)
      d[3*i+1].append(3*j+2)
      d[3*i+2].append(3*j)
e=[s]
f=[s]
h=0
for i in range(1,3*a+3):
  g=[]
  for j in f:
    for k in d[j]:
      if k not in e:
        e.append(k)
        g.append(k)
        if k==t:
          print(i//3)
          h=1
          break
    if h==1:
      break
  if h==1:
    break
  if g==[]:
    print(-1)
    break
  f=copy.copy(g)

Submission status: Time Limit Exceeded

Solution code:
import copy
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(b)]
s,t=map(int,input().split())
dd=[[]for i in range(a+1)]
for i in range(b):
  da=c[i][0]
  db=c[i][1]
  dd[da].append(db)
  
d=[[]for i in range(a+1)]
for i in range(a+1):
  for j in dd[i]:
    for k in dd[j]:
      for l in dd[k]:
        d[i].append(l)
e=[s]
f=[s]
h=0
for i in range(1,a+1):
  g=[]
  for j in f:
    for k in d[j]:
      if k not in e:
        e.append(k)
        g.append(k)
        if k==t:
          print(i)
          h=1
          break
    if h==1:
      break
  if h==1:
    break
  if g==[]:
    print(-1)
    break
  f=copy.copy(g)

Submission status: Time Limit Exceeded

Solution code:
import copy
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(b)]
s,t=map(int,input().split())
dd=[[]for i in range(a+1)]
for i in range(b):
  da=c[i][0]
  db=c[i][1]
  dd[da].append(db)
  
d=[[]for i in range(a+1)]
for i in range(a+1):
  for j in dd[i]:
    for k in dd[j]:
      for l in dd[k]:
        d[i].append(l)
e=[s]
f=[s]
h=0
for i in range(1,a+1):
  g=[]
  for j in f:
    for k in d[j]:
      if k not in e:
        e.append(k)
        g.append(k)
  if g==[]:
    print(-1)
    break
  for j in g:
    if j==t:
      print(i)
      h=1
      break
  if h==1:
    break
  f=copy.copy(g)

Submission status: Time Limit Exceeded

Solution code:

# N:頂点の数 M:辺の数
N,M = map(int,input().split())

#INF(10億)
INF = 1000000000

#cost[u][v]は辺e=(u,v)のコスト N*3 * N*3の配列(存在しない場合はINF)
cost = [[ INF for i in range(N*3)] for j in range(N*3)]

for i in range(M):
    #sからtへの辺を張る
    s,t = map(int,input().split())
    #入力は頂点1から始まるため -1 
    #グラフGが u から v への辺を持つ時、G′ 上に 3 辺 u0 → v1, u1 → v2, u2 → v0 を張る
    #u0 →　v1
    cost[s-1][N+t-1] = 1
    #u1 → v2
    cost[N+s-1][2*N+t-1] = 1    
    #u2 → v0
    cost[2*N+s-1][t-1] = 1

#S:始点 T:終点
S,T = map(int,input().split())
#頂点は0から数えるので-1
S -= 1
T -= 1

#頂点sからの最短距離
d = [ [] for i in range(N*3) ]
#すでに使われたかのフラグ
used = [ [] for i in range(N*3) ]

def dijkstra(s):
    for i in range(N*3):
        d[i] = INF
    for i in range(N*3):
        used[i] = False
    #始点の距離は0
    d[s] = 0

    while(True):
        v = -1
        #まだ使われていない頂点のうち距離が最小のものを探す
        for u in range(N*3):
            if ( not used[u] and ( v == -1 or d[u] < d[v])) :
                v = u
        if v == -1 :
            break
        used[v] = True
        for u in range(N*3):
            #各辺のコストは1
            d[u] = min(d[u],d[v]+cost[v][u])

dijkstra(S)

if d[T] == INF :
    print(-1)
else :
    print(int(d[T]/3))

Submission status: Time Limit Exceeded

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

def solve(N, M, to, start, goal):
    def kenkenpa(f):
        t = []
        for k1 in to[f]:
            for k2 in to[k1]:
                for pa in to[k2]:
                    t.append(pa)
        return t

    new_to = [ [] for _ in range(N+1) ]
    for i in range(1, N+1):
        new_to[i] = kenkenpa(i)
    
    costs = [float('inf')] * (N+1)
    costs[start] = 0

    q = deque()
    q.append(start)

    while len(q) != 0:
        u = q.popleft()
        if u == goal: return costs[u]
        for v in new_to[u]:
            if costs[u] + 1 < costs[v]:
                costs[v] = costs[u] + 1
                q.append(v)
    return -1



def main():
    N, M = map(int, input().split())
    to = [ [] for _ in range(N+1) ]
    for _ in range(M):
        u, v = map(int, input().split())
        to[u].append(v)
    S, T = map(int, input().split())
    print(solve(N, M, to, S, T))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#TLE

from collections import deque

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

G = [ [] for row in range(N*3)]

for i in range(M):
    s,t = map(int,input().split())
    G[s-1].append(N+t-1)
    G[N+s-1].append(2*N+t-1)
    G[2*N+s-1].append(t-1)

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

S -= 1
T -= 1
"""
path_G = [-1] * (N*3)
"""
#幅優先探索
def breadth_first_search(S,T,G):
    #深さ
    depth = 0
    #深さの先頭フラグ
    is_sentou = False
    #先頭
    sentou = S
    deq = deque()
    searched = []
    deq.append(S)
    while len(deq) > 0:
        pos = deq.popleft()
        searched.append(pos)
        if pos == sentou:
            depth += 1
            is_sentou = True
        if pos == T:
            return int((depth -1 ) / 3) 
        for next_pos in G[pos]:
            if (next_pos in searched) :
                continue
            if (next_pos in deq):
                continue
            if is_sentou:
                sentou = next_pos
                is_sentou = False
            deq.append(next_pos)
    return -1

#深さ優先探索
def depth_first_search(S,T,G):
    distance=0
    deq = deque()
    searched = []
    deq.append(S)
    while len(deq) > 0:
        pos = deq.pop()
        searched.append(pos)
        distance+=1
        if pos == T:
            return True
        for next_pos in G[pos]:
            if (next_pos in searched) :
                continue
            if (next_pos in deq):
                continue
            deq.append(next_pos)
    return False


"""
def calculate_path(path_G,S,T):
    distance = 0
    i = T
    while path_G[i] != S:
        distance +=1
        i = path_G[i]
    return distance + 1
"""

print(breadth_first_search(S,T,G))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(3 * N)]
L = [-3 for _ in range(3 * N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[3*u+0].append(3*v+1)
    G[3*u+1].append(3*v+2)
    G[3*u+2].append(3*v+0)
s, t = map(int, input().split())
S = 3 * (s-1)
T = 3 * (t-1)

L[S] = 0
Frontier = [S]
while Frontier:
    v = Frontier.pop(0)
    for i in G[v]:
        if L[i] < 0:
            Frontier.append(i)
            L[i] = L[v] + 1

print(L[T]//3)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(3 * N)]
L = [0 for _ in range(3 * N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[3*u+0].append(3*v+1)
    G[3*u+1].append(3*v+2)
    G[3*u+2].append(3*v+0)
s, t = map(int, input().split())
S = 3 * (s-1)
T = 3 * (t-1)

Frontier = [S]
Explored = []
while Frontier:
    v = Frontier.pop(0)
    l = L[v]
    Explored.append(v)
    for i in G[v]:
        if i == T:
            print((L[v] + 1) // 3)
            exit();
        if i not in Explored:
            Frontier.append(i)
            L[i] = l + 1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(3 * N)]
L = [0 for _ in range(3 * N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[3*u+0].append(3*v+1)
    G[3*u+1].append(3*v+2)
    G[3*u+2].append(3*v+0)
s, t = map(int, input().split())
S = 3 * (s-1)
T = 3 * (t-1)

Frontier = [S]
Explored = []
while Frontier:
    v = Frontier.pop(0)
    l = L[v]
    Explored.append(v)
    next = G[v]
    if T in next:
        print((L[v] + 1) // 3)
        exit();
    for i in next:
        if i not in Explored:
            Frontier.append(i)
            L[i] = l + 1

print(-1)

Submission status: Time Limit Exceeded

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

alist3 = [set([]) for _ in range(n)]
for v in range(n):
    for v1 in alist[v]:
        for v2 in alist[v1]:
            for v3 in alist[v2]:
                alist3[v].add(v3)

# BFS
queue = [s-1]
visited = [-1]*n
visited[s-1] = 0
while len(queue) > 0:
    q = queue.pop(0)
    for v in alist3[q]:
        if visited[v] < 0:
            queue.append(v)
            visited[v] = visited[q] + 1
print(visited[t-1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(3 * N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[3*u+0].append(3*v+1)
    G[3*u+1].append(3*v+2)
    G[3*u+2].append(3*v+0)
s, t = map(int, input().split())
S = 3 * (s-1)
T = 3 * (t-1)


class Node:
    def __init__(self, v, l):
        self.v = v
        self.l = l

Frontier = [Node(S, 0)]
Explored = []
while Frontier:
    node = Frontier.pop(0)
    v = node.v
    l = node.l
    Explored.append(v)
    next = G[v]
    if T in next:
        print((l + 1) // 3)
        exit();
    for i in next:
        if i not in Explored:
            Frontier.append(Node(i,l+1))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#TLE

from collections import deque

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

G = [ [] for row in range(N*3)]

for i in range(M):
    s,t = map(int,input().split())
    G[s-1].append(N+t-1)
    G[N+s-1].append(2*N+t-1)
    G[2*N+s-1].append(t-1)

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

S -= 1
T -= 1

path_G = [-1] * (N*3)

def breadth_first_search(S,T,G):
    deq = deque()
    searched = []
    deq.append(S)
    while len(deq) > 0:
        pos = deq.popleft()
        searched.append(pos)
        if pos == T:
            return True
        for next_pos in G[pos]:
            if (next_pos in searched) :
                continue
            if (next_pos in deq):
                continue
            deq.append(next_pos)
            path_G[next_pos] = pos
    return False

def calculate_path(path_G,S,T):
    distance = 0
    i = T
    while path_G[i] != S:
        distance +=1
        i = path_G[i]
    return distance + 1

if breadth_first_search(S,T,G):
    print(int(calculate_path(path_G,S,T) / 3))
else :
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#提出用

from collections import deque

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

G = [ [] for row in range(N*3)]

for i in range(M):
    s,t = map(int,input().split())
    G[s-1].append(N+t-1)
    G[N+s-1].append(2*N+t-1)
    G[2*N+s-1].append(t-1)

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

S -= 1
T -= 1

path_G = [-1] * (N*3)

def breadth_first_search(S,T,G):
    deq = deque()
    searched = []
    deq.append(S)
    while len(deq) > 0:
        pos = deq.popleft()
        searched.append(pos)
        if pos == T:
            return True
        for next_pos in G[pos]:
            if (next_pos in searched) :
                continue
            if (next_pos in deq):
                continue
            deq.append(next_pos)
            path_G[next_pos] = pos
    return False

def calculate_path(path_G,S,T):
    distance = 0
    i = T
    while path_G[i] != S:
        distance +=1
        i = path_G[i]
    return distance + 1

if breadth_first_search(S,T,G):
    print(int(calculate_path(path_G,S,T) / 3))
else :
    print(-1)

Submission status: Time Limit Exceeded

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

def dijkstra(n, edge, s, t):
    unserched = list(range(n))
    comp = [0] * n
    dist = [n] * n
    # prenode = [-1] * n
    
    dist[s] = 0
    endflag = False
    while(not endflag):
        # 未確定の点のうち距離が最小のものを求める
        min_dist = n
        min_dist_node = -1
        for node in unserched:
            if dist[node] < min_dist:
                min_dist = dist[node]
                min_dist_node = node
        if min_dist_node == -1:
            dist[t] = -1
            break
        if min_dist_node == t:
            endflag = True

        unserched.remove(min_dist_node)
         
        for e in edge[min_dist_node]:
            if comp[e] == 0: # and dist[e] > min_dist + 1:
                comp[e] = 1
                dist[e] = min_dist + 1
                # prenode[e] = min_dist_node
    # ptr = t
    # while ptr != s:
    #     print(ptr)
    #     ptr = prenode[ptr]
    # print(ptr)
    return dist[t]

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

edge = [[] for _ in range(n*3)]
for i in range(m):
    edge[u[i][0]-1].append(u[i][1]-1 + n)
    edge[u[i][0]-1 + n].append(u[i][1]-1 + 2*n)
    edge[u[i][0]-1 + 2*n].append(u[i][1]-1)

# for i in range(m):
#     print(u[i][0], u[i][1])

# for i, e in enumerate(edge):
#     for j in e:
#         print(i,j)
# print(edge)

print(dijkstra(n*3, edge, s-1, t-1)//3)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
L1 = [set() for k in range(3*(N+1))]
for k in range(M):
	u, v = map(int, input().split())
	L1[3*u].add(3*v+1)
	L1[3*u+1].add(3*v+2)
	L1[3*u+2].add(3*v)
S, T = map(int, input().split())
S = 3*S
T = set([3*T])

t = 0
sumi = set([S])
now = set([S])
flg = 0
while(len(now) != 0):
	t += 1
	pre = set()
	for n in now:
		pre = pre.union(L1[n])
	now = pre - sumi
	sumi = sumi.union(pre)
	if T <= pre:
		print(t//3)
		flg =1
		break
if flg == 0:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = next
    return start

stack = [s]
ifReached[s-1] = True
count = 0
unreachable = False
while True:
    n_stack = list(set(indicate3(stack,path)))
    tmp_stack = []
    for position in n_stack:
        if ifReached[position-1] == False:
            tmp_stack.append(position)
            ifReached[position-1] = True

    if len(tmp_stack) == 0:
        print(-1)
        break

    count += 1
    if g in n_stack:
        print(count)
        break
    stack = tmp_stack

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = next
    return start

stack = [s]
ifReached[s-1] = True
count = 0
unreachable = False
while True:
    n_stack = list(set(indicate3(stack,path)))
    tmp_stack = []
    for position in n_stack:
        if ifReached[position-1] == False:
            tmp_stack.append(position)
            ifReached[position-1] = True


    if len(tmp_stack) == 0:
        print(-1)
        break

    if g in n_stack:
        count += 1
        print(count)
        break
    else:
        if n_stack == stack:
            print(-1)
            break
        else:
            count += 1
            if unreachable == True:
                print(-1)
                break
    stack = tmp_stack

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = next
    return start

stack = [s]
count = 0
unreachable = False
while True:
    n_stack = list(set(indicate3(stack,path)))
    diffcount = 0
    for position in n_stack:
        if ifReached[position-1] == False:
            ifReached[position-1] = True
            diffcount += 1

    if diffcount == 0:
        print(-1)
        break

    if g in n_stack:
        count += 1
        print(count)
        break
    else:
        if n_stack == stack:
            print(-1)
            break
        else:
            count += 1
            if unreachable == True:
                print(-1)
                break
    stack = n_stack

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    global ifReached
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = next
    return start

stack = [s]
count = 0
unreachable = False
while True:
    n_stack = indicate3(stack,path)
    diffcount = 0
    for position in n_stack:
        if ifReached[position-1] == False:
            ifReached[position-1] = True
            diffcount += 1

    if diffcount == 0:
        print(-1)
        break
        
    if g in n_stack:
        count += 1
        print(count)
        break
    else:
        if n_stack == stack:
            print(-1)
            break
        else:
            count += 1
            if unreachable == True:
                print(-1)
                break
    stack = n_stack