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: Wrong Answer

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

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

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

s, t = [int(x) for x in input().strip().split(" ")]
print(dfs_w(s, d, t))

Submission status: Wrong Answer

Solution code:

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

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

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

s, t = [int(x) for x in input().strip().split(" ")]
print(dfs_w(s, d, t))

Submission status: Wrong Answer

Solution code:

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

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

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

s, t = [int(x) for x in input().strip().split(" ")]
print(dfs_w(s, d, t))

Submission status: Wrong Answer

Solution code:

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

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

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

s, t = [int(x) for x in input().strip().split(" ")]
print(dfs_w(s, d, t))

Submission status: Wrong Answer

Solution code:
import queue

n,m = map(int,input().split())
lis = [[]for _ in range(3*n)]
for _ in range(m):
  u,v = map(int,input().split())
  lis[3*(u-1)].append(3*(v-1)+1)
  lis[3*(u-1)+1].append(3*(v-1)+2)
  lis[3*(u-1)+2].append(3*(v-1))

s,t = map(int,input().split())
s,t = 3*(s-1),3*(t-1)
path = [0]+[-1]*(3*n-1)
q = queue.Queue()
q.put(s)
while not q.empty() and -1 in path:
  a = q.get()
  for p in lis[a]:
    if path[p] == -1:
      path[p] = path[a]+1
      q.put(p)
print(path[t]//3 if path[t] != -1 else -1)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    a,e=map(int,input().split())
    graph[a-1].append(e+n-1)
    graph[a+n-1].append(e+2*n-1)
    graph[a+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
visited=[False]*(3*n)
leng=[0]*(3*n)
def dfs(checking,length=0):
    visited[checking]=True
    leng[checking]=length
    if checking==t:return 
    for next in graph[checking]:
        if visited[next]:continue
        dfs(next,length+1)
dfs(s,0)
print(-1 if visited[t]==False else leng[t]//3)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
INF = float("inf")
step = [[INF]*3 for _ in range(N)]
step[S-1][0] = 0
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if step[nxt][(d+1)%3] < 0:
			step[nxt][(d+1)%3] = d+1
			q.append((nxt,d+1))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
INF = float("inf")
step = [[INF]*3 for _ in range(N)]
step[S][0] = 0
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if step[nxt][(d+1)%3] > d+1:
			step[nxt][(d+1)%3] = d+1
			q.append((nxt,d+1))
ans = step[T-1][0]
print(-1 if ans==INF else ans//3)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
step = [[float("inf")]*3 for _ in range(N)]
step[S][0] = 0
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if step[nxt][(d+1)%3] > d+1:
			step[nxt][(d+1)%3] = d+1
			q.append((nxt,d+1))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
step = [[-1]*3 for _ in range(N)]
step[S][0] = 0
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if step[nxt][(d+1)%3] < 0:
			step[nxt][(d+1)%3] = d+1
			q.append((nxt,d+1))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
step = [[-1]*3 for _ in range(N)]
step[S][0] = 0
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if step[nxt][(d+1)%3] < 0:
			step[nxt][(d+1)%3] = d
			q.append((nxt,d+1))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    s,e=map(int,input().split())
    graph[s-1].append(e+n-1)
    graph[s+n-1].append(e+2*n-1)
    graph[s+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
stack=deque([s])
length=0;flag=0
visited=[False]*(3*n)
while stack!=deque([]):
    inv=stack.popleft()
    visited[inv]=True
    for i in graph[inv]:
        if visited[i]==True:continue
        stack.append(i)
    length+=1
    if inv == t:
        flag=1
        break
if flag==0:print(-1)
else:print(length//3)

Submission status: Wrong Answer

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


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


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


s, t = LI()


kenken_graph = [[] for _ in range(n)]
for i in range(n):
    dist = [0] * n
    que = deque([(i, 0)])
    while que:
        cur, cost = que.pop()
        for nxt in graph[cur]:
            if dist[nxt] & 1 << cost:
                continue
            dist[nxt] += 1 << cost
            if cost == 2:
                kenken_graph[i] += [nxt]
            else:
                que += [(nxt, cost + 1)]


ken_que = deque([s - 1])
ken_dist = [-1] * n
ken_dist[s - 1] = 0
while ken_que:
    cur = ken_que.pop()
    for nxt in kenken_graph[cur]:
        if ken_dist[nxt] != -1:
            continue
        ken_dist[nxt] = ken_dist[cur] + 1
        ken_que += [nxt]



print(ken_dist[t - 1])

Submission status: Wrong Answer

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

N,M = map(int,input().split())
INF = 10 ** 8

info = [[] for __ in range(3*N)]
for _ in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    info[3*u].append(3*v+1)
    info[3*u+1].append(3*v+2)
    info[3*u+2].append(3*v)
#print(info)

S,T = map(int,input().split())
S = (S - 1) * 3
T = (T - 1) * 3

stack = [[0,S]]
visited = [0] * (3 * N)
visited[S] = 1
m = INF
det = -1


while stack:
    x = stack.pop(-1)
    for z in info[x[1]]:
        if z == T:
            m = min(m,x[0]+1)
            det = 0
            continue
        if visited[z] == 1:continue
        stack.append([x[0]+1,z])
        visited[z] = 1
    #print(stack,visited)

if det == 0:
    print(m//3)
else:
    print(-1)

Submission status: Wrong Answer

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

N,M = map(int,input().split())
INF = 10 ** 8

info = [[] for __ in range(3*N)]
for _ in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    info[3*u].append(3*v+1)
    info[3*u+1].append(3*v+2)
    info[3*u+2].append(3*v)
#print(info)

S,T = map(int,input().split())
S = (S - 1) * 3
T = (T - 1) * 3

stack = [[0,S]]
visited = [0] * (3 * N)
m = INF
det = -1

while stack:
    x = stack.pop(-1)
    for z in info[x[1]]:
        if z == T:
            m = min(m,x[0]+1)
            det = 0
            continue
        if visited[z] == 1:continue
        stack.append([x[0]+1,z])
        visited[z] = 1
    #print(stack,visited)

if det == 0:
    print(m//3)
else:
    print(-1)

Submission status: Wrong Answer

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

N,M = map(int,input().split())
INF = 10 ** 8

info = [[] for __ in range(3*N)]
for _ in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    info[3*u].append(3*v+1)
    info[3*u+1].append(3*v+2)
    info[3*u+2].append(3*v)
#print(info)

S,T = map(int,input().split())
S = (S - 1) * 3
T = (T - 1) * 3

stack = [[0,S]]
visited = [0] * (3 * N)
m = INF
det = -1

while stack:
    x = stack.pop(-1)
    for z in info[x[1]]:
        if z == T:
            m = min(m,x[0]+1)
            det = 0
            continue
        if visited[z] == 1:continue
        stack.append([x[0]+1,z])
        visited[z] = 1
    #print(stack,visited)

if det == 0:
    print(m//3)
else:
    print(-1)

Submission status: Wrong Answer

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

N,M = map(int,input().split())
INF = 10 ** 6

info = [[] for __ in range(3*N)]
for _ in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    info[3*u].append(3*v+1)
    info[3*u+1].append(3*v+2)
    info[3*u+2].append(3*v)
#print(info)

S,T = map(int,input().split())
S = (S - 1) * 3
T = (T - 1) * 3

stack = [[0,S]]
visited = [0] * (3 * N)
m = INF
det = -1

while stack:
    x = stack.pop(-1)
    for z in info[x[1]]:
        if z == T:
            m = min(m,x[0]+1)
            det = 0
            continue
        if visited[z] == 1:continue
        stack.append([x[0]+1,z])
        visited[z] = 1
    #print(stack,visited)

if det == 0:
    print(m//3)
else:
    print(-1)

Submission status: Wrong Answer

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

N,M = map(int,input().split())
INF = 10 ** 6

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

stack = []
visited = [0] * N
visited[S] = 1
for y in info[S]:
    stack.append([1,y])#[到達までの回数,頂点番号]

m = INF
det = -1
while stack:
    x = stack.pop(-1)
    for z in info[x[1]]:
        if z == T and x[0] % 3 == 2:
            m = min(m,(x[0]+1)//3)
            det = 0
            continue
        if visited[z] == 1 and x[0] % 3 == 2:continue
        if x[0] % 3 == 2:
            visited[z] = 1
        stack.append([x[0] + 1,z])

if det == -1:
    print(-1)
else:
    print(m)

Submission status: Wrong Answer

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

N,M = map(int,input().split())
INF = 10 ** 6

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

stack = []
visited = [0] * N
visited[S] = 1
for y in info[S]:
    stack.append([1,y])#[到達までの回数,頂点番号]

m = INF
det = -1
while stack:
    x = stack.pop(-1)
    for z in info[x[1]]:
        if z == T and x[0] % 3 == 2:
            m = min(m,(x[0]+1)//3)
            det = 0
        if visited[z] == 1 and x[0] % 3 == 2:continue
        if x[0] % 3 == 2:
            visited[z] = 1
        stack.append([x[0] + 1,z])

if det == -1:
    print(-1)
else:
    print(m)

Submission status: Wrong Answer

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

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

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

stack = []
visited = [0] * N
visited[S] = 1
for y in info[S]:
    stack.append([1,y])#[到達までの回数,頂点番号]

while stack:
    x = stack.pop(-1)
    for z in info[x[1]]:
        if z == T and x[0] % 3 == 2:
            print((x[0]+1)//3)
            sys.exit()
        if visited[z] == 1 and x[0] % 3 == 2:continue
        if x[0] % 3 == 2:
            visited[z] = 1
        stack.append([x[0] + 1,z])

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    s,e=map(int,input().split())
    graph[s-1].append(e+n-1)
    graph[s+n-1].append(e+2*n-1)
    graph[s+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
stack=deque([s])
length=1;flag=0
visited=[False]*(3*n)
while stack!=deque([]):
    inv=stack.pop()
    visited[inv]=True
    for i in graph[inv]:
        if visited[i]==True:continue
        stack.append(i)
    length+=1
    if inv == t:
        flag=1
        break
if flag==0:print(-1)
else:print(length//3)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    s,e=map(int,input().split())
    graph[s-1].append(e+n-1)
    graph[s+n-1].append(e+2*n-1)
    graph[s+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
stack=deque([s])
length=0;flag=0
visited=[False]*(3*n)
while stack!=deque([]):
    inv=stack.pop()
    visited[inv]=True
    for i in graph[inv]:
        if visited[i]==True:continue
        stack.append(i)
    length+=1
    if inv == t:
        flag=1
        break
if flag==0:print(-1)
else:print(length//3)

Submission status: Wrong Answer

Solution code:
import queue
from collections import defaultdict


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

graph_dic = defaultdict(list)
# visit_dic = defaultdict(list)

for u, v in G:
    graph_dic[u].append(v)

q = queue.Queue()
q.put([S, 1])
visited = False

while not q.empty():
    n, step = q.get()

    if step % 3 == 0 and n == T:
        print(step // 3 + 1)
        exit()

    if n == T and visited and (step - visit_step) % 3 == 0:
        print(-1)
        exit()

    target = graph_dic[n]

    for i in target:
        q.put([i, step + 1])

    if n == T:
        visited = True
        visit_step = step


print(-1)

Submission status: Wrong Answer

Solution code:
import queue
from collections import defaultdict


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

graph_dic = defaultdict(list)
visit_dic = defaultdict(list)

for u, v in G:
    graph_dic[u].append(v)

q = queue.Queue()
q.put([S, 0])

while not q.empty():
    n, step = q.get()

    if step % 3 == 0 and n in visit_dic:
        print(-1)
        exit()

    if step % 3 == 0 and n == T:
        print(step // 3)
        exit()

    target = graph_dic[n]

    for i in target:
        q.put([i, step + 1])

    visit_dic[n] = step


print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import queue

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

s, t = map(int, input().split())

graph = defaultdict(list)

for edge in edges:
	u, v = edge
	graph[u].append(v + n)
	graph[u + n].append(v + 2*n)
	graph[u + 2*n].append(v)

def bfs(s, t, graph):
	vis_set = set()
	dist = defaultdict(lambda: int(-1))
	dist[s] = 0
	que = queue.Queue()
	que.put(s)
	vis_set.add(s)	

	while not que.empty():
		vert = que.get()
		for nxt in graph[vert]:
			if nxt not in vis_set:
				dist[nxt] = dist[vert] + 1
				vis_set.add(nxt)
				que.put(nxt)
				if nxt == t:
					return dist[nxt]
	return -1
ans = bfs(s, t, graph)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
def dijkstra_heap(s,n,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,m = map(int,input().split())
if m == 0:
  print(-1)
  exit()
xy = [list(map(int,input().split())) for _ in range(m)]
s,t = list(map(int,input().split()))

xy=[[item[0]-1,item[1]-1] for item in xy]


# 状態数3倍化
xy_3bai=[[] for item in range(n*3)]
for i in range(m):
    #print(i,3*xy[i][1])
    xy_3bai[3*xy[i][0]].append([1,3*xy[i][1]+1])
    #xy_3bai[3*xy[i][1]].append([1,3*xy[i][0]+1]) 
    
    xy_3bai[3*xy[i][0]+1].append([1,3*xy[i][1]+2])
    #xy_3bai[3*xy[i][1]+1].append([1,3*xy[i][0]+2])
    
    xy_3bai[3*xy[i][0]+2].append([1,3*xy[i][1]])
    #xy_3bai[3*xy[i][1]+2].append([1,3*xy[i][0]])

anslist=dijkstra_heap(s-1,n*3,xy_3bai)[3*(t-1):3*(t-1)+3]
#print(anslist)

print(min(anslist))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
def dijkstra_heap(s,n,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,m = map(int,input().split())
if m == 0:
  print(-1)
  exit()
xy = [list(map(int,input().split())) for _ in range(m)]
s,t = list(map(int,input().split()))

xy=[[item[0]-1,item[1]-1] for item in xy]


# 状態数3倍化
xy_3bai=[[] for item in range(n*3)]
for i in range(m):
    #print(i,3*xy[i][1])
    xy_3bai[3*xy[i][0]].append([1,3*xy[i][1]+1])
    #xy_3bai[3*xy[i][1]].append([1,3*xy[i][0]+1]) 
    
    xy_3bai[3*xy[i][0]+1].append([1,3*xy[i][1]+2])
    #xy_3bai[3*xy[i][1]+1].append([1,3*xy[i][0]+2])
    
    xy_3bai[3*xy[i][0]+2].append([1,3*xy[i][1]])
    #xy_3bai[3*xy[i][1]+2].append([1,3*xy[i][0]])

anslist=dijkstra_heap(s-1,n*3,xy_3bai)[3*(t-1):3*(t-1)+3]
#print(anslist)
if float("inf") in anslist:
  print(-1)
else:
  print(min(anslist))

Submission status: Wrong Answer

Solution code:
#52 ABC132E
class Dijkstra():
    class Edge():
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数
    @property
    def E(self):
        return self._E
    @property
    def V(self):
        return self._V
    def add(self, _from, _to, _cost):
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
    def shortest_path(self, s):
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する
        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue
            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

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

djk=Dijkstra(3*n+1)
for u,v in uv:
	djk.add(u,v+n,1)
	djk.add(u+n,v+n*2,1)
	djk.add(u+n*2,v,1)
d = djk.shortest_path(s)
print(d[2*n+t] if d[2*n+t]!=float("inf") else -1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
E = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    E[u].append(v+N)
    E[u+N].append(v+2*N)
    E[u+2*N].append(v)
S, T = map(int, input().split())
R = [-1 for _ in range(3*N)]
R[S-1] = 0

q = deque()
q.append(S)
while q:
    n = q.pop()
    if n == T:
        break
    for t in E[n]:
        if R[t-1] < 0:
            R[t-1] = R[n-1] + 1
            q.append(t)
print(-1 if R[T-1] < 0 else R[T-1] // 3)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
import sys

sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
E = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    E[u].append(v+N)
    E[u+N].append(v+2*N)
    E[u+2*N].append(v)
S, T = map(int, input().split())
visited = [False]*(3*N)

q = deque()
q.append((S, 0))
while q:
    n, r = q.pop()
    if n == T:
        print(r // 3)
        exit()
    if not visited[n-1]:
        visited[n-1] = True
        for t in E[n]:
            q.append((t, r+1))
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

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

def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for u, v in UV:
    graph[u][v] = 1
for i in range(N+1):
    graph[i][i] = 0
    
shortest = warshall_floyd(graph, N+1)
#print(shortest)

ans = float("inf")
for i, v_i in enumerate(shortest[S]):
    v_j = shortest[i][T]
    path_len = v_i + v_j
    if path_len % 3 == 0:
        ans = min(ans, path_len // 3)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

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

def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for u, v in UV:
    graph[u][v] = 1
for i in range(N+1):
    graph[i][i] = 0
    
shortest = warshall_floyd(graph, N+1)
#print(shortest)

ans = float("inf")
for i, v_i in enumerate(shortest[S]):
    v_j = shortest[i][T]
    path_len = v_i + v_j
    if path_len % 3 == 0:
        ans = min(ans, path_len // 3)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for i in range(3 * N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = 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, T = S - 1, T - 1
INF = float('inf')
d = [INF] * (3 * N)
d[3 * S] = 0


que = deque([(3 * S, 0)])
while que:
    u, k = que.popleft()
    d[u] = k
    for w in G[u]:
        if d[w] == INF:
            que.append((w, k + 1))


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

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for i in range(3 * N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = 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, T = S - 1, T - 1
INF = float('inf')
d = [INF] * (3 * N)
d[3 * S] = 0


que = deque([(3 * S, 0)])
while que:
    u, k = que.pop()
    d[u] = k
    for w in G[u]:
        if d[w] == INF:
            que.append((w, k + 1))


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