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())
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 = -1
nextu = 0
#拡張BFS
while(1):
    # print(visit)
    visit[now_pos[0]][now_pos[1]] += 1
    if visit[now_pos[0]][now_pos[1]]==2:
        break
    if now_pos == [T-1,0]:
        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)


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


def main(): 
    # ダイクストラ法を用いて回答する。
    N, M = LI()
    graph = []
    from collections import defaultdict
    reversed_graph_dict = defaultdict(list)
    for _ in range(M):
        u, v = LI()
        graph.append([u,v])
        reversed_graph_dict[v].append(u)
    S, T = LI()

    # 三段先のグラフを先に作っておく。
    three_steps_dict = defaultdict(list)
    for i in range(1, N+1):
        added = set()
        first_step = reversed_graph_dict[i]
        second_step = []
        for x in first_step:
            second_step += reversed_graph_dict[x]
        third_step = []
        for x in set(second_step):
            for y in reversed_graph_dict[x]:
                if (i,y) not in added:
                    three_steps_dict[i] += [(y, 1)]
                    added.add((i,y))

    N = N+1  # 頂点の数。one-origin の場合は頂点の数+1する。
    S = S  # 始点の番号
    T = T  # 終点の番号

    from heapq import heappop, heappush
    inf=10 ** 18
    d=[inf for i in range(N)]
    d[S]=0  # 始点のコストを 0 とする。頂点は zero origin とする。
    prev=[None]*N

    # 辺のリストを、連結リストに変換する。始点: (終点, 辺のコスト) の list
    p=three_steps_dict

    # ここからダイクストラ法の本体。「重みつき幅優先探索」って感じ。
    q=[(d[S], S)]  # heap queue。中身は (頂点のコスト, 頂点の番号)。始点をまずは格納する。
    while q:
        # print(q,d,prev)
        du, u = heappop(q)  # queue に入っている、コスト最小の頂点を取得する。
                            # この時点で u の最小値は du に確定するので、if u == T: break してもよい。
        if d[u]<du: continue  # 点 u のコストがすでに取得したコストよりも少なかったら、更新せずに次へ。
        for v,weight in p.get(u,[]):  # u から伸びる全辺について、
            alt=du+weight
            if d[v]>alt:  # u から v に行ったほうがいまの v のコストよりも低いなら、v のコストを更新して queue へ。
                d[v]=alt
                prev[v]=u  # その点までの最短経路を覚えておく（1つ前の頂点を覚えておく）。
                heappush(q, (alt,v))

    # 終点までの距離を表示する。
    print(d[T])



main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M=map(int,input().split())
uv=[]
for _ in range(M):
    uv.append([int(i) for i in input().split()])
S,T=map(int,input().split())

uv.sort()

childlist=[]
for _ in range(N):
    childlist.append([])

for i in range(M):
    p=uv[i][0]-1
    q=uv[i][1]-1
    childlist[p].append(q)
    childlist[q].append(p)

q=deque([S-1])

MAP=[-1]*N
MAP[S-1]=0

step=0
while q:
    x = q.popleft()
    for next in childlist[x]:
        MAP[next]=MAP[x]+1
        if next==T-1 and MAP[next]%3==0:
            print((step+1)//3)
            break
        q.append(next)
    step+=1
    if step//3 > N:
        print(-1)
        break

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M=map(int,input().split())
uv=[]
for _ in range(M):
    uv.append([int(i) for i in input().split()])
S,T=map(int,input().split())

uv.sort()

childlist=[]
for _ in range(N):
    childlist.append([])

for i in range(M):
    p=uv[i][0]-1
    childlist[p].append(uv[i][1]-1)

q=deque([S-1])

MAP=[-1]*N
MAP[S-1]=0

step=0
while q:
    x = q.popleft()
    for next in childlist[x]:
        MAP[next]=MAP[x]+1
        if next==T-1 and MAP[next]%3==0:
            print((step+1)//3)
            exit()
        q.append(next)
    step+=1
    if step//3 > N:
        print(-1)
        break

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M=map(int,input().split())
uv=[]
for _ in range(M):
    uv.append([int(i) for i in input().split()])
S,T=map(int,input().split())

uv.sort()

childlist=[]
for _ in range(N):
    childlist.append([])

for i in range(M):
    p=uv[i][0]-1
    childlist[p].append(uv[i][1]-1)

q=deque([S-1])

MAP=[-1]*N
MAP[S-1]=0

step=0
while q:
    x = q.popleft()
    for next in childlist[x]:
        MAP[next]=MAP[x]+1
        if next==T-1 and MAP[next]%3==0:
            print((step+1)//3)
            break
        q.append(next)
        print(MAP)
    step+=1
    if step//3 > N:
        print(-1)
        break

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M=map(int,input().split())
uv=[]
for _ in range(M):
    uv.append([int(i) for i in input().split()])
S,T=map(int,input().split())

childlist=[]
for _ in range(N):
    childlist.append([])

for i in range(M):
    p=uv[i][0]-1
    childlist[p].append(uv[i][1]-1)

q=deque([S-1])

MAP=[-1]*N
MAP[S-1]=0

step=0
while q:
    x = q.popleft()
    for next in childlist[x]:
        MAP[next]=MAP[x]+1
        if next==T-1 and MAP[next]%3==0:
            print((step+1)//3)
            break
        q.append(next)
        print(MAP)
    step+=1
    if step//3 > N:
        print(-1)
        break

Submission status: Wrong Answer

Solution code:
import collections
N, M = [int(_) for _ in input().split()]
UV = [[int(_) for _ in input().split()] for _ in range(M)]
s, t = [int(_) for _ in input().split()]
v = [[0] * (N + 1) for _ in range(3)]
v[0][s] = 0
G = collections.defaultdict(set)
for U, V in UV:
    G[U].add(V)
Q = collections.deque([[0, s]])
while Q:
    d, i0 = Q.popleft()
    d += 1
    for i1 in G[i0]:
        if not v[1][i1]:
            v[1][i1] = 1
            for i2 in G[i1]:
                if not v[2][i2]:
                    v[2][i2] = 1
                    for i3 in G[i2]:
                        if i3 == t:
                            print(d)
                            exit()
                        elif not v[0][i3]:
                            v[0][i2] = 1
                            Q += [[d, i3]]
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import*
n,m,*t=map(int,open(0).read().split())
*w,s,t=[t-1for t in t]
e=[[]for _ in range(n)]
for u,v in zip(w[::2],w[1::2]):
  e[u].append(v)
INF=10**18
f=[[INF]*3for _ in range(n)]
f[s][0]=0
q=deque([(s,0)])
while q:
  v,m=q.popleft()
  if v==t and m==2:
    print(f[v][2])
    break
  for w in e[v]:
    if f[w][-~m%3]<INF:continue
    f[w][-~m%3]=f[v][m]+1
    q.append((w,-~m%3))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
def dfs():
  while len(q) > 0:
    p = q.pop()
    for e in g[p]:
      if d[e] < 0:
        q.append(e)
        d[e] = d[p] + 1
        f[e] = p
      elif d[e] > d[p] + 1:
        d[e] = d[p] + 1
        f[e] = p       

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

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

d = [-1] * (3 * (n+1))
f = [-1] * (3 * (n+1))
d[3*s] = 0
f[3*s] = 0
q = [3*s]
dfs()
c = 0
if f[3*t] == -1:
  print(-1)
  exit()

t = 3 * t
while f[t] > 0:
  c += 1
  t = f[t]
  
print(c // 3)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
node_dic = {}

for i in range(3 * N):
    node_dic[i] = []

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

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

ans_array = [-1] * (3 * N)
use_array = [0] * (3 * N)

edge_queue = deque()
ans_array[(S-1)*3] = 0
use_array[(S-1)*3] = 1
edge_queue.append((S-1)*3)
while(len(edge_queue)):
    edge = edge_queue.pop()
    value = ans_array[edge]
    for e in node_dic[edge]:
        if not use_array[e]:
            edge_queue.append(e)
            ans_array[e] = value + 1
            use_array[e] = 1

print(ans_array[(T-1)*3]//3)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
node_dic = {}

for i in range(3 * N):
    node_dic[i] = []

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

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

ans_array = [-1] * (3 * N)

edge_queue = deque()
ans_array[(S-1)*3] = 0
edge_queue.append((S-1)*3)
while(len(edge_queue)):
    edge = edge_queue.pop()
    value = ans_array[edge]
    for e in node_dic[edge]:
        if ans_array[e] == -1:
            edge_queue.append(e)
            ans_array[e] = value + 1

print(ans_array[(T-1)*3]//3)

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(g, s, t):
    q = deque()
    q.append(s)
    visited = [False] * len(g)
    c = 0
    while q:
        v_c = q.popleft()
        for vt in g[v_c]:
            if not visited[vt]:
                q.append(vt)
        if c % 3 == 0 and c:
            if visited[v_c]:
                return -1
            if v_c == t:
                return c // 3
            else:
                visited[v_c] = True
        c += 1
    return -1


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

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(g, s, t):
    q = deque()
    q.append(s)
    visited = [False] * len(g)
    c = 0
    while q:
        v_c = q.popleft()
        for vt in g[v_c]:
            if not visited[vt]:
                q.append(vt)
        if c % 3 == 0 and c:
            if v_c == t:
                return c // 3
            else:
                visited[v_c] = True
        c += 1
    return -1


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

Submission status: Wrong Answer

Solution code:
from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    tmp=[0]*(n+1)
    ans=1
    for i in range(n*3):
        x=w.pop()
        if x==0:
            ans+=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if tmp[j]==0 or tmp[j]%3!=ans%3:
                    w.appendleft(j)
                    tmp[j]=ans
        if ans%3==0 and tmp[t]==ans:
            print(ans//3)
            exit()
    print(-1)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

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

from queue import *
N, M = map(int, input().split())
es = [[[] for j in range(3)] for i in range(N)]
for i in range(M):
    u, v = map(lambda x : int(x) - 1, input().split())
    es[u][0].append((v, 1))
    es[u][1].append((v, 2))
    es[u][2].append((v, 0))
S, T = map(lambda x : int(x) - 1, input().split())
dist = [[-1] * 3 for i in range(N)]
dist[S][0] = 0
q = Queue()
q.put((S, 0))
while not q.empty():
    v, s = q.get()
    if v == T:
        break
    for u, _s in es[v][s]:
        if dist[u][_s] == -1:
            dist[u][_s] = dist[v][s] + 1
            q.put((u, _s))
print(dist[T][2])

Submission status: Wrong Answer

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

from queue import *
N, M = map(int, input().split())
es = [[[] for j in range(3)] for i in range(N)]
for i in range(M):
    u, v = map(lambda x : int(x) - 1, input().split())
    es[u][0].append((v, 1))
    es[u][1].append((v, 2))
    es[u][2].append((v, 0))
S, T = map(lambda x : int(x) - 1, input().split())
dist = [[-1] * 3 for i in range(N)]
dist[S][0] = 0
q = Queue()
q.put((S, 0))
while q:
    v, s = q.get()
    if v == T:
        break
    for u, _s in es[v][s]:
        if dist[u][_s] == -1:
            dist[u][_s] = dist[v][s] + 1
            q.put((u, _s))
print(dist[T][2])

Submission status: Wrong Answer

Solution code:
from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    #w={s}
    w=deque([0,s])
    tmp=[0]*(n+1)
    n*=3
    ans=0
    while n:
        n-=1
        ans+=1
        while 1:
            x=w.pop()
            if x==0:
                w.appendleft(0)
                break
            if x in d:
                for j in d[x]:
                    if tmp[j]%3!=ans%3:
                        w.appendleft(j)
                        tmp[j]=ans
        if ans%3==0 and tmp[t]==ans:
            print(ans//3)
            exit()
    print(-1)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)

S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, N+1):
    vs = []
    for u in c:
      m[u][count %3] = True
      vs += a[u]
    c = []
    for v in vs:
      if (v == T and count %3 ==0):
        return count//3
      if not(m[v][(count+1) %3]):
        c.append(v)
  return -1
print(main())

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)
print(a)

S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, N+1):
    vs = []
    for u in c:
      m[u][count %3] = True
      vs += a[u]
    c = []
    for v in vs:
      if (v == T and count %3 ==0):
        return count//3
      if not(m[v][(count+1) %3]):
        c.append(v)
  return -1
print(main())

Submission status: Wrong Answer

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

from heapq import *
N, M = map(int, input().split())
es = [[[] for j in range(3)] for i in range(N)]
for i in range(M):
    u, v = map(lambda x : int(x) - 1, input().split())
    es[u][0].append((v, 1))
    es[u][1].append((v, 2))
    es[u][2].append((v, 0))
S, T = map(lambda x : int(x) - 1, input().split())
dist = [[-1] * 3 for i in range(N)]
dist[S][0] = 0
q = [(0, S, 0)]
visit = [[1] * 3 for i in range(N)]
visit[S][0] = 0
while q:
    d, v, s = heappop(q)
    for u, _s in es[v][s]:
        if dist[u][_s] == -1:
            dist[u][_s] = d+1
            visit[u][_s] = 0
            heappush(q, (d+1, u, _s))
print(dist[T][2])

Submission status: Wrong Answer

Solution code:
from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    tmp=[0]*(n+1)
    n*=2
    ans=0
    while n:
        n-=1
        ans+=1
        while 1:
            x=w.pop()
            if x==0:
                w.appendleft(0)
                break
            if x in d:
                for j in d[x]:
                    if tmp[j]!=ans:
                        w.appendleft(j)
                        tmp[j]=ans
        if ans%3==0 and tmp[t]==ans:
            print(ans//3)
            exit()
    print(-1)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

connect = [[] for _ in range(3*N)]

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

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

def bfs(s):
    q = deque()
    q.append(s)
    d = [-1 for _ in range(3*N)]
    d[s]
    
    while q:
        v = q.popleft()
        if v == T:
            return d[v]
    
        for u in connect[v]:
            if d[u] == -1:
                q.append(u)
                d[u] = d[v]+1
                
    return -1

ans =  bfs(S)

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

Submission status: Wrong Answer

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

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

dist = [-1] * (3*N)
dist[S] = 0
que = deque([S])
while len(que) != 0:
    q = que.pop()
    cost = dist[q]
    for v in graph[q]:
        if dist[v] == -1:
            dist[v] = cost + 1
            que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

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

dist = [-1] * (3*N)
que = [S]
dist[S] = 0
while len(que) != 0:
    q = que.pop()
    cost = dist[q]
    for v in graph[q]:
        if dist[v] == -1:
            dist[v] = cost + 1
            que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 2
dist = [-1] * cnt

que = [S]
dist[S] = 0
while len(que) != 0:
    q = que.pop()
    cost = dist[q]
    for v in graph[q]:
        if dist[v] == -1:
            dist[v] = cost + 1
            que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 2
dist = [float("inf")] * cnt

que = [S]
dist[S] = 0
while len(que) != 0:
    q = que.pop()
    cost = dist[q]
    for v in graph[q]:
        if dist[v] == float("inf"):
            dist[v] = cost + 1
            que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 2
dist = [float("inf")] * cnt

que = [S]
dist[S] = 0
while len(que) != 0:
    q = que.pop()
    cost = dist[q]
    for v in graph[q]:
        if dist[v] == float("inf"):
            dist[v] = cost + 1
            que.append(v)
if dist[T] != float("inf") and dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 2
dist = [float("inf")] * cnt

que = [S]
dist[S] = 0
while len(que) != 0:
    q = que.pop()
    for v in graph[q]:
        if dist[v] == float("inf"):
            dist[v] = dist[q] + 1
            que.append(v)
if dist[T] != float("inf") and dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 2
dist = [float("inf")] * cnt

que = [S]
dist[S] = 0
visited = set()
visited.add(S)
while len(que) != 0:
    q = que.pop()

    for v in graph[q]:
        if v in visited:
            continue
        dist[v] = min(dist[v], dist[q] + 1)
        que.append(v)
        visited.add(v)
if dist[T] != float("inf") and dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * 10 ** 5 + 10
dist = [float("inf")] * cnt

que = [S]
dist[S] = 0
visited = set()
visited.add(S)
while len(que) != 0:
    q = que.pop()

    for v in graph[q]:
        if v in visited:
            continue
        dist[v] = min(dist[v], dist[q] + 1)
        que.append(v)
        visited.add(v)
if dist[T] != float("inf") and dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * 10 ** 5 + 10
dist = [float("inf")] * cnt

que = [S]
dist[S] = 0
visited = set()
while len(que) != 0:
    q = que.pop()
    if q in visited:
        continue
    else:
        visited.add(q)
    for v in graph[q]:
        if v in visited:
            continue

        dist[v] = min(dist[v], dist[q] + 1)
        que.append(v)
if dist[T] != float("inf") and dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 4 * 10 ** 5
dist = [float("inf")] * cnt

que = [S]
dist[S] = 0
visited = set()
while len(que) != 0:
    q = que.pop()
    if q in visited:
        continue
    else:
        visited.add(q)
    for v in graph[q]:
        if v in visited:
            continue

        dist[v] = min(dist[v], dist[q] + 1)
        que.append(v)
if dist[T] != float("inf"):
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 4 * 10 ** 5
dist = [float("inf")] * cnt


que = [S]
dist[S] = 0
visited = set()
while len(que) != 0:
    q = que.pop()
    if q in visited:
        continue
    else:
        visited.add(q)
    for v in graph[q]:
        if dist[v] > dist[q] + 1 and v not in visited:
            dist[v] = dist[q] + 1
            que.append(v)
if dist[T] != float("inf"):
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def main():
	N, M = map(int, input().split())
	mat = [[] for _ in range(3*N)]
	for _ in range(M):
		u, v = map(int, input().split())
		mat[u-1].append([N+v-1, 1])
		mat[N+u-1].append([2*N+v-1, 1])
		mat[2*N+u-1].append([v-1, 1])

	S, T = map(int, input().split())
	queue = list(mat[S-1])
	visited = [False]*(3*N)
	visited[S-1] = True
	while queue:
		pos, d = queue.pop()
		if pos == T-1:
			print(d//3)
			return
		visited[pos] = True
		next_positions = mat[pos]
		for next_pos, next_d in next_positions:
			if visited[next_pos]:
				continue
			queue.append([next_pos, d+next_d])
	print(-1)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
def main():
	N, M = map(int, input().split())
	INF = 2**30-1
	mat = [[] for _ in range(3*N)]
	for _ in range(M):
		u, v = map(int, input().split())
		mat[u-1].append([N+v-1, 1])
		mat[N+u-1].append([2*N+v-1, 1])
		mat[2*N+u-1].append([v-1, 1])

	S, T = map(int, input().split())
	queue = list(mat[S-1])
	cost = [INF]*(3*N)
	cost[S-1] = 0
	while queue:
		pos, d = queue.pop()
		if pos == T-1:
			print(d//3)
			return
		cost[pos] = d
		next_positions = mat[pos]
		for next_pos, next_d in next_positions:
			if cost[next_pos] < d+1:
				continue
			queue.append([next_pos, d+next_d])
	print(-1)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 4 * 10 ** 5
dist = [float("inf")] * cnt


que = [S]
dist[S] = 0
visited = set()
while len(que) != 0:
    q = que.pop()
    if q in visited:
        continue
    else:
        visited.add(q)
    for v in graph[q]:
        if dist[v] > dist[q] + 1:
            dist[v] = dist[q] + 1
            que.append(v)
if dist[T] != float("inf"):
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 4
dist = [float("inf")] * cnt


que = [S]
dist[S] = 0
visited = set()
while len(que) != 0:
    q = que.pop()
    if q in visited:
        continue
    else:
        visited.add(q)
    for v in graph[q]:
        if dist[v] > dist[q] + 1:
            dist[v] = dist[q] + 1
            que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 4
dist = [float("inf")] * cnt


que = [S]
dist[S] = 0
visited = [False] * cnt
visited[S] = True
while len(que) != 0:
    q = que.pop()
    for v in graph[q]:
        if dist[v] == float("inf"):
            dist[v] = dist[q] + 1
            visited[v] = True
            que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Wrong Answer

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

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 4
dist = [float("inf")] * cnt


que = [S]
dist[S] = 0
visited = [False] * cnt
visited[S] = True
while len(que) != 0:
    q = que.pop()
    for v in graph[q]:
        if visited[v]:
            continue
        if dist[v] == float("inf"):
            dist[v] = dist[q] + 1
            visited[v] = True
            que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)