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 deque
n, m = map(int, input().split())
adjacent_list = [[] for i in range(3*n + 3)]
for i in range(m):
    u, v = map(int, input().split())
    for j in range(1,4):
        p = j + 3 * u - 3
        q = (j % 3) + 3 * v - 2
        adjacent_list[p].append(q)
s, t = map(int, input().split())

def bfs(start, target):
    que = deque()
    finished = set()
    que.append([start, 0])
    while que:
        node, dist = que.popleft()
        if (node, dist % 3) in finished:
            continue
        if node == target:
            return dist // 3
        for i in adjacent_list[node]:
            que.append([i, dist+1])
            finished.add((node, dist % 3))
    return -1
print(bfs(s, 3*t-2))

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
adjacent_list = [[] for i in range(3*n + 3)]
for i in range(m):
    u, v = map(int, input().split())
    for j in range(1,4):
        p = j + 3 * u - 3
        q = (j % 3) + 3 * v - 2
        adjacent_list[p].append(q)
s, t = map(int, input().split())

def bfs(start, target):
    que = deque()
    finished = set()
    que.append([start, 0])
    while que:
        node, dist = que.popleft()
        if (node, dist % 3) in finished:
            continue
        else:
            finished.add((node, dist%3))
        if node == target:
            return dist // 3
        for i in adjacent_list[node]:
            que.append([i, dist+1])
    return -1
print(bfs(s, 3*t-2))

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
adjacent_list = [[] for i in range(3*n + 3)]
for i in range(m):
    u, v = map(int, input().split())
    for j in range(1,4):
        p = j + 3 * u - 3
        q = (j % 3) + 3 * v - 2
        adjacent_list[p].append(q)
s, t = map(int, input().split())

def bfs(start, target):
    que = deque()
    finished = set()
    que.append([start, 0])
    while que:
        node, dist = que.popleft()
        if node in finished:
            return -1
        else:
            finished.add(node)
        if node == target:
            return dist // 3
        for i in adjacent_list[node]:
            que.append([i, dist+1])
    return -1
print(bfs(s, 3*t-2))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())
dijkstra = Dijkstra(3 * N)
for a, b in edges:
    a, b = a - 1, b - 1
    dijkstra.add_edge(a, b, 0); dijkstra.add_edge(2*a, 2*b, 0); dijkstra.add_edge(3*a, 3*b, 1)
ans = dijkstra.distance(S - 1)[3 * (T - 1)]
print(ans if ans != float('inf') else -1)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M = getNM()
query = [getList() for i in range(M)]
S, T = getNM()

def build_tree_dis(N, edge_list):

    G = [[] for i in range(N)]

    for i in range(len(edge_list)):
        a, b = edge_list[i]
        G[a - 1].append(b - 1)

    # 葉（末端の数）
    leaves = []
    for i in range(N):
        if len(G[i]) == 1:
            leaves.append(i)

    return G

edges = build_tree_dis(N, query)

ignore = [[-1] * 20 for i in range(N)]
ignore[S - 1][0] = 0

pos = deque([[S - 1, 1]])

while len(pos) > 0:
    u, t = pos.popleft()
    for i in edges[u]:
        if ignore[i][-1] == -1:
            index = 0
            for j in range(20):
                if ignore[i][j] == -1:
                    index = j
                    break
            if i >= 1 and t == ignore[i][index - 1]:
                continue
            ignore[i][index] = t
            pos.append([i, t + 1])

for i in ignore[T - 1]:
    if i % 3 == 0:
        print(i // 3)
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M = getNM()
query = [getList() for i in range(M)]
S, T = getNM()

def build_tree_dis(N, edge_list):

    G = [[] for i in range(N)]

    for i in range(len(edge_list)):
        a, b = edge_list[i]
        G[a - 1].append([b - 1, 1])

    # 葉（末端の数）
    leaves = []
    for i in range(N):
        if len(G[i]) == 1:
            leaves.append(i)

    return G

edges = build_tree_dis(N, query)

def dij(start, goal):
    dist = [float('inf') for i in range(N)]
    dist_sec = [float('inf') for i in range(N)]
    dist[start] = 0

    pq = [(0, start)]

    # pqの先頭がgoal行きのものなら最短距離を返す
    while len(pq) > 0:
        d, now = heapq.heappop(pq)
        # 制限緩和
        if d > dist_sec[now]:
            continue
        for i in edges[now]:
            if dist[i[0]] > dist[now] + i[1]:
                dist[i[0]] = dist[now] + i[1]
                heapq.heappush(pq, (dist[i[0]], i[0]))
            # ２番目の最短路
            if dist[i[0]] < d + i[1] < dist_sec[i[0]]:
                dist_sec[i[0]] = d + i[1]
                heapq.heappush(pq, (dist_sec[i[0]], i[0]))
    return [dist[goal], dist_sec[goal]]

# 0から2への最短路は0→1→0→1
ans = dij(S - 1, T - 1)
if ans[0] % 3 == 0:
    print(ans[0] // 3)
    exit()
if ans[1] % 3 == 0:
    print(ans[1] // 3)
    exit()

cycle = ans[1] - ans[0]

if cycle % 3 == 0 or ans[1] == float('inf'):
    print(-1)
else:
    while True:
        ans[1] += cycle
        if ans[1] % 3 == 0:
            print(ans[1] // 3)
            break

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

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

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            vis[now][(step+1)%3] = cnt
            q.append((x,cnt+1))

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

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

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            vis[now][step] = cnt
            q.append((x,cnt+1))

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

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

q = queue.Queue()
vis = [-1 for _ in range(N*3+3)]
def bfs():
    while not q.empty():
        if time.time() -start_t > 1.9:
            return -3
        now,cnt = q.get()
        #print(now,T,cnt,path[now],q)
        vis[now] = cnt
        if now == T: 
            return cnt
        [q.put((x,cnt+1)) for x in path[now] if vis[x] == -1]
        #for x in path[now]:
         #   if vis[x] == -1:
          #      q.append((x,cnt+1))
    return -3
vis[S] = 1
q.put([S,0])
print(bfs()//3)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

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

q = collections.deque()
vis = [-1 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        if time.time() -start_t > 1.9:
            return -3
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = cnt
        if now == T: 
            return cnt
        [q.append((x,cnt+1)) for x in path[now] if vis[x] == -1]
        #for x in path[now]:
         #   if vis[x] == -1:
          #      q.append((x,cnt+1))
    return -3
vis[S] = 1
q.append([S,0])
print(bfs()//3)

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())
    u-=1
    v-=1
    path[u].append(v)
S,T = map(int,input().split())
S-=1
T-=1
import collections

q = collections.deque()
vis = [10**10 for _ in range(N)]
def bfs():
    for _ in range(10**6):
        if len(q) == 0: break
        now,cnt = q.popleft()
        if cnt % 3 == 1:
            vis[now] = min(cnt,vis[now])
        for x in path[now]:
            q.append([x,cnt+1])
vis[S] = 1
q.append([S,1])
bfs()
if vis[T] == 10**10: print(-1)
else: print(vis[T]//3)

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())
    u-=1
    v-=1
    path[u].append(v)
S,T = map(int,input().split())
S-=1
T-=1
import collections

q = collections.deque()
vis = [10**10 for _ in range(N)]
def bfs():
    for _ in range(10**6*3):
        if len(q) == 0: break
        now,cnt = q.popleft()
        if cnt % 3 == 1:
            vis[now] = min(cnt,vis[now])
        for x in path[now]:
            q.append([x,cnt+1])
vis[S] = 1
q.append([S,1])
bfs()
if vis[T] == 10**10: print(-1)
else: print(vis[T]//3)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque


def kenkenpa(s):
    res = []
    for v1 in e[s]:
        for v2 in e[v1]:
            for v3 in e[v2]:
                res.append(v3)
    return res


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

S, T = map(int, input().split())
q = deque([[S, 0]])
visited = [False]*(N+1)
visited[S] = True
while q:
    u, c = q.popleft()
    if u == T:
        print(c)
        break
    for v in kenkenpa(u):
        if not visited[v]:
            visited[v] = True
            q.append([v, c+1])

Submission status: Wrong Answer

Solution code:
def main():
  N, M = map(int, input().split())
  edge = [[] for _ in range(N)]
  for i in range(M):
    u, v = map(int, input().split())
    edge[u-1].append(v-1)
  d = [-1]*N
  S, T = map(int, input().split())
  d[S-1] = 0
  que = [S-1]
  count = 0
  while len(que)>0:
    now = que.pop(0)
    count += 1
    for i in edge[now]:
      for j in edge[i]:
        for k in edge[j]:
          if d[k] == -1:
            que.append(k)
            d[k] = count  
  print(d[T-1])
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int,input().split())
G = [[[] for _ in range(3)] for _ in range(n)]
for _ in range(m):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    G[u][0].append((v,1))
    G[u][1].append((v,2))
    G[u][2].append((v,0))
s,t = map(int,input().split())
s -= 1
t -= 1

dist = [[-1]*3 for _ in range(n)]
dist[0][0] = 0
Q = deque([(s,0)])
while Q:
    now,r = Q.popleft()
    for nxt,nr in G[now][r]:
        if dist[nxt][nr] != -1: continue
        dist[nxt][nr] = dist[now][r]
        if r == 2: dist[nxt][nr] += 1
        Q.append((nxt,nr))
# print(dist)
print(dist[t][0])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10000000)

n,m = map(int,input().split())
to=[[] for _ in range(n)]
dist=[[0] *3 for _ in range(100005)]
INF=10**15

for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    to[a].append(b)

sv,tv=map(int,input().split())
sv-=1;tv-=1

for i in range(n):
    for j in range(3):
        dist[i][j] =INF

q=deque()
q.append((sv,0))
dist[sv][0]=0

while q:
    v,l=q.pop()
    for u in to[v]:
        nl =(l+1)%3
        if dist[u][nl] != INF: continue
        dist[u][nl] = dist[v][l]+1
        q.append((u,nl))

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

Submission status: Wrong Answer

Solution code:


import sys
from collections import deque

sys.setrecursionlimit(10000000)
input=sys.stdin.readline

n,m = map(int,input().split())
to=[[] for _ in range(n)]
dist=[[0] *3 for _ in range(100005)]
INF=10**9


for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    to[a].append(b)

sv,tv=map(int,input().split())
sv-=1;tv-=1

for i in range(n):
    for j in range(3):
        dist[i][j] =INF

q=deque()
q.append((sv,0))
dist[sv][0]=0

while q:
    v,l=q.pop()
    for u in to[v]:
        nl =(l+1)%3
        if dist[u][nl] != INF: continue
        dist[u][nl] = dist[v][l]+1
        q.append((u,nl))

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()
adj = [list() for _ in range(N)]
for _ in range(M):
    u, v = map(lambda s: int(s) - 1, sys.stdin.readline().split())
    adj[u].append(v)
S, T = map(lambda s: int(s) - 1, sys.stdin.readline().split())

st = [(0, S, 0)]
seen = {S}
while len(st) > 0:
    dim, v, cnt = st.pop()
    seen.add(dim * N + v)
    if v == T and dim == 0:
        print(cnt // 3)
        exit(0)
    ndim = (dim + 1) % 3
    for nxt in adj[v]:
        if ndim * N + nxt not in seen:
            st.append((ndim, nxt, cnt + 1))
print(-1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
u=[]
v=[]
g=[[] for _ in range(n)]

for i in range(m):
    uu,vv=map(int,input().split())
    u.append(uu)
    v.append(vv)
    g[uu-1].append(vv-1)
    
s,t=map(int,input().split())
s-=1
t-=1

from collections import deque
 
def bfs(u):
    queue1 = deque([u])
    queue2 = deque([0])
    d=[]
    for i in range(n):
        d.append([-1]*3)
    d[u][0]=0
    while queue1:
        v=queue1.popleft()
        l=queue2.popleft()
        nl=(l+1)%3
        for i in g[v]:
            if d[i][nl] is -1:
                d[i][nl]=d[v][l]+1
                queue1.append(i)
                queue2.append(nl)
    return d



d=bfs(0)

ans=int(d[t][0]/3)
if d[t][0]==-1:
    ans=-1
print(ans)

Submission status: Wrong Answer

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

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

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

now = [[s-1,0]]
gone[s-1][0] = 1
for ans in range(1,1000000):
    next = []
    for point,key in now:
        for go,gokey in path[point][key]:
            if go == t-1 and gokey == 2:
                print(ans)
                exit()
            if gone[go][gokey] == 0:
                gone[go][gokey] = 1
                next.append([go,gokey])
    now = next
print(-1)

Submission status: Wrong Answer

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

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

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

now = [[s-1,0]]
gone[s-1][0] = 1
for ans in range(1,100000):
    next = []
    for point,key in now:
        for go,gokey in path[point][key]:
            if go == t-1 and gokey == 2:
                print(ans)
                exit()
            if gone[go][gokey] == 0:
                gone[go][gokey] = 1
                next.append([go,gokey])
    now = next
print(-1)

Submission status: Wrong Answer

Solution code:
#coding: utf-8
from collections import deque
N, M = map(int, input().split())
graph = {i:[] for i in range(1, N+1)}
for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    # graph[v].append(u)
S, T = map(int, input().split())
queue = deque([[graph[S][i], 0] for i in range(len(graph[S]))])
cnt = 0
visited = [False for _ in range(N)]
past = None
while queue:
    now = queue.popleft()
    now[1] += 1
    if now[1] % 3 == 0:
        # print("visited", now[0])
        visited[now[0]-1] = True
        if now[0] == T:
            print(now[1] // 3)
            exit()
        if past == now[0]:
            break
        else:
            past = now[0]
        for i in range(len(graph[now[0]])):
            queue.append([graph[now[0]][i], now[1]])
    else:
        for i in range(len(graph[now[0]])):
            queue.append([graph[now[0]][i], now[1]])
print(-1)

Submission status: Wrong Answer

Solution code:
#coding: utf-8
from collections import deque
N, M = map(int, input().split())
graph = {i:[] for i in range(1, N+1)}
for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    # graph[v].append(u)
S, T = map(int, input().split())
queue = deque([[graph[S][i], 0] for i in range(len(graph[S]))])
cnt = 0
visited = [False for _ in range(N)]
while queue:
    # print(len(queue))
    now = queue.popleft()
    # print(now)
    now[1] += 1
    # if visited[now[0]-1]:
    #     continue
    if now[1] >= 10**5:
        break
    if now[1] % 3 == 0:
        # print("visited", now[0])
        visited[now[0]-1] = True
        if now[0] == T:
            print(now[1] // 3)
            exit()
        for i in range(len(graph[now[0]])):
            queue.append([graph[now[0]][i], now[1]])
    else:
        for i in range(len(graph[now[0]])):
            queue.append([graph[now[0]][i], now[1]])
print(-1)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
tree1=[[] for _ in range(N)]
tree2=[[] for _ in range(N)]
tree3=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree1[u-1].append(v-1)
for i in range(N):
    nex=[]
    for j in tree1[i]:
        nex.extend(tree1[j])
    tree2[i].extend(nex)
for i in range(N):
    nex=[]
    for j in tree2[i]:
        nex.extend(tree1[j])
    tree3[i].extend(nex)
S,T=map(int,input().split())
now=[S-1]
T-=1
ischecked=[0]*N
ischecked[S-1]=1
ans=-1
count=0
while now:
    count+=1
    nex=[]
    for a in now:
        for i in tree3[a]:
            if ischecked[i]==1:
                continue
            if i==T:
                ans=count
                break
            nex.append(i)
            ischecked[i]=1
    now=nex
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  roads0 = [[] for _ in range(n)]
  roads1 = [[] for _ in range(n)]
  roads2 = [[] for _ in range(n)]
  
  for i in range(m):
    u, v = map(int, input().split())
    roads0[u-1].append(v-1)
    roads1[u-1].append(v-1)
    roads2[u-1].append(v-1)
  

  s, t = map(int, input().split())
  not_yet = deque([])
  already = [[False]*3 for _ in range(n)]
  dist = [[0]*3 for _ in range(n)]
  for v in roads0[s-1]:
    not_yet.append((v, 1))
    dist[v][1] = 1
    already[v][1] = True
  already[s-1][0] = True
  while not_yet:
    key = not_yet.popleft()
    k1, k2 = key[0], key[1]
    if k2 == 0:
      for v in roads1[k1]:
        if already[v][1]:
          continue
        dist[v][1] = dist[k1][0]+1
        already[v][1] = True
        not_yet.append((v, 1))
    elif k2 == 1:
      for v in roads2[k1]:
        if already[v][2]:
          continue
        dist[v][2] = dist[k1][1]+1
        already[v][2] = True
        not_yet.append((v, 2))
    else:
      for v in roads0[k1]:
        if already[v][0]:
          continue
        dist[v][0] = dist[k1][2]+1
        already[v][0] = True
        not_yet.append((v, 0))
  print(dist)
  if already[t-1][0]:
    print(dist[t-1][0]//3)
  else:
    print(-1)
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  roads0 = [[] for _ in range(n)]
  roads1 = [[] for _ in range(n)]
  roads2 = [[] for _ in range(n)]
  
  for i in range(m):
    u, v = map(int, input().split())
    roads0[u-1].append(v-1)
    roads1[u-1].append(v-1)
    roads2[u-1].append(v-1)
  

  s, t = map(int, input().split())
  not_yet = deque([])
  already = [[False]*3 for _ in range(n)]
  dist = [[0]*3 for _ in range(n)]
  for v in roads0[s-1]:
    not_yet.append((v, 1))
    dist[v][1] = 1
    already[v][1] = True
  already[s-1][0] = True
  while not_yet:
    key = not_yet.pop()
    k1, k2 = key[0], key[1]
    if k2 == 0:
      for v in roads1[k1]:
        if already[v][1]:
          continue
        dist[v][1] = dist[k1][0]+1
        already[v][1] = True
        not_yet.append((v, 1))
    elif k2 == 1:
      for v in roads2[k1]:
        if already[v][2]:
          continue
        dist[v][2] = dist[k1][1]+1
        already[v][2] = True
        not_yet.append((v, 2))
    else:
      for v in roads0[k1]:
        if already[v][0]:
          continue
        dist[v][0] = dist[k1][2]+1
        already[v][0] = True
        not_yet.append((v, 0))
  if already[t-1][0]:
    print(dist[t-1][0]//3)
  else:
    print(-1)
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    ta, tb = map(int, input().split())
    E[ta-1].append(tb-1)
S, T = map(int, input().split())
S -= 1
T -= 1

INF = float('inf')
dist = [[INF] * N for _ in range(3)]
dist[0][S] = 0
q = [[S,0]]

while q:
    cp, cd = q.pop()
    nd = (cd + 1) % 3
    for np in E[cp]:
        if dist[nd][np] != INF:
            continue
        else:
            dist[nd][np] = min(dist[nd][np], dist[cd][cp] + 1)
            q.append([np,nd])

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    ta, tb = map(int, input().split())
    E[ta-1].append(tb-1)
S, T = map(int, input().split())
S -= 1
T -= 1

INF = float('inf')
dist = [[INF] * N for _ in range(3)]
dist[0][S] = 0
q = [[S,0]]

while q:
    cp, cd = q.pop()
    if (cp == T) and (cd == 0):
        break
    nd = (cd + 1) % 3
    for np in E[cp]:
        if dist[nd][np] != INF:
            continue
        else:
            dist[nd][np] = dist[cd][cp] + 1
            q.append([np,nd])

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = [[] for _ in range(3 * (N+1))]
for _ in range(M):
    ta, tb = map(int, input().split())
    E[ta * 3].append(tb * 3 + 1)
    E[ta * 3 + 1].append(tb * 3 + 2)
    E[ta * 3 + 2].append(tb * 3)
S, T = map(int, input().split())
q = [S * 3]
flg = [0] * (3 * (N+1))
cond = 0
while q:
    cp = q.pop()
    if cp == 3 * T:
        ans = flg[cp] // 3
        cond = 1
        break

    for np in E[cp]:
        if flg[np] != 0:
            continue
        else:
            flg[np] = flg[cp] + 1
            q.append(np)

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

Submission status: Wrong Answer

Solution code:
from copy import copy
import sys
n,M=map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(M):
    u,v = [int(i) for i in input().split()]
    G[v-1].append(u-1)
s,t=map(lambda x:int(x)-1,input().split())
m = [-1 for _ in range(n)]
m2 = [-1 for _ in range(n)]
m[t] = 0
m2[t] = 0
cnt=0
while True:
    for i in range(n):
        if i == s and m[i]%3==0:
            print(m[i]//3)
            sys.exit()
            
        for j in G[i]:
            if m[i] != -1:
                m2[j] = m[i] + 1
    m = copy(m2)
    cnt += 1
    if cnt > n*5:
        print(-1)
        sys.exit()

Submission status: Wrong Answer

Solution code:
from copy import copy
import sys
n,M=map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(M):
    u,v = [int(i) for i in input().split()]
    G[v-1].append(u-1)
s,t=map(lambda x:int(x)-1,input().split())
m = [-1 for _ in range(n)]
m2 = [-1 for _ in range(n)]
m[t] = 0
m2[t] = 0
cnt=0
while True:
    for i in range(n):
        if i == s and m[i]%3==0:
            print(m[i]//3)
            sys.exit()
            
        for j in G[i]:
            if m[i] != -1:
                m2[j] = m[i] + 1
    m = copy(m2)
    cnt += 1
    if cnt > n*M:
        print(-1)
        sys.exit()

Submission status: Wrong Answer

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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n, m = map(int, readline().split())
graph = [[0] * n for _ in range(n)]
for i in range(m):
    u, v = map(int, readline().split())
    graph[u - 1][v - 1] = 1
    graph[v - 1][u - 1] = 1
s, t = map(int, readline().split())
cost = dijkstra(csr_matrix(graph))
if cost[s - 1][t - 1] == float('inf') or cost[s - 1][t - 1] % 3 == 1:
    print(-1)
else:
    print(int(sum(divmod(cost[s - 1][t - 1], 3))))