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:
from collections import defaultdict, deque


def bfs(V, s, t):
    q = deque([(0, s)])
    used = set()
    
    while q:
        dist, a = q.popleft()
        used.add(a)
        if a == t:
            break
        for b in V[a]:
            if b in used: continue
            q.append((dist+1, b))
    return dist


if __name__ == "__main__":
    V = defaultdict(list)
    N, M = map(int, input().split())
    for _ in range(M):
        u, v = map(int, input().split())
        V[(u, 0)].append((v, 1))
        V[(u, 1)].append((v, 2))
        V[(u, 2)].append((v, 0))

    S, T = map(int, input().split())
    dist = bfs(V, (S, 0), (T, 0))
    print(-1 if dist%3 or dist==0 else dist//3)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

V = defaultdict(list)
N, M = map(int, input().split())
for _ in range(M):
    u, v = map(int, input().split())
    V[u].append(v)

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


def dfs(S, T):
    q = [(0, S)]
    used = [False] * (N+1)
    while q:
        dist, p = q.pop()
        used[p] = True
        if p==T:break
        for i in V[p]:
            if used[i]:continue
            q.append((dist+1, i))
    return dist


st, ts = dfs(S, T), dfs(T, S)
if st==0 and ts==0:
    print(-1)
elif (st+ts)%3==0 and st%3:
    print(-1)
else:
    p = 0
    while 1:
        v = (st+ts)*p+st
        if v%3==0:
            print(v//3)
            break
        p += 1

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N*3+5)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v+N+1)
        adj[u+N+1].append(v+2*N+2)
        adj[u+2*N+2].append(v)

    s, t = map(int, input().split())
    que = deque()
    que.append(s)
    seen = [-1] * (N*3+5)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                que.append(u)

    if seen[t] == -1:
        print(-1)
    else:
        print(seen[t] // 3)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

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

    s, t = map(int, input().split())
    que = deque()
    que.append(s)
    seen = [-1] * (N*3+1)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                que.append(u)

    if seen[t] == -1:
        print(-1)
    else:
        print(seen[t] // 3)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

graphs = [[] for _ in range( 3 * N)]
dists = [-1 for _ in range( 3 * N)]
for uv in UVm:
  u = uv[0] - 1
  v = uv[1] - 1
  graphs[u].append(v + N)
  graphs[u + N].append( v + 2 * N)
  graphs[u + 2 * N].append(v)
  
from collections import deque
que = deque()
que.append(S - 1)
dists[S - 1] = 0
while len(que) > 0:
  nex = que.pop()
  for edge in graphs[nex]:
    if dists[edge] != -1:
      continue
    que.append(edge)
    dists[edge] = dists[nex] + 1
print(dists[T-1] // 3)

Submission status: Wrong Answer

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

graphs = [[] for _ in range( 3 * N)]
checked = [False for _ in range( 3 * N)]
dists = [-1 for _ in range( 3 * N)]
for uv in UVm:
  u = uv[0] - 1
  v = uv[1] - 1
  graphs[u].append(v + N)
  graphs[u + N].append( v + 2 * N)
  graphs[u + 2 * N].append(v)
  
from collections import deque
que = deque()
#que.append((S - 1, 0))
que.append(S - 1)
dists[S - 1] = 0
find = False
while len(que) > 0:
  nex = que.pop()
  checked[nex] = True
  for edge in graphs[nex]:
    if not checked[edge]:
      que.append(edge)
      dists[edge] = dists[nex] + 1
print(dists[T-1] // 3)

Submission status: Wrong Answer

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

graphs = [[] for _ in range( 3 * N)]
checked = [False for _ in range( 3 * N)]
dists = [-1 for _ in range( 3 * N)]
for uv in UVm:
  u = uv[0] - 1
  v = uv[1] - 1
  graphs[u].append(v + N)
  graphs[u + N].append( v + 2 * N)
  graphs[u + 2 * N].append(v)
  
from collections import deque
que = deque()
#que.append((S - 1, 0))
que.append(S - 1)
dists[S - 1] = 0
find = False
while len(que) > 0:
  nex = que.pop()
  if nex == T - 1:
    find =True
    break
  checked[nex] = True
  for edge in graphs[nex]:
    if not checked[edge]:
      que.append(edge)
      dists[edge] = dists[nex] + 1
print(dists[T-1] // 3)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque

N,M = list(map(int,stdin.readline().split()))
Cs = [tuple(map(int,stdin.readline().split())) for _ in range(M)]
S,T = list(map(int,stdin.readline().split()))

INF = 10 ** 15
# visit = [False] * ( (N + 1) * 3 )
dist  = [-1] * ( (N) * 3 + 1 )
graph_connection = defaultdict(lambda :[])
graph_cost = defaultdict(lambda :defaultdict(lambda :INF))
#
# def dfs(v,dist_before):
#
#     dist[v] = dist_before + 1
#     next_vertexs = graph_connection[v]
#     for next_v  in next_vertexs :
#         if dist[next_v] == -1:
#             dfs(next_v,dist[v])
#     return 0
#

for cost in  Cs:
    a,b= cost
    for i in range(0,3):
        from_v = a + (i) * N
        to_v = b + (i + 1) % 3 * N
        graph_connection[from_v].append(to_v )

        # from_v = b + (i) * N
        # to_v = a + (i + 1) % 3 * N
        # graph_connection[from_v].append(to_v )

# dist[S] = 0


que = deque()
#(from_v,to_v)
que.append((S,S))

while len(que) != 0:
    from_v, to_v = que.popleft()
    dist[to_v] = dist[from_v] + 1
    for next_v in graph_connection[to_v]:
        if dist[next_v] == -1:
            que.appendleft((to_v,next_v))
if dist[T] < 0:
    print(dist[T] )
else:
    print(dist[T]//3)

Submission status: Wrong Answer

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


graphs = [[] for _ in range( 3 * N)]
checked = [False for _ in range( 3 * N)]
for uv in UVm:
  u = uv[0] - 1
  v = uv[1] - 1
  graphs[u].append(v + N)
  graphs[u + N].append( v + 2 * N)
  graphs[u + 2 * N].append(v)
  
from collections import deque
que = deque()
que.append((S - 1, 0))
find = False
while len(que) > 0:
  nex, count = que.pop()
  if nex == T - 1:
    find =True
    break
  checked[nex] = True
  for edge in graphs[nex]:
    if not checked[edge]:
      que.append((edge, count + 1))
if find:
  print(count // 3)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
#### 132_E

import queue
import sys
sys.setrecursionlimit(300000)
 
n,m=map(int,input().split())

edges=[[] for i in range(3*n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    edges[u].append(u+n)
    edges[u+n].append(u+2*n)
    edges[u+2*n].append(v)
    
s,t=map(int,input().split())
s,t=s-1,t-1
    
def bfs(s,t):
    que=queue.Queue()
    que.put(s)
    d[s]=0
    visit[s]=True
    while not que.empty():
        q=que.get()
        if q==t:
            return d[t]
        for z in edges[q]:
            if visit[z]==False:
                que.put(z)
                d[z]=d[q]+1
                visit[z]=True
    return d[t]
                
visit=[False for _ in range(3*n)]
d=[-1 for _ in range(3*n)]

ans=bfs(s,t)
print(ans//3 if ans%3==0 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
path=[[] for i in range(n*3+3)]
seen=[[False] for i in range(n*3+3)]
for i in range(m):
  u,v=map(int,input().split())
  path[3*(u-1)].append(3*(v-1)+1)
  path[3*(u-1)+1].append(3*(v-1)+2)
  path[3*(u-1)+2].append(3*(v-1))
s,t=map(int,input().split())
s-=1
t-=1
q=deque()
q.append((s*3,0))
seen[s*3]=True
while q:
  x,cnt=q.popleft()
  seen[x]=True
  for i in path[x]:
    if not seen[i]:
      continue
    elif i//3==t:
      print(cnt*3-1)
      exit()
    q.append((i,cnt+1))
print(-1)

Submission status: Wrong Answer

Solution code:
import queue

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

g = [[] * 1 for i in range(n*3)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a * 3 + 0].append(b * 3 + 1)
    g[a * 3 + 1].append(b * 3 + 2)
    g[a * 3 + 2].append(b * 3 + 0)


s, t = map(int, input().split())
s -= 1
t -= 1
d = [-1 for i in range(n*3)]
q = queue.Queue()
q.put(s)
d[s*3+0] = 0
while not q.empty():
    v = q.get()
    for to in g[v]:
        if d[to] == -1:
            d[to] = d[v] + 1
            q.put(to)

if d[t*3+0] == -1:
    print(-1)
else:
    print(d[t*3+0] // 3)

Submission status: Wrong Answer

Solution code:
n,m= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
s,t= map(int, input().split())

b= [[] for i in range(3*n)]
# 3で割り切れる数がもとの点
for i in range(m):
    b[3*(a[i][0]-1)].append(3*(a[i][1]-1)+1)
    b[3*(a[i][0]-1)+1].append(3*(a[i][1]-1)+2)
    b[3*(a[i][0]-1)+2].append(3*(a[i][1]-1))

import collections
from collections import deque
def tree(s,g):

    INF=-10**9
    dis = [INF for i in range(3*n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1

        return dis[g]
    return bfs()

ans=tree(s-1,3*(t-1))
if ans==-10**9:
    print(-1)
else:
    print(ans//3)

Submission status: Wrong Answer

Solution code:
n,m= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
s,t= map(int, input().split())

b= [[] for i in range(3*n)]
# 3で割り切れる数がもとの点
for i in range(m):
    b[3*(a[i][0]-1)].append(3*(a[i][1]-1)+1)
    b[3*(a[i][0]-1)+1].append(3*(a[i][1]-1)+2)
    b[3*(a[i][0]-1)+2].append(3*(a[i][1]-1))

import collections
from collections import deque
def tree(s,g):

    INF=-10**9
    dis = [INF for i in range(3*n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()
            if x==g:
                break
            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1

        return dis[g]
    return bfs()

ans=tree(s-1,3*(t-1))
if ans==-10**9:
    print(-1)
else:
    print(ans//3)

Submission status: Wrong Answer

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

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

path = [[-1] * 3 for _ in range(N + 1)]
path[S][0] = 0
node = [(S, 0)]
while node:
    s, d = node.pop()
    dist = path[s][d]

    d = (d+1) % 3
    for t in edge[s]:
        if path[t][d] != -1:
            continue
        path[t][d] = dist + 1
        node.append((t, d))


ans = path[T][0]//3
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
e_in = [set() for _ in range(N + 1)]
for _ in range(M):
    s, t = map(int, input().split())
    e_in[t].add(s)
S, T = map(int, input().split())


def bef(E):
    res = [set() for _ in range(N + 1)]
    for i, e in enumerate(E):
        for j in e:
            res[i] |= e_in[j]
    return res


two = bef(e_in)  # 2歩進むことでiに到着できるノード番号
three = bef(two)  # 3歩進むことでiに到着できるノード番号

seen = [-1] * (N + 1)

# ゴールから調べる
seen[T] = 0
node = [T]
while node:
    s = node.pop()
    d = seen[s]
    for t in three[s]:
        if seen[t] != -1:
            continue
        seen[t] = d + 1
        node.append(t)

ans = seen[S]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

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

    S,T = map(int,input().split())
    q = deque()
    go = [[False for _ in range(3)] for _ in range(N)]
    q.append((S-1,0,1))
    while q:
        now,step,d = q.pop()
        if step == 3:
            if now == T-1:
                print(d)
                exit()
            step = 0
            d += 1
        if go[now][step]:
            continue
        go[now][step] = True
        for fol in edge[now]:
            q.append((fol,step+1,d))

    print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M = map(int,input().split())
    edge =[[[] for _ in range(3)] for _ in range(N)]
    for _ in range(M):
        u,v = map(int,input().split())
        for i in range(3):
            edge[u-1][i].append((v-1,(i+1)%3))

    S,T = map(int,input().split())
    go =[[0 for _ in range(3)] for _ in range(N)]
    q = deque([(S-1,0)])
    while q:
        now,rest = q.pop()
        for fol,fr in edge[now][rest]:
            if go[fol][fr] == 0:
                go[fol][fr] = go[now][rest]+1
                q.append((fol,fr))
                
    if go[T-1][0] != 0 and go[T-1][0]%3 == 0:
        print(go[T-1][0]//3)
        exit()
    
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)

s, t = map(int, sys.stdin.readline().split())

def main():
    dist = [inf] * (n + 1)
    can_reach = [[False] * 3 for _ in range(n + 1)]
    stack = [(0, s)]
    can_reach[s][0] = True
    while stack:
        d, x = stack.pop()
        if d % 3 == 0:
            dist[x] = min(dist[x], d // 3)
        d += 1
        for y in g[x]:
            if not can_reach[y][d%3]:
                can_reach[y][d%3] = True
                stack.append((d, y))

    return dist[t] if dist[t] != inf else -1

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)

s, t = map(int, sys.stdin.readline().split())

def main():
    dist = [inf] * (n + 1)
    can_reach = [[False] * 3 for _ in range(n + 1)]
    stack = [(0, s)]
    can_reach[s][0] = True
    while stack:
        d, x = stack.pop()
        if d % 3 == 0:
            dist[x] = d // 3
        d += 1
        for y in g[x]:
            if not can_reach[y][d%3]:
                can_reach[y][d%3] = True
                stack.append((d, y))

    return dist[t] if dist[t] != inf else -1

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m = inpm()
    g = [[] for _ in range(n)]
    for _ in range(m):
        u,v = inpm()
        u -= 1
        v -= 1
        g[u].append(v)
    s,t = inpm()
    s -= 1
    t -= 1
    que = deque()
    que.append(s)
    visited1 = [0 for _ in range(n)]
    visited1[s] = 1
    visited2 = [0 for _ in range(n)]
    visited3 = [0 for _ in range(n)]
    cnt = 1
    while True:
        tank1 = deque()
        tank2 = deque()
        tank3 = deque()
        key = 1
        while que:
            start = que.pop()
            for go in g[start]:
                if not visited1[go]:
                    key = 0
                    visited1[go] = 1
                    tank1.append(go)
        while tank1:
            start = tank1.pop()
            for go in g[start]:
                if not visited2[go]:
                    visited2[go] = 1
                    tank2.append(go)
        while tank2:
            start = tank2.pop()
            for go in g[start]:
                if not visited3[go]:
                    visited3[go] = 1
                    tank3.append(go)
                if go == t:
                    print(cnt)
                    return
        que = tank3
        cnt += 1
        if not que:
            break
    print(-1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(3*N)]
    for i in range(M):
        u,v=map(lambda x: int(x)-1,input().split())
        for k in range(3):
            edge[u*3+k].append(v*3+(k+1)%3)
    S,T=map(lambda x:int(x)-1,input().split())
    que=deque()
    que.append(S)
    c=[-1]*(3*N)
    c[S*3]=0
    while que:
        v=que.popleft()
        for nv in edge[v]:
            if c[nv]==-1:
                c[nv]=c[v]+1
                que.append(nv)
    print(c[T*3]//3 if c[T*3]!=-1 else -1)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(3*N)]
    for i in range(M):
        u,v=map(lambda x: int(x)-1,input().split())
        for k in range(3):
            edge[u*3+k].append(v*3+(k+1)%3)
    S,T=map(lambda x:int(x)-1,input().split())
    que=deque()
    que.append(S)
    c=[-1]*(3*N)
    c[0]=0
    while que:
        v=que.popleft()
        for nv in edge[v]:
            if c[nv]==-1:
                c[nv]=c[v]+1
                que.append(nv)
    print(c[T*3]//3 if c[T*3]!=-1 else -1)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(3*N)]
    for i in range(M):
        u,v=map(lambda x: int(x)-1,input().split())
        for k in range(3):
            edge[u*3+k].append(v*3+(k+1)%3)
    S,T=map(lambda x:int(x)-1,input().split())
    que=deque()
    que.append(S)
    c=[INF]*(3*N)
    c[0]=0
    while que:
        v=que.popleft()
        for nv in edge[v]:
            if c[nv]==INF:
                c[nv]=c[v]+1
                que.append(nv)
    print(c[T*3]//3 if c[T*3]!=INF else -1)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
graph=[[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
s,t=map(int,input().split())
visited=[[-1,-1,-1] for i in range(n+1)]
que=deque([(s,0,0)])
while que:
  x,mod,cnt=que.popleft()
  visited[x][mod]=cnt
  if x==t and mod==0:
    break
  for y in graph[x]:
    if visited[y][(mod+1)%3]==-1:
      que.append((y,(mod+1)%3,cnt+1))
print(visited[t][0])

Submission status: Wrong Answer

Solution code:
class Graph(): #directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]-1].append(e[1]-1)
            self.deg[e[1]-1] += 1

import sys
input = sys.stdin.readline

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

g = Graph(N,edge)

stack = [S]
reachable = [-1 for _ in range(N)]
reachable[S] = 0

while stack:
    node = stack.pop()
    dist = [-1 for _ in range(N)]
    dist[node] = 0
    stack_ = [node]
    
    while stack_:
         node_ = stack_.pop()
         for adj in g.graph[node_]:
             dist[adj] = dist[node_]+1
             if dist[adj] < 3:
                 stack_.append(adj)
             if dist[adj] == 3 and reachable[adj] == -1:
                 reachable[adj] = reachable[node]+1
                 stack.append(adj)
                 
print(reachable[T])

Submission status: Wrong Answer

Solution code:
class Graph(): #directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]-1].append(e[1]-1)
            self.deg[e[1]-1] += 1

import sys
input = sys.stdin.readline

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

g = Graph(N,edge)

stack = [S]
depth = [None for _ in range(N)]
depth[S] = 0
used = [[False]*3 for _ in range(N)]
used[S][0] = True
ans = -1

while stack:
    node = stack.pop()
    for adj in g.graph[node]:
        if used[adj][(depth[node]+1)%3]:
            continue
        depth[adj] = depth[node]+1
        if adj == T and depth[adj]%3 == 0:
            ans = depth[adj]//3
        used[adj][depth[adj]%3] = True
        stack.append(adj)

print(ans)

Submission status: Wrong Answer

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
#https://atcoder.jp/contests/abc148/tasks/abc148_f
#F - Playing Tag on Tree
"""
"""
N = gi()
M = gi()
g = [[] for i in range(3 * N)]
for i in range(M):
    u = gi() - 1
    v = gi() - 1
    for r in range(3):
        g[u].append(v + N)
        g[u + N].append(v + 2 * N)
        g[u + 2 * N].append(v)
S = gi() - 1
T = gi() - 1
d = [-1] * (3 * N)

q = deque()

d[S] = 0
q.append(S)

while len(q):
    v = q.pop()
    for u in g[v]:
        if d[u] >= 0:
            continue
        d[u] = d[v] + 1
        q.append(u)

if d[T] >= 0:
    #print(T, d[T], d[T] // 3)
    print(d[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
#https://atcoder.jp/contests/abc148/tasks/abc148_f
#F - Playing Tag on Tree
"""
"""
N = gi()
M = gi()
g = [[] for _ in range(3 * N)]
for _ in range(M):
    u = gi() - 1
    v = gi() - 1
    for r in range(3):
        g[u * 3 + r].append(v * 3 + (r + 1) % 3)
        #g[v * 3 + r].append(u * 3 + (r + 1) % 3)
S = (gi() - 1) * 3
T = (gi() - 1) * 3
d = [-1] * (3 * N)

q = deque()

d[S] = 0
q.append(S)

while len(q):
    v = q.pop()
    for u in g[v]:
        if d[u] >= 0:
            continue
        d[u] = d[v] + 1
        q.append(u)

if d[T] >= 0:
    #print(T, d[T], d[T] // 3)
    print(d[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

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

inf = 10**10
ans = [[inf, inf, inf] for i in range(N+1)]

q = [S]
ans[S][0] = 0
while q:
    now = q.pop()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[next][(i+1)%3] == inf and ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

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

Submission status: Wrong Answer

Solution code:
##########################################
inf=10**9
import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """    
    class Edge():
        #重み付き有向辺
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        #引数Vは頂点数
        self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
        self. _E = 0 #辺の数
        self._V = V #頂点数
    
    #proparty - 辺の数
    def E(self):
        return self._E
    
    #proparty - 頂点数
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        #2頂点と辺のコストを追加
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        #2頂点と辺のコスト（無向）を追加
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s):
        #始点sから頂点iまでの最短経路長のリストを返す
        
        que = [] #priority queue
        d = [inf] * self.V()
        prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
        d[s] = 0
        heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
        
        while len(que)!=0:
            #キューに格納されてある中で一番コストが小さい頂点を取り出す
            cost,v = heapq.heappop(que)
            
            #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
            if d[v] < cost:
                continue
                
            #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
            for i in range(len(self.G[v])):
                e = self.G[v][i] #vのi個目の隣接辺
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost #更新
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

        return d
########################

#グラフの頂点を3倍化

import sys
input = sys.stdin.readline

N,M=map(int,input().split())
djk = Dijkstra(N*3)

for i in range(M):
    u,v=map(int,input().split())
    u-=1
    v-=1
    djk.add(u,N+v,1)
    djk.add(N+u,2*N+v,1)
    djk.add(2*N+u,v,1)
S,T=map(int,input().split())

d = djk.shortest_path(S-1)
ans=d[2*N+T-1]
if ans==inf:
    ans=-1
print(ans)

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])
INF=10**9
ans=INF
while stack:
  node=stack.pop()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      if ans>turn:
        ans=turn
      continue
    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:
  if ans==INF:
    print(-1)
  else:
    print(ans)

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