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=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

stack=[]
seen=[[False for i in range(3)] for j in range(N)]
stack.append([S,0,1])
while stack:
  node=stack.pop()
  v=node[0]
  step=node[1]
  turn=node[2]
  print(v,step,turn)
  if step==3:
    if v==T:
      print(turn)
      break
    step=0
    turn+=1
  if seen[v][step]:
    continue
  seen[v][step]=True
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  print(-1)

Submission status: Wrong Answer

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

def bfs(graph,N,s,t):
    S=[s]
    visited=set()
    distance={(i+1,j):0 for i in range(N) for j in range(3)}
    while len(S)>0:
        v=S.pop(0)
        if v==t:
            return True,distance[v]+1
        if v not in visited:
            visited.add(v)
            for w in graph[v]:
                distance[w] = distance[v]+1
                S.append(w)
    return False,-1
if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    print(N,M)
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))
    flag,ans=bfs(graph,N,(S,0),(T,0))

    if flag:
        print(ans//3)
    else:
        print(-1)

Submission status: Wrong Answer

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

def dfs(graph,s,t):
    S=[s]
    visited=set()
    count=0
    while len(S)>0:
        v=S.pop()
        if v==t:
            return True,count
        if v not in visited:
            count+=1
            visited.add(v)
            for w in graph[v]:
                S.append(w)
    return False,-1


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    ans=-1
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))

    flag,ans=dfs(graph,(S,0),(T,0))
    if flag:
        print(ans//3)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

# 最短経路に閉路がくっついているとは限らなかった・・・

read = sys.stdin.read
N, M, *uv, S, T = map(int, read().split())

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 15
# [けん,けんけん,けんけんぱ] * (N + 1)
dist = [[INF] * (N + 1) for _ in range(3)]
stack = deque([(0, 1)])

while stack:
    cost, v = stack.popleft()
    if dist[cost % 3][v] != INF:
        continue

    dist[cost % 3][v] = cost
    for i in graph[v]:
        stack.append((cost + 1, i))

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

Submission status: Wrong Answer

Solution code:
import sys

# 最短経路に閉路がくっついているとは限らなかった・・・

read = sys.stdin.read
N, M, *uv, S, T = map(int, read().split())

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 15
# [けん,けんけん,けんけんぱ] * (N + 1)
dist = [[INF] * (N + 1) for _ in range(3)]
stack = [(0, 1)]

while stack:
    cost, v = stack.pop()
    if dist[cost % 3][v] < cost:
        continue

    dist[cost % 3][v] = cost
    for i in graph[v]:
        stack.append((cost + 1, i))

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

Submission status: Wrong Answer

Solution code:
import sys

# 最短経路に閉路がくっついているとは限らなかった・・・

read = sys.stdin.read
N, M, *uv, S, T = map(int, read().split())

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 18
# [けん,けんけん,けんけんぱ] * (N + 1)
dist = [INF] * (3 * (N + 1))
stack = [(0, 1)]

while stack:
    cost, v = stack.pop()
    r = cost % 3
    tmp = dist[3 * v + r]
    if tmp == INF:
        pass
    elif tmp < cost:
        continue

    dist[3 * v + r] = cost
    for i in graph[v]:
        stack.append((cost + 1, i))

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

Submission status: Wrong Answer

Solution code:
import sys

# 最短経路に閉路がくっついているとは限らなかった・・・

read = sys.stdin.read
N, M, *uv = map(int, read().split())
T = uv.pop()
S = uv.pop()

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 10
# [けん,けんけん,けんけんぱ] * (N + 1)
dist = [INF] * (3 * (N + 1))
stack = [(0, 1)]

while stack:
    cost, v = stack.pop()
    r = cost % 3
    if dist[3 * v + r] < cost:
        continue

    dist[3 * v + r] = cost
    for i in graph[v]:
        stack.append((cost + 1, i))

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

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heapify, heappush

# 最短経路に閉路がくっついているとは限らなかった・・・

read = sys.stdin.read
N, M, *uv = map(int, read().split())
T = uv.pop()
S = uv.pop()

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 10
# [けん,けんけん,けんけんぱ] * (N + 1)
dist = [INF] * (3 * (N + 1))
heap = [(0, 1)]
heapify(heap)

while heap:
    cost, v = heappop(heap)
    r = cost % 3
    if dist[3 * v + r] < cost:
        continue

    dist[3 * v + r] = cost
    for i in graph[v]:
        heappush(heap, (cost + 1, i))

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

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heapify, heappush

# 最短経路に閉路がくっついているとは限らなかった・・・

read = sys.stdin.read
N, M, *uv = map(int, read().split())
T = uv.pop()
S = uv.pop()

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = float('inf')
# [けん,けんけん,けんけんぱ] * (N + 1)
dist = [INF] * (3 * (N + 1))
heap = [(0, 1)]
heapify(heap)

while heap:
    cost, v = heappop(heap)
    r = cost % 3
    if dist[3 * v + r] < cost:
        continue

    dist[3 * v + r] = cost
    for i in graph[v]:
        heappush(heap, (cost + 1, i))

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

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heapify, heappush

# 最短経路に閉路がくっついているとは限らなかった・・・

read = sys.stdin.read
N, M, *uv = map(int, read().split())
T = uv.pop()
S = uv.pop()

graph = [[] for _ in range(3 * (N + 1))]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 10
# [けん,けんけん,けんけんぱ] * (N + 1)
dist = [INF] * (3 * (N + 1))
heap = [(0, 1)]
heapify(heap)

while heap:
    cost, v = heappop(heap)
    r = cost % 3
    if dist[3 * v + r] != INF:
        continue

    dist[3 * v + r] = cost
    for i in graph[v]:
        heappush(heap, (cost + 1, i))

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

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heapify, heappush


def dijkstra(grid, size, start):
    INF = 10 ** 9
    H, W = size
    table = [[INF] * W for _ in range(H)]

    H -= 1
    W -= 1
    heap = [(0, start)]
    heapify(heap)

    while heap:
        cost, (h, w) = heappop(heap)
        if table[h][w] != INF:
            continue

        table[h][w] = cost
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_w, new_h = w + j, h + i
            if 0 <= new_h <= H and 0 <= new_w <= W:
                new_cost = cost + grid[new_h][new_w]
                heappush(heap, (new_cost, (new_h, new_w)))

    return table


read = sys.stdin.read
N, M, *uv = map(int, read().split())
T = uv.pop()
S = uv.pop()

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 10
dist = [INF] * (N + 1)
heap = [(0, S)]
heapify(heap)
check = []
heapify(check)

while heap:
    cost, v = heappop(heap)
    if dist[v] != INF:
        heappush(check, (cost, v))
        continue

    dist[v] = cost
    for i in graph[v]:
        heappush(heap, (cost + 1, i))

if dist[T] == INF:
    print(-1)
elif dist[T] % 3 == 0:
    print(T // 3)
else:
    q = dist[T] // 3
    r = dist[T] % 3
    while check:
        cost, v = heappop(check)
        # 閉路の長さ
        d = cost - dist[v]
        # 実現可能な距離はdist[T] + d * n
        for i in range(1, 3):
            tmp = r + d * i
            if tmp % 3 == 0:
                print(q + tmp // 3)
                exit()

    print(-1)

Submission status: Wrong Answer

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

N,M=map(int,input().split())
L=[[]for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    L[a].append(b)
    
#print(L)
S,T=map(int,input().split())
dist=[[10**7 for i in range(N+1)]for j in range(3)]
dist[0][S]=0
#print(dist)
Q=[]
for i in L[1]:
    Q.append([i,1,0])

for i in range(10**7):
    if len(Q)==i:
        break
    if dist[(Q[i][2]+1)%3][Q[i][0]] == 10**7:
        dist[(Q[i][2]+1)%3][Q[i][0]] = dist[(Q[i][2])%3][Q[i][1]] + 1
        for j in L[Q[i][0]]:
            if dist[(Q[i][2]+2)%3][j] == 10**7:
                Q.append([j,Q[i][0],Q[i][2]+1])
if dist[0][T]%3==0:
    print(dist[0][T]//3)
else:
    print(-1)

Submission status: Wrong Answer

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

N,M=map(int,input().split())
L=[[]for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    L[a].append(b)
    
#print(L)
S,T=map(int,input().split())
dist=[[10**6 for i in range(N+1)]for j in range(3)]
dist[0][S]=0
#print(dist)
Q=[]
for i in L[1]:
    Q.append([i,1,0])

for i in range(10**6):
    if len(Q)==i:
        break
    if dist[(Q[i][2]+1)%3][Q[i][0]] == 10**6:
        dist[(Q[i][2]+1)%3][Q[i][0]] = dist[(Q[i][2])%3][Q[i][1]] + 1
        for j in L[Q[i][0]]:
            if dist[(Q[i][2]+2)%3][j] == 10**6:
                Q.append([j,Q[i][0],Q[i][2]+1])
if dist[0][T]%3==0:
    print(dist[0][T]//3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph1 = [[] for _ in range(N + 1)]
for U, V in UV:
  graph1[U].append(V)
#print("graph1:", graph1)

graph2 = [[] for _ in range(N + 1)]
for i in range(len(graph1)):
  for g in graph1[i]:
    for gg in graph1[g]:
      graph2[i].append(gg)
#print("graph2:", graph2)

graph3 = [[] for _ in range(N + 1)]
for i in range(len(graph2)):
  for g in graph2[i]:
    for gg in graph1[g]:
      graph3[i].append(gg)
#print("graph3:", graph3)

INF = 10 ** 10
dist = [INF] * (N + 1)

stack = []
for g in graph3[S]:
  stack.append(g)
  dist[g] = 1

while stack:
  s = stack.pop()
  for g in graph3[s]:
    if dist[g] == 0:
      dist[g] = INF
    if dist[g] > dist[s] + 1:
      dist[g] = dist[s] + 1
      stack.append(s)
#print("dist:", dist)
print(dist[T] if dist[T] != INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=list(map(int,input().split()))
    g[u-1].append(v-1)
s,t=map(int,input().split())
s-=1;t-=1
INF=10**9
U=[[INF]*n for i in range(3)]
U[0][s]=0
que=deque([(s,0)])
while que:
    v,t=que.popleft()
    u=(t+1)%3
    d=U[t][v]
    if t==2:
        d+=1
    for w in g[v]:
        if U[u][w]!=INF:
            continue
        que.append((w,u))
        U[u][w]=d

print(U[0][t] if U[0][t]<INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=list(map(int,input().split()))
    g[u-1].append(v-1)
s,t=map(int,input().split())
s-=1;t-=1
INF=10**9
U=[[INF]*n for i in range(3)]
U[0][s]=0
que=deque([(s,0)])
while que:
    v,t=que.popleft()
    u=(t+1)%3
    for w in g[v]:
        if U[u][w]!=INF:
            continue
        que.append((w,u))
        if t==2:
            U[u][w]=U[t][v]+1

print(U[0][t] if U[0][t]<INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=list(map(int,input().split()))
    g[u-1].append(v-1)
s,t=map(int,input().split())
s-=1;t-=1
INF=10**9
U=[[INF]*n for i in range(3)]
U[0][s]=0
que=deque([(s,0)])
while que:
    v,t=que.popleft()
    u=(t+1)%3
    d=U[t][v]
    if t==2:
        d+=1
    for w in g[v]:
        if U[u][w]!=INF:
            continue
        que.append((w,u))
        U[u][w]=d
print(U)
print(U[0][t] if U[0][t]<INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=list(map(int,input().split()))
    g[u-1].append(v-1)
s,t=map(int,input().split())
s-=1;t-=1
INF=10**9
U=[[INF]*n for i in range(3)]
U[0][s]=0
que=deque([(s,0)])
while que:
    v,t=que.popleft()
    u=(t+1)%3
    d=U[u][v]
    if t==2:
        d+=1
    for w in g[v]:
        if U[u][w]!=INF:
            continue
        que.append((w,u))
        U[u][w]=d
print(U[0][t] if U[0][t]<INF else -1)

Submission status: Wrong Answer

Solution code:
N,M=[int(s) for s in input().split()]
edge = [set() for _ in range(3*N)]
for i in range(M):
  x,y=[int(s) for s in input().split()]
  edge[x-1].add(y-1+N)    #有向グラフなので片方でよい
  edge[x-1+N].add(y-1+2*N)
  edge[x-1+2*N].add(y-1)
S,T=[int(s) for s in input().split()]
stack=[S-1]   #indexに注意
dist=[0 for _ in range(3*N)]
flag=0
while stack: #stackが空になるまで
  vrt = stack.pop()
  for to in edge[vrt].copy():
    stack.append(to)
    if dist[to]>0:              #木でないならこの行が必要
      if dist[to]>dist[vrt]+1:  #木でないならこの行が必要
        dist[to]=dist[vrt]+1    #木でないならこの行が必要
    else:                       #木でないならこの行が必要
      dist[to]=dist[vrt]+1      #木のときはここだけ残す
    edge[vrt].discard(to)

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

Submission status: Wrong Answer

Solution code:
N,M=[int(s) for s in input().split()]
edge = [set() for _ in range(3*N)]
for i in range(M):
  x,y=[int(s) for s in input().split()]
  edge[x-1].add(y-1+N)    #有向グラフなので片方でよい
  edge[x-1+N].add(y-1+2*N)
  edge[x-1+2*N].add(y-1)
S,T=[int(s) for s in input().split()]
stack=[S-1]   #indexに注意
dist=[0 for _ in range(3*N)]
flag=0
while stack: #stackが空になるまで
  vrt = stack.pop()
  for to in edge[vrt].copy():
    stack.append(to)
    if dist[to]>0:              #木でないならこの行が必要
      if dist[to]>dist[vrt]+1:  #木でないならこの行が必要
        dist[to]=dist[vrt]+1    #木でないならこの行が必要
    else:                       #木でないならこの行が必要
      dist[to]=dist[vrt]+1      #木のときはここだけ残す
    edge[vrt].discard(to)

if dist[T-1]==0:
  print(-1)
else:
  print(dist[T-1])

Submission status: Wrong Answer

Solution code:
N,M=[int(s) for s in input().split()]
edge = [set() for _ in range(3*N)]
for i in range(M):
  x,y=[int(s) for s in input().split()]
  edge[x-1].add(y-1+N)    #有向グラフなので片方でよい
  edge[x-1+N].add(y-1+2*N)
  edge[x-1+2*N].add(y-1)
S,T=[int(s) for s in input().split()]
stack=[S-1]   #indexに注意
dist=[0 for _ in range(3*N)]
flag=0
while stack: #stackが空になるまで
  vrt = stack.pop()
  for to in edge[vrt].copy():
    stack.append(to)
    if dist[to]>0:              #木でないならこの行が必要
      if dist[to]>dist[vrt]+1:  #木でないならこの行が必要
        dist[to]=dist[vrt]+1    #木でないならこの行が必要
    else:                       #木でないならこの行が必要
      dist[to]=dist[vrt]+1      #木のときはここだけ残す
    if to==T-1:       #indexに注意
      print(dist[to]//3)
      flag=1         #目的の場所に来たら終了したい
      break
    edge[vrt].discard(to)
  if flag==1:
    break
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

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

dic = {}
nend = [True] * N
far = [float("inf")] * N

for i in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []
    if v not in dic:
        dic[v] = []

    dic[u].append(v)
    dic[v].append(u)

q = []

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

heapq.heappush(q,[0,S])

while len(q) > 0:

    now = heapq.heappop(q)
    nd = now[0]
    np = now[1]
    nend[np] = False
    
    far[np] = min(far[np],nd)

    if np in dic:
        for i in dic[np]:

            if nend[i]:
                heapq.heappush(q,[nd + 1 , i])

if far[T] == float("inf"):
    print (-1)
else:
    print (far[T] // 3 + far[T] % 3)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, raw_input().split())
E = np.empty([M,2], dtype=int)
for i in xrange(M):
    E[i] = map(int, raw_input().split())

E -= 1    
S, T = map(int, raw_input().split())

Dist = [[] for i in xrange(N)]
for i in xrange(M):
    Dist[E[i][0]].append(E[i][1])

def search_three_steps(S, Dist):
    T_1 = Dist[S]
    T_2 = sum([Dist[s] for s in T_1], [])
    T_3 = sum([Dist[s] for s in T_2], [])
    return T_3

def search_one_step(S, Dist):
    return sum([Dist[s] for s in S], [])

def delete_repeat(A, B):
    for b in B:
        if b in A:
            B.remove(b)
        else:
            A.append(b)

Dist_new = []
for i in xrange(N):
    Dist_new.append(search_three_steps(i, Dist))

searched = [S-1]
start = [S-1]
for i in xrange(1, 2000):
    end = search_one_step(start, Dist_new)
    delete_repeat(searched, end)
    if T-1 in end:
        print i
        break
    elif end == []:
        print -1
        break
    start = end

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
N, M = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    G[(u-1, 0)].append((v-1, 1))
    G[(u-1, 1)].append((v-1, 2))
    G[(u-1, 2)].append((v-1, 0))
S, T = map(int, input().split())
dist = defaultdict(lambda : -1)
que = deque([(S-1, 0)])
dist[(S-1, 0)] = 0
while que:
    v = que.pop()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]>=0:
            continue
        dist[nv] = d+1
        que.append(nv)
print(dist[(T-1, 0)]//3)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
N, M = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    G[(u-1, 0)].append((v-1, 1))
    G[(u-1, 1)].append((v-1, 2))
    G[(u-1, 2)].append((v-1, 0))
S, T = map(int, input().split())
G3 = defaultdict(list)
dist = defaultdict(lambda : -1)
que = deque([(S-1, 0)])
dist[(S-1, 0)] = 0
while que:
    v = que.pop()
    if v == (T-1, 0):
        break
    d = dist[v]
    for nv in G[v]:
        if dist[nv]>=0:
            continue
        dist[nv] = d+1
        que.append(nv)
print(dist[(T-1, 0)]//3)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())

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

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

s, t = map(int, input().split())
s -= 1
t -= 1
s = s * 3
t = t * 3

from heapq import heappush, heappop


def dijkstra(graph: list, n: int, start: int, INF: int = float('inf')) -> list:
    # graph[node] = [(cost, to)]
    dist = [INF] * n
    num = [0] * n

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        _, v_from = heappop(heap)
        for v_to in graph[v_from]:
            dist_cand = dist[v_from] + 1
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist
    # dist = [costs to nodes]


inf = float('inf')
dist = dijkstra(graph1, n * 3, s, INF=10**8)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t] // 3)

Submission status: Wrong Answer

Solution code:
def search(S_list,current_count=0):
    next_list = []
    for s in S_list:
        for i1 in graph[s]:
            for i2 in graph[i1]:
                for i3 in graph[i2]:
                    if already_reach[i3] == -1: #はじめての到達
                        already_reach[s] = current_count+1
                        next_list.append(i3)
    if len(next_list) > 0:
        search(next_list,current_count+1)

Submission status: Wrong Answer

Solution code:
from collections import deque as dq
n,m = list(map(int,input().split()))
graph = [[] for i in range(n)]
for i in range(m):
    a,b = list(map(int,input().split()))
    a -= 1;b -= 1
    graph[a].append(b)
s,t = list(map(int,input().split()))
s -= 1;t -= 1
check = [[-1,-1,-1] for i in range(n)]
que = dq()
que.appendleft([s,0])
check[s][0] = 0
while (que):
    v,l = que.pop()
    for i in graph[v]:
        if check[i][(l+1)%3] == -1:
            que.append([i,(l+1)%3])
            check[i][(l+1)%3] = check[v][l] + 1
if check[t][0] == -1:
    print(-1)
else:
    print(check[t][0] // 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


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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()
G = [[] for _ in range(n)]
for _ in range(m):
    x, y = LI()
    G[x - 1] += [y - 1]
    G[y - 1] += [x - 1]

dist = [[INF] * n for _ in range(3)]
s, t = LI()
dist[0][s - 1] = 0
dq = deque([(0, s - 1)])
while dq:
    cost, u = dq.popleft()
    for v in G[u]:
        if cost + 1 < dist[(cost + 1) % 3][v]:
            dist[(cost + 1) % 3][v] = cost + 1
            dq += [(cost + 1, v)]


ans = dist[0][t - 1]
if ans == INF:
    print(-1)
else:
    print(ans // 3)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
n,m=map(int,input().split())
g=[[] for _ in range(3*n)]
for _ in range(m):
  u,v=map(int, sys.stdin.readline().split())
  u-=1
  v-=1
  g[u].append(n+v)
  g[u+n].append(v+2*n)
  g[u+2*n].append(v)
s,t=map(int,input().split())
s-=1
t-=1
vit=set([s])
ans=[-3]*3*n
q=deque([s])
ans[s]=0
while q:
  a=q.pop()
  for b in g[a]:
    if b in vit:
      continue
    vit.add(b)
    ans[b]=ans[a]+1 
    q.append(b)
print(ans[t]//3)

Submission status: Wrong Answer

Solution code:
from collections import deque

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[u].append(n+v)
  g[u+n].append(v+2*n)
  g[u+2*n].append(v)
s,t=map(int,input().split())
s-=1
t-=1
vit=set([s])
ans=[-3]*3*n
q=deque([s])
ans[s]=0
while q:
  a=q.pop()
  for b in g[a]:
    if b in vit:
      continue
    vit.add(b)
    ans[b]=ans[a]+1 
    q.append(b)
print(ans[t]//3)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(3*n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[3*u].append(3*v+1)
        E[3*u+1].append(3*v+2)
        E[3*u+2].append(3*v)
    s,t=map(int,input().split())
    s-=1; t-=1

    # DFS
    from collections import deque
    d=[INF]*(3*n)
    d[3*s]=0
    stack=[]
    stack.append(3*s)
    while(stack):
        v=stack.pop()
        for nv in E[v]:
            if(d[nv]!=INF): continue
            d[nv]=min(d[v]+1,d[nv])
            stack.append(nv)
    ans=d[3*t]
    print(ans//3 if(ans!=INF) else -1)
resolve()

Submission status: Wrong Answer

Solution code:
import collections
N,M = map(int,input().split())
edge = collections.defaultdict(list)
for _ in range(M):
    u,v = map(int,input().split())
    edge[u-1].append(v-1)
S,T = map(int,input().split())
dp = [-1 for _ in range(N)]
dp[S-1] = 0
q = collections.deque()
q.append(S-1)
while q:
    p = q.pop()
    for k1 in edge[p]:
        for k2 in edge[k1]:
            for k3 in edge[k2]:
                if dp[k3] == -1:
                    dp[k3] = dp[p] + 1
                    q.append(k3)
                    if k3 == T-1:
                        break
print(dp[T-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
G = {}
for i in range(3*n):
    G[i] = []
for i in range(m):
    ui, vi = map(int, input().split())
    ui = (ui-1)*3
    vi = (vi-1)*3
    G[ui].append(vi+1)
    G[ui+1].append(vi+2)
    G[ui+2].append(vi)
s, t = map(int, input().split())
s = (s-1) * 3
t = (t-1) * 3

res = -1

q = deque()

c = s

dist = {c: -1}
q.append(c)
visited = {c: True}
while len(q) != 0:
    p = c
    c = q.popleft()
    dist[c] = dist[p] + 1
    visited[c] = True
    if c == t:
        res = dist[c]
        break
    for nv in G[c]:
        if not nv in visited:
            visited[nv] = True
            q.append(nv)


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

Submission status: Wrong Answer

Solution code:
from itertools import count
N,M = map(int,input().split())

adj = [list() for _ in range(N)]


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

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

visited = [False]*(N*3)
visited[S] = True
q = [S]

for step in count():
    offset = N*(step % 3)
    nq = []
    for u in q:
        for v in adj[u]:
            if not visited[v+offset]:
                nq.append(v)
                visited[v+offset] = True
    q = nq

    if visited[T] or not q:
        break
if visited[T]:
    print(step//3)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from itertools import count
N,M = map(int,input().split())

adj = [list() for _ in range(N)]


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

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

visited = [False]*(N*3)
visited[S] = True
q = [S]

for step in range(1,10):
    offset = N*(step % 3)
    nq = []
    for u in q:
        for v in adj[u]:
            if not visited[v+offset]:
                nq.append(v)
                visited[v+offset] = True
    q = nq

    if visited[T] or not q:
        break
if visited[T]:
    print(step//3)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M=map(int,input().split())
# 頂点の番号は0-initialのまま扱う
E=set() # 辺から成るset
for i in range(M):
    u,v=map(int,input().split())
    E.add((u,v))
S,T=map(int,input().split())

d1=[set() for i in range(N+1)] # d1[i]=頂点iからの距離が1であるような頂点vから成るset
for e in E:
    u=e[0];v=e[1]
    d1[u].add(v)

d2=[set() for i in range(N+1)] # d2[i]=頂点iからの距離が2であるような頂点vから成るset
for e in E:
    u=e[0];v=e[1]
    d2[u].update(d1[v])

d3=[set() for i in range(N+1)]
for e in E:
    u=e[0];v=e[1]
    d3[u].update(d2[v])

dis={S:0} # 頂点v:頂点Sからの距離
# WFS
q=deque()
q.append(S)
while q:
#    print(q) #DB
#    print(dis) #DB
    u=q.popleft()
    vs=d3[u]-set(dis)
    for v in vs:
        dis[v]=dis[u]+1
    q.extend(vs)
print(dis) #DB
print(-1 if T not in dis else dis[T])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
UVST = list(map(int,read().split()))
S,T = UVST[-2:]
UV = UVST[:-2]; U = UV[::2]; V = UV[1::2]

graph = [[] for _ in range(1+N+N+N)]
for x,y in zip(U,V):
    x1=x+N; x2=x1+N
    y1=y+N; y2=y1+N
    graph[x].append(y1)
    graph[x1].append(y2)
    graph[x2].append(y)   

INF = 10**15
dist = [INF] * (N+N+N+1)
dist[S] = 0
stack = [S]
while stack:
    x = stack.pop()
    for y in graph[x]:
        if dist[y] != INF:
            continue
        stack.append(y)
        dist[y] = dist[x] + 1

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)

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