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: Runtime Error

Solution code:

import numpy as np
MAX_VAL=1000000007
n,m=map(int,input().split())
uv=[tuple(map(int,input().split())) for _ in range(m)]
s,t=map(int,input().split())
s,t=s-1,t-1

move=np.zeros((n,n))
for ui,vi in uv:
    ui,vi=ui-1,vi-1
    move[ui][vi]=1
# print(move)
kenkenpa=np.dot(np.dot(move,move),move)

visited=[False for _ in range(n)]
cost=[MAX_VAL for _ in range(n)]
cost[s]=0
# prev=[-1 for _ in range(n)]
# prev[s]=s
now=s
while True:
    min=MAX_VAL
    next=-1
    visited[now]=True
    for i in range(n):
        if not visited[i]:
            if kenkenpa[now][i]==1:
                tmpCost=cost[now]+1
                if cost[i]>tmpCost:
                    cost[i]=tmpCost
                    # prev[i]=now
                if min>cost[i]:
                    min=cost[i]
                    next=i
    if next==-1:
        break
    elif next==t:
         break
    now=next
# print(cost)
# print(prev)
if cost[t]==MAX_VAL:
    print(-1)
else:
    print(cost[t])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    # power_funcを用いて(nCk) mod p を求める 
    # nCk = n!/((n-k)!k!)を使用

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    # a^b mod p を求める
    # bを2進数分解して高速累乗

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

#D
def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge):

    dist = [inf for i in range(num)]
    dist[start] = 0
    q = [(dist[start], start)]
    while q:
        du, u = heappop(q)
        for j in edge[u]:
            if dist[j] > du + 1:
                dist[j] = du + 1
                heappush(q, [dist[j], j])
    return dist
#E
def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = defaultdict(list)
    for x,y in v:
        edge[x].append((y))
    newedge = defaultdict(list)
    for key, value in edge.items():
        b = []
        for j in value:
            for k in edge[j]:
                for l in edge[k]:
                    if l == key:
                        continue
                    b.append(l)
        newedge[key] = b
    d = dijkstra(n, s, newedge)
    if d[t] == inf:
        print(-1)
    else:
        print(d[t])
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Runtime Error

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

n, m = map(int, input().split())

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

INF = float('inf')
memo = [[INF for _ in range(n)] for i in range(3)]

def dfs(v, mod, dist):
    if dist < memo[mod][v]:
        memo[mod][v] = dist
        for nv in g[v]:
            if dist >= memo[(mod+1)%3][nv]:
                continue
            dfs(nv, (mod+1)%3, dist+1)


dfs(s, 0, 0)
if memo[0][t] == INF:
    print(-1)
else:
    print(memo[0][t]//3)

Submission status: Runtime Error

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

adjucent_dict={u:set() for u in range(1,N+1)}
for u,v in UV:
  adjucent_dict.setdefault(u,set()).add(v)
  #adjucent_dict.setdefault(v,set()).add(u)
  
two_adjucent_dict={u:set.union(*[adjucent_dict[v] for v in adjucent_dict[u]]) for u in range(1,N+1) if u in adjucent_dict}
three_adjucent_dict={u:set.union(*[adjucent_dict[v] for v in two_adjucent_dict[u]]) for u in range(1,N+1) if u in two_adjucent_dict}

visited=set([S])
just_visited=set([S])
n=1
while True:
  three_step = set.union(*[three_adjucent_dict[u] for u in just_visited if u in three_adjucent_dict])
  just_visited = three_step - visited
  if T in just_visited:
    print(n)
    break
  if len(just_visited)==0:
    print(-1)
    break
    
  visited = visited & just_visited
  n+=1

Submission status: Runtime Error

Solution code:
import numpy as np
n,m=map(int,input().split())
G = np.zeros((n,n))
for _ in range(m):
    u,v=map(int,input().split())
    G[u-1,v-1]=1
G3 = np.dot(np.dot(G,G),G)

Gn = G3
s,t=map(int,input().split())
check = 0
for i in range(1,n):
    if Gn[s-1,t-1] > 0:
        print(i)
        break
    elif i==n-1:
        print(-1)
        break
    else:
        Gn=np.dot(Gn,G3)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
N,M = map(int,input().split(' '))
#G = {i:[] for i in range(1,N+1)}

GM = np.zeros((N,N)).astype(np.int)

for j in [0]*M:
	u,v = map(int,input().split(' '))
	GM[u-1,v-1] = 1
	#G[u].append(v)
S,T = map(int,input().split(' '))

GM = np.dot(np.dot(GM,GM),GM)

G3 = {i: list(np.where(GM[i-1]==1)[0]+1) for i in range(1,N+1)}

#dq =deque([S])
st = [S]
visited = [S]
ans = 1
exist = True
while(exist):
	new_st = []
	exist = False
	for cand in st:
		for n in G3[cand]:
			if n == T:
				print(ans)
				exit()
			if not n in visited:
				exist = True
				visited.append(n)
				new_st.append(n)
	st = new_st
	ans += 1
print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys

# main
N, M = [int(i) for i in input().split(' ')]
matrix = np.matrix([ [0 for i in range(N)] for i in range(N) ])

for i in range(M):
    (u, v) = [int(i) for i in input().split(' ')]
    matrix[u - 1, v - 1] = 1

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

start = np.matrix([1 if i == S - 1 else 0 for i in range(N)])

def matrix_eval_three_steps(matrix, vector):
    return vector @ matrix @ matrix @ matrix 

for i in range(N):
    start = matrix_eval_three_steps(matrix, start)
    if start[0, T - 1] > 0:
        print(i + 1)
        sys.exit()

print(-1)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from collections import deque
fastinput = sys.stdin.readline
N,M = [int(i) for i in fastinput().split()]
rinsetsu = np.zeros((N,N),dtype = "bool")
for i in range(M):
    u,v =  [int(i) for i in fastinput().split()]
    rinsetsu[u-1][v-1] = True
kenken = np.dot(rinsetsu,rinsetsu)
kenpa = np.dot(kenken,rinsetsu)
S,T = map(int,input().split())
S-=1
T-=1

rinlist = [[] for i in range(N)]
for s,row in enumerate(kenpa):
    for t,i in enumerate(row):
        if i:rinlist[s].append(t)
queue = deque()
went = [False]*N
turn = [0]*N
went[S] = True
queue.append((S,0))
while queue:
    cur,curturn = queue.popleft()
    for togo in rinlist[cur]:
        if not went[togo]:
            went[togo] = True
            turn[togo] = curturn + 1
            queue.append((togo,curturn+1))
if not went[T]:
    print(-1)
else:
    print(turn[T])

Submission status: Runtime Error

Solution code:
import numpy as np
MAX_VAL=1000000007
n,m=map(int,input().split())
uv=[tuple(map(int,input().split())) for _ in range(m)]
s,t=map(int,input().split())
s,t=s-1,t-1

move=np.zeros((n,n))
for ui,vi in uv:
    ui,vi=ui-1,vi-1
    move[ui][vi]=1
# print(move)
kenkenpa=np.dot(np.dot(move,move),move)

visited=[False for _ in range(n)]
cost=[MAX_VAL for _ in range(n)]
cost[s]=0
# prev=[None for _ in range(n)]
# prev[s]=s
now=s
while True:
    min=MAX_VAL
    next=-1
    visited[now]=True
    for i in range(n):
        if not visited[i]:
            if kenkenpa[now][i]==1:
                tmpCost=cost[now]+1
                if cost[i]>tmpCost:
                    cost[i]=tmpCost
                    # prev[i]=now
            if min>cost[i]:
                min=cost[i]
                next=i
    if next==-1:
        break
    now=next
# print(cost)
# print(prev)
if cost[t]==MAX_VAL:
    print(-1)
else:
    print(cost[t])

Submission status: Runtime Error

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

adjucent_dict={u:set() for u in range(1,N+1)}
for u,v in UV:
  adjucent_dict.setdefault(u,set()).add(v)
  #adjucent_dict.setdefault(v,set()).add(u)
  
visited=set([S])
just_visited=set([S])
n=1
while True:
  one_step=set.union(*[adjucent_dict[u] for u in just_visited])
  two_step=set.union(*[adjucent_dict[u] for u in one_step])
  three_step = set.union(*[adjucent_dict[u] for u in two_step])
  just_visited = three_step - visited
  if T in just_visited:
    print(n)
    break
  if len(just_visited)==0:
    print(-1)
    break
    
  visited = visited & just_visited
  n+=1

Submission status: Runtime Error

Solution code:
import numpy as np
n,m=map(int,input().split())
uv=[tuple(map(int,input().split())) for _ in range(m)]
s,t=map(int,input().split())
s,t=s-1,t-1

move=np.zeros((n,n))
for ui,vi in uv:
    ui,vi=ui-1,vi-1
    move[ui][vi]=1
# print(move)
kenkenpa=np.dot(np.dot(move,move),move)

visited=[False for _ in range(n)]
cost=[1000000007 for _ in range(n)]
prev=[None for _ in range(n)]
cost[s]=0
prev[s]=s
now=s
while True:
    min=1000000007
    next=-1
    visited[now]=True
    for i in range(n):
        if not visited[i]:
            if kenkenpa[now][i]==1:
                tmpCost=cost[now]+1
                if cost[i]>tmpCost:
                    cost[i]=tmpCost
                    prev[i]=now
            if min>cost[i]:
                min=cost[i]
                next=i
    if next==-1:
        break
    now=next
print(cost)
print(prev)
if prev[t]==None:
    print(-1)
else:
    print(cost[t])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
INF = float("inf")


def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    A = np.zeros((N, N))
    for from_, to_ in zip(u, v):
        A[to_-1][from_-1] = 1
    A3 = np.asarray(np.dot(np.dot(A, A), A) > 0,
                    dtype=int)                   # けんけんぱでの遷移
    x = np.zeros(N)
    x[S-1] = 1
    for i in range(3*M):
        x = np.dot(A3, x)
        if x[T-1] > 0:
            print(i+1)
            return
    print(-1)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]"
    v = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, u, v, S, T)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
INF = float("inf")


def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    A = np.zeros((N, N))
    for from_, to_ in zip(u, v):
        A[to_-1][from_-1] = 1
    A3 = np.asarray(np.dot(np.dot(A, A), A) > 0,
                    dtype=int)                   # けんけんぱでの遷移
    x = np.zeros(N)
    x[S-1] = 1
    for i in range(3*M):
        x = A3@x
        if x[T-1] > 0:
            print(i+1)
            return
    print(-1)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]"
    v = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, u, v, S, T)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
INF = float("inf")


def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    A = np.zeros((N, N))
    for from_, to_ in zip(u, v):
        A[to_-1][from_-1] = 1
    A3 = np.asarray(A@A@A > 0, dtype=int)                   # けんけんぱでの遷移
    x = np.zeros(N)
    x[S-1] = 1
    for i in range(3*M):
        x = A3@x
        if x[T-1] > 0:
            print(i+1)
            return
    print(-1)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]"
    v = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, u, v, S, T)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
g = []
for i in range(n):
    g.append([])
for i in range(m):
    u, v = na()
    g[u-1].append(v-1)

s, t = na()
s -= 1;
t -= 1

ds = [[9999999999] * n for i in range(3)]
ds[0][s] = 0

q = Queue()
q.put((0, s))
while not q.empty():
    r, cur = q.get_nowait()
    nr = (r+1) % 3
    for e in g[cur]:
        # print(nr, e)
        if ds[nr][e] > ds[r][cur] + 1:
            ds[nr][e] = ds[r][cur] + 1
            q.put((nr, e))
if ds[0][t] >= 0:
    print(ds[0][t]//3)
else:
    print(-1)