Problem:


Score : 500 points

Problem Statement

Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G.
G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.

First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.

Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq \min(10^5, N (N-1))

1 \leq u_i, v_i \leq N(1 \leq i \leq M)

u_i \neq v_i (1 \leq i \leq M)

If i \neq j, (u_i, v_i) \neq (u_j, v_j).

1 \leq S, T \leq N

S \neq T

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
:
u_M v_M
S T

Output

If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1.
If he can, print the minimum number of ken-ken-pa needed to reach vertex T.

Sample Input 1

4 4
1 2
2 3
3 4
4 1
1 3

Sample Output 1

2

Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.

Sample Input 2

3 3
1 2
2 3
3 1
1 2

Sample Output 2

-1

Any number of ken-ken-pa will bring Ken back to Vertex 1, so he cannot reach Vertex 2, though he can pass through it in the middle of a ken-ken-pa.

Sample Input 3

2 0
1 2

Sample Output 3

-1

Vertex S and Vertex T may be disconnected.

Sample Input 4

6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6

Sample Output 4

2



Sample input:
4 4
1 2
2 3
3 4
4 1
1 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    UV = ii2nnn(M)
    S, T = i2nn()
    to = [[] for _ in range(N+1)]
    for u, v in UV:
        to[u].append(v)
    bit = [0] * (N+1)
    q = deque()
    q.append((S, 1, 0))
    while q:
        i, b, c = q.pop()
        if b & bit[i] == b:
            continue
        if i == T and (b & 1) == 1:
            print(c//3)
            return
        bit[i] |= b
        b2 = b << 1
        if b2 >= 8:
            b2 -= 7
        for j in to[i]:
            q.append((j, b2, c+1))
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
import sys
sys.getrecursionlimit()

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

graph1 = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]

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


def dfs(v0, v, k):
    if k == 0:
        graph2[v0].append((1, v))
        return

    for _, nv in graph1[v]:
        dfs(v0, nv, k-1)

for i in range(n):
    dfs(i, i, 3)
    # print(graph1[i])

for i in range(n):
    graph2[i] = list(set(graph2[i]))
# print()
for i in range(n):
    print(graph2[i])

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


from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

inf = float('inf')
dist = dijkstra(graph2, n, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t])

Submission status: Wrong Answer

Solution code:
from collections import deque


conn = {}
N, M = map(int, input().split())
for _ in range(M):
    u, v = map(int, input().split())
    if u not in conn:
        conn[u] = set()
    conn[u].add(v)
S, T = map(int, input().split())


def get(dic, key):
    return dic[key] if key in dic else []


def hop3(n):
    ans = set()
    n1 = n
    for n2 in get(conn, n1):
        ans.add(n2)
        for n3 in get(conn, n2):
            if n3 == n1:
                continue
            for n4 in get(conn, n3):
                ans.add(n4)
    return ans


q = deque()
q.append(S)
dp = [-1] * (N + 1)
dp[S] = 0


while len(q) > 0:
    n = q.popleft()
    for m in hop3(n):
        if dp[m] < 0:
            dp[m] = dp[n] + 1
            if m == T:
                print(dp[m])
                exit()
            q.append(m)
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    adj1 = [set() for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj1[u-1].add(v-1)
    S, T = map(int, input().split())
    adj2 = [set() for _ in range(N)]
    q = deque()
    q.append((S, []))
    while len(q):
        p, history = q.popleft()
        if len(history) > 3:
            if p not in adj2[history[-3]]:
                adj2[history[-3]].add(p)
            else:
                continue
        nhistory = history + [p]
        for nxt in adj1[p]:
            if len(nhistory) > 3 and p in adj2[nhistory[-3]]:
                continue
            q.append((nxt, nhistory))

    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost)
            return
        for nxt in adj2[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    UV = ii2nnn(M)
    S, T = i2nn()
    to = [[] for _ in range(N+1)]
    for u, v in UV:
        to[u].append(v)
    bit = [0] * (N+1)
    q = deque()
    q.append((S, 1, 0))
    x = 0
    while q:
        x += 1
        if x > 20:
            break
        i, b, c = q.pop()
        if b & bit[i] == b:
            continue
        if i == T and (b & 1) == 1:
            print(c//3)
            return
        bit[i] |= b
        b2 = b << 1
        if b2 >= 8:
            b2 -= 7
        for j in to[i]:
            q.append((j, b2, c+1))
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
List = [[] for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    List[u-1].append(v-1)
S, T = map(int, input().split())
que = [(S-1, 0)]
node = [[] for _ in range(N)]
for i in range(N):
    for j in List[i]:
        for k in List[j]:
            for l in List[k]:
                node[i].append(l)
step = 0
ans = -1
flag = [True]*N
while que:
    edge = que.pop()
    if edge[0]==T-1:
        ans = edge[1]
        break
    step=edge[1]
    for i in node[edge[0]]:
        if flag[i]:
            que.append((i, step+1))
            flag[i]=False
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()

    # print(reversed_graph_dict)

    import collections
    def bfs(graph, root):
        # 三段先のグラフを先に作っておく。
        three_steps_dict = defaultdict(list)
        for i in range(1, N+1):
            first_step = graph[i]
            second_step = []
            for x in first_step:
                second_step += graph[x]
            third_step = []
            for x in second_step:
                third_step += graph[x]
            three_steps_dict[i] = third_step

        seen, queue = set([root]), collections.deque([root])
        tries = 0
        while queue:
            tries += 1
            vertex = queue.popleft()
            for node in three_steps_dict[vertex]:
                if node == S:
                    print(tries)
                    return
                if node not in seen:
                    seen.add(node)
                    queue.append(node)
        print(-1)
        return

    bfs(reversed_graph_dict, T)


main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys

# main
N, M = [int(i) for i in input().split(' ')]
matrix = np.matrix([ [0 for i in range(N)] for i in range(N) ])

for i in range(M):
    (u, v) = [int(i) for i in input().split(' ')]
    matrix[u - 1, v - 1] = 1

(S, T) = [int(i) for i in input().split(' ')]

start = np.matrix([1 if i == S - 1 else 0 for i in range(N)])

def matrix_eval_three_steps(matrix, vector):
    return np.dot(np.dot(np.dot(vector, matrix), matrix), matrix)

for i in range(int(N/3)):
    before = start
    start = matrix_eval_three_steps(matrix, start)
    if np.allclose(before, start):
        break
    if start[0, T - 1] > 0:
        print(i + 1)
        sys.exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import copy

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

que = set([1])
nque = set()
ans = 0

while T not in que and ans <= N:
    for _ in range(3):
    
        for s in que:
            for t in G[s-1]:
                nque.add(t) 

        que = copy.copy(nque)
        nque.clear()
    ans += 1

if ans > N: ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

inf = 10 ** 6

def main():
    n, m = [int(i) for i in sys.stdin.readline().strip().split()]
    edges = [tuple(int(i) for i in sys.stdin.readline().strip().split()) for j in range(m)]
    e_dict = {i: [] for i in range(1, n+1)}
    s, t = [int(i) for i in sys.stdin.readline().strip().split()]

    for a, b in edges:
        e_dict[a].append(b)

    ret = -1
    loop = 0
    que = []
    que.append((s, 0))
    while len(que):
        loop += 1
        if loop > inf:
            break
        nod, st = que.pop(0)
        if nod == t and st % 3 == 0:
            ret = st // 3
            break
        for u in e_dict[nod]:
            que.append((u, st+1))
    return ret
    
print(main())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
    u,v = inpl()
    u -= 1
    v -= 1
    lines[u].add(v+N)
    lines[u+N].add(v+2*N)
    lines[u+2*N].add(v)


S,T = inpl()
S -= 1
T -= 1



def search (s,w_0): #s->t
	global weight
	global q

	for t in list(lines[s]):
		w = w_0 + 1
		if weight[t] > w:
			heapq.heappush(q, [w,t])
			weight[t] = w


ans = INF

# Start, S
weight = [INF]*(N*3)
weight[S] = 0
q = [[0,S]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)
ans = min(ans,weight[T],weight[N+T],weight[T+2*N])

# Start, S+N
weight = [INF]*(N*3)
weight[S] = 0
q = [[0,S]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)
ans = min(ans,weight[T],weight[N+T],weight[T+2*N])

# Start, S+2*N
weight = [INF]*(N*3)
weight[S] = 0
q = [[0,S]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)
ans = min(ans,weight[T],weight[N+T],weight[T+2*N])

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys

# main
N, M = [int(i) for i in input().split(' ')]
matrix = np.matrix([ [0 for i in range(N)] for i in range(N) ])

for i in range(M):
    (u, v) = [int(i) for i in input().split(' ')]
    matrix[u - 1, v - 1] = 1

(S, T) = [int(i) for i in input().split(' ')]

start = np.matrix([1 if i == S - 1 else 0 for i in range(N)])

def matrix_eval_three_steps(matrix, vector):
    return np.dot(np.dot(np.dot(vector, matrix), matrix), matrix)

for i in range(int(N/3)):
    start = matrix_eval_three_steps(matrix, start)
    if start[0, T - 1] > 0:
        print(i + 1)
        sys.exit()

print(-1)

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

    # print(reversed_graph_dict)

    import collections
    def bfs(graph, root):
        seen, queue = set([root]), collections.deque([root])
        tries = 0
        while queue:
            tries += 1
            vertex = queue.popleft()
            # 三段先を見に行く。
            first_step = graph[vertex]
            second_step = []
            for x in first_step:
                second_step += graph[x]
            third_step = []
            for x in second_step:
                third_step += graph[x]
            for node in third_step:
                if node == S:
                    print(tries)
                    return
                if node not in seen:
                    seen.add(node)
                    queue.append(node)
        print(-1)
        return

    bfs(reversed_graph_dict, T)


main()

Submission status: Wrong Answer

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

edges = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    edges[u].append(v)

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

cost = 0
memo = 0
ans = -1

que = deque()
que.append(s)

while len(que):
    pos = que.popleft()
    if pos == t:
        if cost % 3 == 0:
            ans = cost // 3
            break
        elif cost % 3 == memo:
            break
        else:
            memo = cost % 3
    for n in edges[pos]:
        que.append(n)
    cost += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()
S,T = LI()

routes = {}
for i in range(N):
    routes[i] = []
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = {}
for i in range(N):
    used[i] = -1


def skip(now,move_cnt):
    if move_cnt != 0 and move_cnt % 3 == 0:
        used[now] = move_cnt//3
    for route in routes[now]:
        if used[route] == -1:
            skip(route,move_cnt+1)
        else:
            continue

skip(S,0)
# print(used)
try:
    ans = used[T]
except:
    ans = -1
print(ans)

Submission status: Wrong Answer

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

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

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = [St-1]
hoge = [0]*N
for i in range(1,N*3+3):
    l = 0
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > D[q][(i-1)%3]:
                D[s][i%3] = D[q][(i-1)%3]+1
                if not s in hoge[:l]:
                    hoge[l] = s
                    l += 1
    queue = hoge[:l]
if D[T-1][0] > N*2:
    print(-1)
else:
    print(D[T-1][0]//3)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    G[u-1].add(v-1)
#print(G)
S,T=map(int,input().split())
S-=1;T-=1
#dp[i][j]:i番目の頂点をmod 3=jで行けるかどうか
dp=[[0 for i in range(3)] for i in range(N)]
dp2=[[10**10 for i in range(3)] for i in range(N)]
dp[S][0]=1
dp2[S][0]=0
q=deque([S])
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        tmp=sum(dp[p])
        for i in range(3):
            if dp[r][i]==1:
                dp[p][i-2]=1
                dp2[p][i-2]=min(dp2[r][i]+1,dp2[p][i-2])
        if tmp==sum(dp[p]):
            continue
        q.append(p)
#print(dp)
#print(dp2)
if dp[T][0]==0:
    print(-1)
else:
    print(dp2[T][0]//3)

Submission status: Wrong Answer

Solution code:
import heapq
def sol(inp=input):
    n,m=map(int,inp().split())
    G={i+1:set() for i in range(n)}
    for _ in range(m):
        i,j=map(int,inp().split())
        G[i].add(j)
    s,t=map(int,inp().split())
    cache_kenken={}
    cache_kenkenpa={}
    def kenken(v):
        if v not in cache_kenken:
            cache_kenken[v]=[v2 for v1 in G[v] for v2 in G[v1]]
        return cache_kenken[v]
    def kenkenpa(v):
        if v not in cache_kenkenpa:
            cache_kenkenpa[v]=[v3 for v2 in kenken(v) for v3 in G[v2]]
        return cache_kenkenpa[v]
    visited={s}
    que=[]
    heapq.heappush(que,(0,s))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in kenkenpa(u):
            #print('{}:{}->{}'.format(step,u,v))
            if v==t:
                return step+1
            if v not in visited:
                heapq.heappush(que,(step+1,v))
                visited.add(v)
    return -1

Submission status: Wrong Answer

Solution code:
import heapq
def sol(inp=input):
    n,m=map(int,inp().split())
    G={i+1:set() for i in range(n)}
    for _ in range(m):
        i,j=map(int,inp().split())
        G[i].add(j)
    s,t=map(int,inp().split())
    cache_kenken={}
    cache_kenkenpa={}
    def kenken(v):
        if v not in cache_kenken:
            cache_kenken[v]=[v2 for v1 in G[v] for v2 in G[v1]]
        return cache_kenken[v]
    def kenkenpa(v):
        if v not in cache_kenkenpa:
            cache_kenkenpa[v]=[v3 for v2 in kenken(v) for v3 in G[v2]]
        return cache_kenkenpa[v]
    visited={s}
    que=[]
    heapq.heappush(que,(0,s))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in kenkenpa(u):
            print('{}:{}->{}'.format(step,u,v))
            if v==t:
                return step+1
            if v not in visited:
                heapq.heappush(que,(step+1,v))
                visited.add(v)
    return -1
print(sol())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

from collections import deque
from copy import deepcopy


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

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

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


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

q = deque([])
cnt = 0

ans = -1

def explore(now,cnt) :
    if cnt == 3 :
        q.append(now)
        return
    
    
    for to in G[now] :
        explore(to,cnt+1)
    

explore(S,0)

if T in q :
    ans = 1
else :
    flg = 0
    r = deepcopy(q)
    for qq in r :
        explore(qq,0)
        if T in q :
            ans = 2
            flg = 1
            break
        
    if not flg :
        r = deepcopy(q)
        for qq in r :
            explore(qq,0)
            if T in q :
                ans = 3
                break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from heapq import heappop, heappush
from io import IOBase

import __pypy__


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u - 1].append(v - 1)

    start, t = map(int, input().split())
    start -= 1

    new_graph = [[] for _ in range(n)]
    for i in range(n):
        for child in graph[i]:
            for grandchild in graph[child]:
                for greatgrandchild in graph[grandchild]:
                    new_graph[i].append(greatgrandchild)

    n = len(graph)
    dist = [10**9] * n
    dist[start] = 0

    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if path_len == dist[v]:
            for w in graph[v]:
                if 1 + path_len < dist[w]:
                    dist[w] = 1 + path_len
                    heappush(queue, (1 + path_len, w))

    d = dist[t - 1]
    print(-1 if d == 10**9 else d)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


input = sys.stdin.readline
n, m = map(int, input().split())
info = tuple(map(int, input().split()) for i in range(m))
s, t = map(int, input().split())

graph = [[] for i in range(n)]
for i, j in info:
    graph[i-1].append(j-1)

graph2 = [[] for i in range(n)]
q = deque()
q.append((s - 1, 0))
INF = float("inf")
visited = [INF] * n
visited_1 = [INF] * n
visited_2 = [INF] * n
visited[0] = 0
while q:
    pos, times = q.popleft()
    for i in graph[pos]:
        if (times + 1) % 3 == 1 and times + 1 < visited_1[i]:
            visited_1[i] = times + 1
            q.append((i, times + 1))
        elif (times + 1) % 3 == 2 and times + 1 < visited_2[i]:
            visited_2[i] = times + 1
            q.append((i, times + 1))            
        elif (times + 1) % 3 == 0 and times + 1 < visited[i]:
            visited[i] = times + 1
            q.append((i, times+1))

if visited[t-1] == float("inf"):
    print(-1)
else:
    print(visited[t-1]//3)

Submission status: Wrong Answer

Solution code:
def step():
    onestep_points = set()
    twostep_points = set()
    threestep_points = set()
    for p in current_points:
        if(routes[p] == 0):
            continue
        for s in routes[p]:
            onestep_points.add(s)
    for p in onestep_points:
        if(routes[p] == 0):
            continue
        for s in routes[p]:
            twostep_points.add(s)
    for p in twostep_points:
        if(routes[p] == 0):
            continue
        for s in routes[p]:
            threestep_points.add(s)
    next_stop = set()
    for p in threestep_points:
        if(p not in stopped_points):
            stopped_points.add(p)
            next_stop.add(p)
    return next_stop
  
import collections
routes = collections.Counter()

N, M = list(map(int, input().split()))
for m in range(M):
    routes[m+1] = []

for m in range(M):
    u, v = list(map(int, input().split()))
    routes[u].append(v)

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

loop = 0
current_points = set()
stopped_points = set()
current_points.add(1)

ans = -1
while(True):
    loop += 1
    current_points = step()
    if(T in current_points):
        ans = loop
        break
    if(len(current_points) == 0):
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math

from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


def main():
    node_num, edge_num = map(int, input().split())
    graph_data = defaultdict(set)

    for i in range(edge_num):
        a, b = map(int, input().split())
        graph_data[a].add(b)

    start, goal = map(int, input().split())
    visit_flg = [0 for i in range(node_num + 1)]
    visit_flg[1] += 1

    now_set = set()
    now_set.add(start)
    next_set = set()

    ans = 0

    while len(now_set) > 0:
        ans += 1

        for now_node in now_set:
            search_now_set = set()
            search_now_set.add(now_node)
            search_next_set = set()

            for i in range(3):
                for search_now_node in search_now_set:
                    search_next_set |= graph_data[search_now_node]
                search_now_set = search_next_set
                search_next_set = set()

            for ele_check in search_now_set:
                if visit_flg[ele_check]:
                    continue
                else:
                    visit_flg[ele_check] = 1
                    next_set.add(ele_check)

        if visit_flg[goal]:
            break

        now_set = next_set
        next_set = set()

    if visit_flg[goal]:
        print(ans)
    else:
        print(-1)












if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    G[u-1].add(v-1)
#print(G)
S,T=map(int,input().split())
S-=1;T-=1
#dp[i][j]:i番目の頂点をmod 3=jで行けるかどうか
dp=[[0 for i in range(3)] for i in range(N)]
dp2=[[0 for i in range(3)] for i in range(N)]
dp[S][0]=1
q=deque([S])
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        tmp=sum(dp[p])
        for i in range(3):
            if dp[r][i]==1:
                dp[p][i-2]=1
                dp2[p][i-2]=dp2[r][i]+(1 if i==2 else 0)
        if tmp==sum(dp[p]):
            continue
        q.append(p)
#print(dp)
#print(dp2)
if dp[T][0]==0:
    print(-1)
else:
    print(dp2[T][0])

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    G[u-1].add(v-1)
#print(G)
S,T=map(int,input().split())
S-=1;T-=1
#dp[i][j]:i番目の頂点をmod 3=jで行けるかどうか
dp=[[0 for i in range(3)] for i in range(N)]
dp2=[[0 for i in range(3)] for i in range(N)]
dp[S][0]=1
q=deque([S])
while(len(q)>0):
    r=q.popleft()
    for p in G[r]:
        tmp=sum(dp[p])
        for i in range(3):
            if dp[r][i]==1:
                dp[p][i-2]=1
                dp2[p][i-2]=dp2[r][i]+(1 if i==2 else 0)
        if tmp==sum(dp[p]):
            continue
        q.append(p)
#print(dp)
#print(dp2)
if dp[T][0]==0:
    print(-1)
else:
    print(dp2[T][0])

Submission status: Wrong Answer

Solution code:
import sys
from queue import Queue

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
g = []
for i in range(n):
    g.append([])
for i in range(m):
    u, v = na()
    g[u-1].append(v-1)

s, t = na()
s -= 1;
t -= 1

ds = [[9999999999] * n for i in range(3)]
ds[0][s] = 0

q = Queue()
q.put((0, s))
while not q.empty():
    r, cur = q.get_nowait()
    nr = (r+1) % 3
    for e in g[cur]:
        # print(nr, e)
        if ds[nr][e] > ds[r][cur] + 1:
            ds[nr][e] = ds[r][cur] + 1
            q.put((nr, e))
if ds[0][t] >= 0:
    print(ds[0][t]//3)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
o=inputs()
s,T=map(int,o.pop().split())

for i in o:
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    #undirected->erase#edges[__].append((_,___))
    """
    _,__=map(int,i.split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

    #undirected->erase#edges[__].append(_)
    """
"""#weighted->erase

from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=set()
seen.add(3*s)
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if t not in seen:
            dq.append((t,c+1))
            seen.add(now)

print("-1")