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 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
S,T = IL()
S,T = S-1,T-1

graph2 = [set() for i in range(N)]
for x in range(N):
  for y in graph[x]:
    for z in graph[y]:
      graph2[x].add(z)
    
graph3 = [set() for i in range(N)]
for x in range(N):
  for y in graph2[x]:
    for z in graph[y]:
      graph3[x].add(z)

def bfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    for v in graph[u]:
      if d[v] != INF: continue
      d[v] = d[u] + 1
      q.append(v)
  return d

d = bfs(graph3,S)
if d[T] == INF:
  print(-1)
else:
  print(d[T])

Submission status: Time Limit Exceeded

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
S,T = IL()
S,T = S-1,T-1

graph2 = [[] for i in range(N)]
for x in range(N):
  for y in graph[x]:
    for z in graph[y]:
      graph2[x].append(z)
    
graph3 = [[] for i in range(N)]
for x in range(N):
  for y in graph2[x]:
    for z in graph[y]:
      graph3[x].append(z)

def bfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    for v in graph[u]:
      if d[v] != INF: continue
      d[v] = d[u] + 1
      q.append(v)
  return d

d = bfs(graph3,S)
if d[T] == INF:
  print(-1)
else:
  print(d[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M=map(int,input().split())
G=[[] for i in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
S,T=map(int,input().split())

def makeG2():
  G2=[[] for i in range(N+1)]
  for i in range(1,N+1):
    for j in G[i]:
      for k in G[j]:
        G2[i].extend(G[k])
  return G2

def bfs(s,t):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque()
    now = s
    seen[now]=1
    todo.append(now)
    while todo:
      a = todo.popleft()
      for b in G2[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
        if b == t:return d[t]
    return -1

G2=makeG2()
print(bfs(S,T))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M=map(int,input().split())
G=[[] for i in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
S,T=map(int,input().split())

def makeG2():
  G2=[[] for i in range(N+1)]
  for i in range(1,N+1):
    for j in G[i]:
      for k in G[j]:
        G2[i].extend(G[k])
  return G2

def bfs(s,t):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque()
    now = s
    seen[now]=1
    todo.append(now)
    while todo:
      a = todo.popleft()
      for b in G2[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
        if b == t:return d[t]
    return -1

G2=makeG2()
print(bfs(S,T))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M=map(int,input().split())
G=[[] for i in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
S,T=map(int,input().split())

G2=[[] for i in range(N+1)]
for i in range(1,N+1):
  for j in G[i]:
    for k in G[j]:
      G2[i].extend(G[k])

def bfs(s,t):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque()
    now = s
    seen[now]=1
    todo.append(now)
    while todo:
      a = todo.popleft()
      for b in G2[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
        if b == t:return d[t]
    return -1

print(bfs(S,T))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M=map(int,input().split())
G=[[] for i in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
S,T=map(int,input().split())


G2=[[] for i in range(N+1)]
for i in range(1,N+1):
  for j in G[i]:
    for k in G[j]:
      G2[i] = G2[i] + G[k]

def bfs(s,t):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque([])
    now = s
    seen[now]=1
    todo.append(now)
    while todo:
      a = todo.popleft()
      for b in G2[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
        if b == t:return d[t]
    return -1

print(bfs(S,T))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M=map(int,input().split())
G=[[] for i in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
S,T=map(int,input().split())

G2=[[] for i in range(N+1)]
for i in range(1,N+1):
  for j in G[i]:
    for k in G[j]:
      for l in G[k]:
        G2[i].append(l)

def bfs(s,t):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque([])
    now = s
    seen[now]=1
    todo.append(now)
    while todo:
      a = todo.popleft()
      for b in G2[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
        if b == t:return d[t]
    return -1

print(bfs(S,T))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
to = [[] for _ in range(N*3)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a*3].append(b*3+1)
  to[a*3+1].append(b*3+2)
  to[a*3+2].append(b*3)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Stack = [start*3]
visit = [INF for _ in range(N*3)]
visit[start*3] = 0
while Stack:
  v = Stack.pop()
  for w in to[v]:
    if visit[w] <= visit[v]+1:
      continue
    visit[w] = min(visit[w],visit[v]+1) 
    Stack.append(w) #step歩目でwにいて次vへ行く。

#print(visit)
if visit[end*3] == INF:
  ans = -1
else:
  ans = visit[end*3]//3
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
to = [[] for _ in range(N*3)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a*3].append(b*3+1)
  to[a*3+1].append(b*3+2)
  to[a*3+2].append(b*3)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Stack = [start*3]
visit = [INF for _ in range(N*3)]
visit[start*3] = 0
while Stack:
  v = Stack.pop()
  for w in to[v]:
    if visit[w] <= visit[v]:
      continue
    visit[w] = min(visit[w],visit[v]+1) 
    Stack.append(w) #step歩目でwにいて次vへ行く。

#print(visit)
if visit[end*3] == INF:
  ans = -1
else:
  ans = visit[end*3]//3
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
to = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a].append(b)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Stack = [(start,0)] #今の点、何歩目か
visit = [[INF,INF,INF] for _ in range(N)] #三歩目、一歩目、二歩目
visit[start][0] = 0
while Stack: #今の点、けんけんぱのどれか、一個前に止まった点
  v,step = Stack.pop()
  now = visit[v][step]
  step = (step+1)%3 #ここでstep+1歩目でvへ行く
  for w in to[v]:
    #print(visit[w][step],step,now)
    if visit[w][step] <= now:
      continue
    Stack.append((w,step)) #step歩目でwにいて次vへ行く。
    if step %3 == 0:
      visit[w][step] = min(visit[w][step],now+1)
    else:
      visit[w][step] = min(visit[w][step],now)
#print(visit)
if visit[end][0] == INF:
  ans = -1
else:
  ans = visit[end][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
to = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a].append(b)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Stack = [(start,0)] #今の点、何歩目か
visit = [[INF,INF,INF] for _ in range(N)] #三歩目、一歩目、二歩目
visit[start][0] = 0
while Stack: #今の点、けんけんぱのどれか、一個前に止まった点
  v,step = Stack.pop()
  now = visit[v][step]
  step = (step+1)%3 #ここでstep+1歩目でvへ行く
  for w in to[v]:
    if visit[w][step] <= now:
      continue
    Stack.append((w,step)) #step歩目でwにいて次vへ行く。
    if step %3 == 0:
      visit[w][step] = min(visit[w][step],now+1)
    else:
      visit[w][step] = min(visit[w][step],now)
#print(visit)
if visit[end][0] == INF:
  ans = -1
else:
  ans = visit[end][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
INFTY = 10**6
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())
Q = deque([S])
F = {}
hist = [0 for _ in range(N+1)]
while Q:
    z = Q.popleft()
    if hist[z]==1:continue
    hist[z]=1
    F[z] = []
    que = deque([(z,0)])
    while que:
        x,d = que.popleft()
        if d==3:
            F[z].append(x)
        else:
            for y in G[x]:
                que.append((y,d+1))
    for x in F[z]:
        Q.append(x)
dist = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
heap = [(0,S)]
dist[S] = 0
while heap:
    d,x = heapq.heappop(heap)
    if dist[x]<d:continue
    hist[x] = 1
    for y in F[x]:
        if hist[y]==0:
            if dist[y]>d+1:
                dist[y]=d+1
                heapq.heappush(heap,(d+1,y))
if dist[T]<INFTY:
    print(dist[T])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
E = defaultdict(list)
for i in range(M):
	u, v = rl()
	E[u-1].append(v-1)
	#E[v-1].append(u-1)
S, T = rl()
S -= 1
T -= 1

dp = [[float('inf')]*3 for i in range(N)]

def dfs(n, d):
	for m in E[n]:
		r = (d+1)%3
		if dp[m][r] > d+1:
			dp[m][r] = d+1
			dfs(m, d+1)

dfs(S, 0)
if dp[T][0] != float('inf'):
	print(dp[T][0]//3)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  g[a].append(b)
s,t=map(int,input().split())
s,t=s-1,t-1
gg=[set(()) for _ in range(n)]
for i in range(n):
  for j in g[i]:
    for k in g[j]:
      for l in g[k]:
        if l!=i:
          gg[i].add(l)
from collections import deque
todo=deque([s])
seen=[-1]*n
seen[s]=0
while todo:
  v=todo.popleft()
  for l in gg[v]:
    if seen[l]==-1:
      todo.append(l)
      seen[l]=seen[v]+1
print(seen[t])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, p):
        for u in edge_extend[p][v]:
            next_p = 0 if p == 2 else p + 1
            if dist[next_p][u] <= dist[p][v] + 1:
                continue
            else:
                dist[next_p][u] = dist[p][v] + 1
                dfs(u, next_p)

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

    edge_extend = []
    for _ in range(3):
        edge_extend.append(edge)

    dist = [[f_inf] * n for _ in range(3)]
    dist[0][s - 1] = 0
    dfs(s - 1, 0)
    print(dist[0][t - 1] // 3 if dist[0][t - 1] != f_inf else -1)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    

    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in set(roots[now]):
                    purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    purposes.add(root)
            next_targets = deque(purposes)
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
            if next_target == T:
                print(costs[next_target])
                sys.exit()
    print(-1)
if __name__ == "__main__":
    func()

Submission status: Time Limit Exceeded

Solution code:

import sys

N, M = map(int, input().split())
uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, input().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0
todo_set = set([S])

while len(todo)>0:
    checking = todo.popleft()
    next_targets = deque([checking])
    for i in range(3):
        purposes = set()
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.add(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] < 0 and next_target not in todo_set:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
            todo_set.add(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:

import sys

N, M = map(int, input().split())
uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, input().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

count = 0
while len(todo)>0:
    count+=1
    if count > M :
        break
    checking = todo.popleft()
    next_targets = deque([checking])
    for i in range(3):
        purposes = set()
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.add(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] < 0:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())
uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, input().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

while len(todo)>0:
    checking = todo.popleft()
    next_targets = deque([checking])
    for i in range(3):
        purposes = set()
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.add(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] < 0:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:

import sys

N, M = map(int, input().split())
uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, input().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

while len(todo)>0:
    checking = todo.popleft()
    next_targets = deque([checking])
    for i in range(3):
        purposes = set()
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.add(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] < 0:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:


import sys


N, M = map(int, input().split())
uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, input().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

while len(todo)>0:
    checking = todo.popleft()
    next_targets = deque([checking])
    for i in range(3):
        purposes = []
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.append(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] == -10000:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:

import sys

N, M = map(int, input().split())
uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, input().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

while len(todo)>0:
    checking = todo.popleft()
    next_targets = deque([checking])
    for i in range(3):
        purposes = []
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.append(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] == -10000:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    edges[u-1].append(v-1)

S, T = map(int, sys.stdin.readline().split())
S -= 1
T -= 1

visited = {}
q = deque()
q.append((S, 0))
d = -1
while q:
    s, c = q.popleft()
    if s in visited and visited[s] % 3 == c % 3:
        continue
    visited[s] = c
    for n in edges[s]:
        if n == T and c % 3 == 2:
            d = c + 1
            break
        q.append((n, c+1))

    if d % 3 == 0:
        break

if d == -1:
    print(-1)
else:
    print(d // 3)