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:
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
used = [False] * (3 * N)


que = [(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 = INF
if d[3 * T] % 3 == 0:
    ans = d[3 * T] // 3

if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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


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

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

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

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

Submission status: Wrong Answer

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


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

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

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

Submission status: Wrong Answer

Solution code:
N,M = [int(s) for s in input().split()]
vertexes=[0]*(3*N)
edges=[]
for i in range(M):
  x,y=[int(s) for s in input().split()]
  edges=edges+([[x,N+y],[N+x,N+N+y],[N+N+x,y]])
edges=sorted(edges)
def possibleQ(ver,edge,num1,num2):
  num_edges=len(edge)
  poss=[num1]
  val_array=[]
  for j in range(0,3*N):
    for i in range(num_edges):
      if(edge[i][0]==poss[j]):
        val_array.append(edge[i][1])
      elif(edge[i][0]>poss[j]):
        break
    if(num2 in val_array):
      return j+1
      break
    poss=poss+list(set(val_array)-set(poss))
    if(j+1==len(poss)):
      return -1
      break
S,T= [int(s) for s in input().split()]
print(possibleQ(vertexes,edges,S,T)//3)

Submission status: Wrong Answer

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

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

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

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

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

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

BFS((S, 0))

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

Submission status: Wrong Answer

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

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

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

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, deq, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] < inf): continue
        dist[node] = dist[now] + 1
        deq.append(node)
    if(len(deq) > 0):
        next_node = deq.popleft()
        BST(next_node, deq, dist)
    return

deq = deque()
BST((S, 0), deq, dist)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
n, m = map(int, input().split())

edges = defaultdict(lambda: [])
for i in range(m):
    u, v = map(int, input().split())
    u1, v1 = (0, u), (1, v)
    u2, v2 = (1, u), (2, v)
    u3, v3 = (2, u), (0, v)
    edges[u1].append(v1)
    edges[u2].append(v2)
    edges[u3].append(v3)
    edges[v1].append(u1)
    edges[v2].append(u2)
    edges[v3].append(u3)

#print(edges)
s, t = map(int, input().split())
s = (0, s)
t = (2, t)

dist = {}
dist[s] = 0
visiting = deque()
visiting.append(s)
while len(visiting) > 0:
    v = visiting.popleft()
    # check neighbors of v
    neighbors = edges[v]
    for neighbor in neighbors:
        if neighbor in dist:
            continue
        visiting.append(neighbor)
        dist[neighbor] = dist[v] + 1
        
    if t in dist:
        break
#print(dist)
if t not in dist:
    print(-1)
else:
    print(dist[t])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque
N, M = map(int, input().split())
e = dd(list)
inf = 10 ** 9
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v + N)
  e[u + N].append(v + 2 * N)
  e[u + 2 * N].append(v)
S, T = map(int, input().split())
T += 2 * N
stopped = [inf] * (3 * N + 1)
Q = deque()
Q.append(S)
stopped[S] = 0
while len(Q) != 0:
  p = Q.popleft()
  if stopped[p] >= stopped[T]:
    break
  for q in e[p]:
    if stopped[q] > stopped[p] + 1:
      Q.append(q)
      stopped[q] = stopped[p] + 1
if stopped[T] == inf:
  print(-1)
else:
  print(stopped[T])

Submission status: Wrong Answer

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

e=[1]
f=[1]
h=0
for i in range(1,a+1):
  g=[]
  for j in f:
    for k in d[j]:
      if k not in e:
        e.append(k)
        g.append(k)
  if g==[]or i==a:
    print(-1)
    break
  for j in g:
    if j==t:
      print(i)
      h=1
      break
  if h==1:
    break

  f=copy.copy(g)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
u=[0]*M
v=[0]*M
for i in range(M):
  u[i],v[i] = map(int, input().split())
S,T=map(int, input().split())

edges = []
for i in range(M):
  edges.append([u[i]*3-3, v[i]*3-2])
  edges.append([u[i]*3-2, v[i]*3-1])
  edges.append([u[i]*3-1, v[i]*3-3])

def edges_to_pt(edges,n):
  '''
  input
    edges: 枝の[始点,終点]を格納した2次元配列　edges=[[0,1],[1,2],[2,0]]
    n:  頂点数 n=3

  output
    pt: 各点との結合場所を格納した2次元配列 pt=[[1],[2],[0]]
  '''
  pt = [[] for i in range(n)]
  while edges:
    temp_edge = edges.pop()
    pt[temp_edge[0]].append(temp_edge[1])
  return pt

def dfs(pt,v):
  '''
  input
    pt: 各点との結合場所を格納した2次元配列　pt=[[1, 2, 3], [0], [5, 0], [6, 0], [6], [2], [3, 4]]
    v: 初期点 v=0

  output
    d: 初期点からの距離を格納した配列 d=[0, 1, 1, 1, 3, 2, 2]
  '''
  n=len(pt)
  d=[-1]*n
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
  return d

pt = edges_to_pt(edges,3*N)
ans = dfs(pt,3*S-3)[3*T-3] // 3

if ans == -1:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
#TLE

from collections import deque

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

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

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

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

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


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


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

print(breadth_first_search(S,T,G))

Submission status: Wrong Answer

Solution code:
from collections import deque
 
N, M = map(int, input().split())
 
vec = [[] for _ in range(N)]
for _ in range(M) :
    u, v = map(int, input().split())
    vec[u-1].append(v-1)
 
S, T = map(int, input().split())
S, T = S - 1, T - 1
 
visited = [[False] * N for _ in range(3)]
visited[0][S] = True
queue = deque([(S, 0)])
 
while queue :
    print(queue)
    q, cost = queue.popleft()
    print(q,cost)
    print("vec[q] =",vec[q])
    p = (cost + 1) % 3
    for i in vec[q] :
        if p == 0 and i == T :
            
            print((cost + 1) // 3)
            exit()
        if not visited[p][i] :
            visited[p][i] = True
            #print(visited)
            #print(i)
            queue.append((i, cost + 1))
 
print(-1)

Submission status: Wrong Answer

Solution code:
#パクリ　記録用
from collections import deque
 
N, M = map(int, input().split())
 
vec = [[] for _ in range(N)]
for _ in range(M) :
    u, v = map(int, input().split())
    vec[u-1].append(v-1)
 
S, T = map(int, input().split())
S, T = S - 1, T - 1
 
visited = [[False] * N for _ in range(3)]
visited[0][S] = True
queue = deque([(S, 0)])
 
while queue :
    print(queue)
    q, cost = queue.popleft()
    print(q,cost)
    print("vec[q] =",vec[q])
    p = (cost + 1) % 3
    for i in vec[q] :
        if p == 0 and i == T :
            
            print((cost + 1) // 3)
            exit()
        if not visited[p][i] :
            visited[p][i] = True
            #print(visited)
            #print(i)
            queue.append((i, cost + 1))
 
print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque

N, M = list(map(int, input().split()))
graph = {str(i+1)+a:deque() for i in range(N) for a in 'abc'}
visited = {key:[False, 10**20] for key in graph.keys()}

for i in range(M):
    u, v = input().split()
    graph[u+'a'].append(v+'b')
    graph[u+'b'].append(v+'c')
    graph[u+'c'].append(v+'a')

S, T = input().split()
q = [(S+'a', 0)]
visited[S+'a'][1] = 0

while q:

    u, cost = heapq.heappop(q)

    if not visited[u][0]:
        visited[u][0] = True
        cost += 1

        for v in graph[u]:
            if cost < visited[v][1]:
                visited[v][1] = cost
                heapq.heappush(q, (v, cost))

flag, cost = visited[T+'a']

if flag and not cost % 3:
    print(cost//3)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

N, M = list(map(int, input().split()))
graph = {str(i+1)+a:[] for i in range(N) for a in 'abc'}
visited = {key:[False, 10**20] for key in graph.keys()}

for i in range(M):
    u, v = input().split()
    graph[u+'a'].append(v+'b')
    graph[u+'b'].append(v+'c')
    graph[u+'c'].append(v+'a')

S, T = input().split()
q = [(S+'a', 0)]
visited[S+'a'][1] = 0

while q:

    u, cost = heapq.heappop(q)

    if not visited[u][0]:
        visited[u][0] = True
        cost += 1
        for v in graph[u]:
            if cost < visited[v][1]:
                visited[v][1] = cost
                heapq.heappush(q, (v, cost))

if visited[T+'a'][0]:
    print(visited[T+'a'][1]//3)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

INF = float('inf')
dist = [[INF for i in range(3)] for j in range(N)]

def bfs():
    q = deque()
    q.append((S, 0))
    dist[S][0] = 0
    while q:
        p = q.popleft()
        v = p[0]
        l = p[1]
        for nv in edge[v]:
            nl = (l+1)%3
            if dist[nv][nl] != INF:
                continue
            dist[nv][nl] = dist[v][l] + 1
            q.append((nv, nl))
    return dist[T][0]

ans = bfs()
if ans == INF:
    ans = -1
else:
    ans /= 3
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

INF = float('inf')
dist = [[INF for i in range(3)] for j in range(N)]

def bfs():
    q = deque()
    q.append((S, 0))
    dist[S][0] = 0
    while q:
        p = q.popleft()
        v = p[0]
        l = p[1]
        for nv in edge[v]:
            nl = (l+1)%3
            if dist[nv][nl] != INF:
                continue
            dist[nv][nl] = dist[v][l] + 1
            q.append((nv, nl))
    return dist[T][0] // 3

print(bfs())

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
nodes =[[[]for _ in range(3)] for j in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    nodes[u-1][0].append((v-1, 1))
    nodes[u-1][1].append((v-1, 2))
    nodes[u-1][2].append((v-1, 0))
S, T = map(int, input().split())
que = [(S-1, 0, 0)]
flag = [[False]*3 for _ in range(N)]
flag[0][0]=True
ans = -1
while que:
    edge, cnt, distance = que.pop()
    #print(edge, cnt, distance)
    if edge == T-1 and cnt == 0:
        ans = distance
        break
    for ni in nodes[edge][cnt]:
        a, b = ni
        if flag[a][b]:
            continue
        que.append((a, b, distance+1))
        flag[a][b] = True
print(ans//3)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
E = [list(map(int, input().split())) for _ in range(M)]
S,T = map(int, input().split())
#辺の重みがすべて１のダイクストラ
#optionsはすでに計算された経路、[頂点]
options = []
#optionsに対応したコスト
cost = []
#xは現在地, コスト
x = [S, 0]

while True:
    print(x)
    for e in E:
        if e[0] == x[0]:
            options.append(e[1])
            cost.append(x[1] + 1)
    if len(options) == 0:
        break
        
    x = [options.pop(cost.index(min(cost))), cost.pop(cost.index(min(cost)))]

    if x[1]%3 == 0:
        if x[0] == T:
            break
    if x[1] > M:
        break
            
if x[0] == T:
    print(int(x[1]/3))
else:
    print(-1)

Submission status: Wrong Answer

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

s, g = map(int, input().split(" "))

def indicate3(start,path):
    global unreachable
    ifReachable = False
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        if g in next:
            ifReachable = True
        start = next

    if not ifReachable:
        unreachable = True
    return start

stack = [s]
count = 0
unreachable = False
while True:
    n_stack = indicate3(stack,path)
    if g in n_stack:
        count += 1
        print(count)
        break
    else:
        if n_stack == stack:
            print(-1)
            break
        else:
            count += 1
            if unreachable == True:
                print(-1)
                break
    stack = n_stack

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  n,m = (int(i) for i in input().split())
  step = [[] for _ in range(n)] 
  for i in range(m):
    u,v = (int(i) for i in input().split())
    if not v in step[u-1]:
     step[u-1].append(v)


  S,T = (int(i) for i in input().split())
  query = deque([])
  query.append((S,0))
  visit = [False for _ in range(n+2)]
  ans = 5000000
  checker = 0
  time = 0
  while query:
    time += 1
    place,move = query.popleft()
    move += 1 
    if move%3 ==0 and visit[place]:
      continue  
    else:
      if move%3 == 0: 
        visit[place] = True
      for i in range(len(step[place-1])):
        query.append((step[place-1][i],move))
        
    if place == T and (move-1)%3 == 0:
      ans = min(ans,move-1)
      break
    if time >= 500000:
      break
  if not ans == 5000000:
   print(ans//3)
  else:
    print(-1)
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
def solve():
  n,m = (int(i) for i in input().split())
  step = [[] for _ in range(n)] 
  for i in range(m):
    u,v = (int(i) for i in input().split())
    if not v in step[u-1]:
     step[u-1].append(v)


  S,T = (int(i) for i in input().split())
  query = deque([])
  query.append((S,0))
  visit = [False for _ in range(n+2)]
  ans = 5000000
  checker = 0
  while (query):
    place,move = query.popleft()
    move += 1
    if place == T and (move-1)%3 == 0:
      ans = min(ans,move-1)
      break
    if visit and move%3 == 0:
      checker += 1
      if checker == 51551:
        print(-1)
        exit()
    
    if move%3 ==0 and visit[place]:
      continue
    else:
      if move%3 == 0: 
        visit[place] = True
      for i in range(len(step[place-1])):
        
        query.append((step[place-1][i],move))

       ## print(query)
    
  if not ans == 5000000:
   print(ans//3)
  else:
    print(-1)
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
def solve():
  n,m = (int(i) for i in input().split())
  step = [[] for _ in range(n)] 
  for i in range(m):
    u,v = (int(i) for i in input().split())
    if not v in step[u-1]:
     step[u-1].append(v)
    if not u in step[v-1]:
     step[v-1].append(u)
  ##print(step)
  S,T = (int(i) for i in input().split())
  query = deque([])
  query.append((S,0))
  visit = [False for _ in range(n+2)]
  ans = 5000000
  checker = 0
  while (query):
    place,move = query.popleft()
    move += 1
    if place == T and (move-1)%3 == 0:
      ans = min(ans,move-1)
      break
    if visit and move%3 == 0:
      checker += 1
      if checker == 51551:
        print(-1)
        exit()
    
    if move%3 ==0 and visit[place]:
      continue
    else:
      if move%3 == 0: 
        visit[place] = True
      for i in range(len(step[place-1])):
        
        query.append((step[place-1][i],move))

        
    
  if not ans == 5000000:
   print(ans//3)
  else:
    print(-1)
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int,input().split())
uv = [[] for _ in range(n)]
for i in range(m):
  u,v = map(lambda x:int(x)-1,input().split())
  uv[u].append(v)
s,t = map(lambda x:int(x)-1,input().split())
time = 0
now = deque([s])
flag = 0
while time < n:
  time += 1
  tmp = deque([])
  for x in now:
    for y in uv[x]:
      tmp.append(y)
  now = tmp
  if time % 3 == 0:
    if t in now:
      flag = 1
      break
if flag == 1:
  print(time//3)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

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

# edges , costs
nodes = [[] for _ in range(3 * N)]

confilm = [False] * (3 * N)  # 確定フラグ

costs = [-1] * (3 * N)  # 最短経路

# 辺の入力
for _ in range(M) :
    fromNode , toNode = map(int,input().split())
    fromNode -= 1
    toNode -= 1
    fromNode *= 3
    toNode *= 3

    nodes[fromNode].append((toNode + 1,1))
    nodes[fromNode + 1].append((toNode + 2,1))
    nodes[fromNode + 2].append((toNode,1))


# スタート ゴール
startNode , endNode = map(int,input().split())
startNode -= 1
endNode -= 1

costs[startNode] = 0

q = [(0,startNode)]

# 探索
while q : # 空になるまで
    nowCost , nowNode = heapq.heappop(q)

    if confilm[nowNode] :
        continue

    confilm[nowNode] = True

    # 長さを更新
    for nextNode , cost in nodes[nowNode] :
        # if not confilm[nextNode] :  # 確定ノード以外
        nextCost = nowCost + cost
        if costs[nextNode] == -1 or nextCost < costs[nextNode] :
            costs[nextNode] = nextCost  # コストを更新
            heapq.heappush(q,(nextCost,nextNode))

if costs[endNode * 3] < 0 :
    print(-1)
else :
    print(costs[endNode * 3] // 3)

Submission status: Wrong Answer

Solution code:
import heapq

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

# edges , costs
nodes = [[] for _ in range(3 * N)]

confilm = [False] * (3 * N)  # 確定フラグ

costs = [-1] * (3 * N)  # 最短経路

# 辺の入力
for _ in range(M) :
    fromNode , toNode = map(int,input().split())
    fromNode -= 1
    toNode -= 1
    fromNode *= 3
    toNode *= 3

    nodes[fromNode].append((toNode + 1,1))
    nodes[fromNode + 1].append((toNode + 2,1))
    nodes[fromNode + 2].append((toNode,1))


# スタート ゴール
startNode , endNode = map(int,input().split())
startNode -= 1
endNode -= 1

costs[startNode] = 0

q = [(0,startNode)]

# 探索
while q : # 空になるまで
    nowNode = heapq.heappop(q)[1]

    confilm[nowNode] = True

    # 長さを更新
    for nextNode , cost in nodes[nowNode] :
        if not confilm[nextNode] :  # 確定ノード以外
            nextCost = costs[nowNode] + cost
            if costs[nextNode] == -1 or nextCost < costs[nextNode] :
                costs[nextNode] = nextCost  # コストを更新
                if not nextNode in q :
                    heapq.heappush(q,(nextCost,nextNode))

if costs[endNode * 3] < 0 :
    print(-1)
else :
    print(costs[endNode * 3] // 3)

Submission status: Wrong Answer

Solution code:
import heapq

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

# edges , costs
nodes = [[] for _ in range(3 * N)]

confilm = [False] * (3 * N)  # 確定フラグ

costs = [-1] * (3 * N)  # 最短経路

# 辺の入力
for _ in range(M) :
    fromNode , toNode = map(int,input().split())
    fromNode -= 1
    toNode -= 1
    fromNode *= 3
    toNode *= 3

    nodes[fromNode].append((toNode + 1,1))
    nodes[fromNode + 1].append((toNode + 2,1))
    nodes[fromNode + 2].append((toNode,1))


# スタート ゴール
startNode , endNode = map(int,input().split())
startNode -= 1
endNode -= 1

if startNode == endNode :
    print(0)
else :
    costs[startNode] = 0

    q = [(0,startNode)]

    # 探索
    while q : # 空になるまで
        nowNode = heapq.heappop(q)[1]

        if confilm[nowNode] :
            continue

        confilm[nowNode] = True

        # 長さを更新
        for nextNode , cost in nodes[nowNode] :
            if not confilm[nextNode] :  # 確定ノード以外
                nextCost = costs[nowNode] + cost
                if costs[nextNode] == -1 or nextCost < costs[nextNode] :
                    costs[nextNode] = nextCost  # コストを更新
                    heapq.heappush(q,(nextCost,nextNode))

    if costs[endNode * 3] < 0 :
        print(-1)
    else :
        print(costs[endNode * 3] // 3)

Submission status: Wrong Answer

Solution code:
import heapq

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

# edges , costs
nodes = [[] for _ in range(3 * N)]

confilm = [False] * (3 * N)  # 確定フラグ

costs = [-1] * (3 * N)  # 最短経路

# 辺の入力
for _ in range(M) :
    fromNode , toNode = map(int,input().split())
    fromNode -= 1
    toNode -= 1
    fromNode *= 3
    toNode *= 3

    nodes[fromNode].append((toNode + 1,1))
    nodes[fromNode + 1].append((toNode + 2,1))
    nodes[fromNode + 2].append((toNode,1))


# スタート ゴール
startNode , endNode = map(int,input().split())
startNode -= 1
endNode -= 1

costs[startNode] = 0

q = [(0,startNode)]

# 探索
while q : # 空になるまで
    nowNode = heapq.heappop(q)[1]

    if confilm[nowNode] :
        continue

    confilm[nowNode] = True

    # 長さを更新
    for nextNode , cost in nodes[nowNode] :
        if not confilm[nextNode] :  # 確定ノード以外
            nextCost = costs[nowNode] + cost
            if costs[nextNode] == -1 or nextCost < costs[nextNode] :
                costs[nextNode] = nextCost  # コストを更新
                heapq.heappush(q,(nextCost,nextNode))

if costs[endNode * 3] < 0 :
    print(-1)
else :
    print(costs[endNode * 3] // 3)

Submission status: Wrong Answer

Solution code:
import sys
n,m = map(int,sys.stdin.readline().split())
vertices = [[] for _ in range(n+1)]
jumpValue = [[-1,-1,-1] for _ in range(n+1)]
visited = set()
queue = []
temp = []
def bfs(arr,jump):
    temp = []
    for node in arr:
        if jumpValue[node][(jump+1)%3]==-1:
            queue.append([node,jump+1])
        temp = temp+vertices[node]
    return temp
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    vertices[a].append(b)
s,t = map(int,sys.stdin.readline().split())
visited.add(s)
queue.append([s,0])
done =set()
while(len(queue)>0 ):
    next=queue.pop(-1)
    if jumpValue[next[0]][next[1]%3] == -1:
        jumpValue[next[0]][next[1]%3] = next[1]
        bfs(vertices[next[0]], next[1])
print(max(jumpValue[t][0]//3,-1))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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

if 0 == M:
	print(-1)
	exit()

s, t = S - 1, T - 1

graph = [[] for _ in range(N)]
for u, v in UV:
	graph[u - 1] += [v - 1]

INF = 10 ** 12
cost = [[INF, INF, INF] for _ in range(N)]
def print_cost(cost):
	for line in cost:
		for cell in line:
			print("  INF" if cell == INF else " {:4d}".format(cell), end="")
		print()
	print()

def dfs(graph, cost, c, d):
	if cost[c][d % 3] <= d:
		return
	cost[c][d % 3] = d
	print_cost(cost)
	for n in graph[c]:
		dfs(graph, cost, n, d + 1)

dfs(graph, cost, s, 0)

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

Submission status: Wrong Answer

Solution code:
N,M= map(int,input().split())
uv = [0]*M
for i in range(M):
    uv[i]=list(map(int, input().split()))
S,T= map(int,input().split())

# ans = [10**5]
graph = [[] for j in range(N)]
for i in range(M):
    graph[uv[i][0]-1].append([uv[i][0]-1,uv[i][1]-1])



#graphにはインデックス

next_stack = []
visit = [[0 for i in range(3)] for j in range(N)]
candidate = []
trace_count = 0
now_pos = [S-1,0]
ans = 10**5
nextu = 0
#拡張BFS
while(1):
    print(now_pos)
    visit[now_pos[0]][now_pos[1]] += 1
    if visit[now_pos[0]][now_pos[1]]==2:
        break
    if now_pos == [T-1,0]:
        if ans > trace_count//3:
            ans = trace_count//3
    #現在のノードからいけるノードを追加する
    if now_pos[1]==2:
        nextu = 0
    else:
        nextu = now_pos[1]+1

    
    # print(graph[now_pos[0]])
    for node in graph[now_pos[0]]:
        # print(node)
        next_stack.append([node[1],nextu])

    
    trace_count += 1
    if len(next_stack)==0:
        break
    now_pos = next_stack.pop(0)



if ans == 10**5:
    ans = -1
print(ans)