Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

2 \leq N \leq 10^5

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

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

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

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

1 \leq S, T \leq N

S \neq T

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
:
u_M v_M
S T

Output

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

Sample Input 1

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

Sample Output 1

2

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

Sample Input 2

3 3
1 2
2 3
3 1
1 2

Sample Output 2

-1

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

Sample Input 3

2 0
1 2

Sample Output 3

-1

Vertex S and Vertex T may be disconnected.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
2

Submission status: Wrong Answer

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


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.visited = [0]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.visited = [0] * self.n
        p, t = start, time
        self.visited[p] = 1
        data1[p] = 0
        next_set = deque([(p, t)])
        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.visited[q] == 2:
                    continue
                # if q == goal:
                #     return (t+1)//3
                if self.visited[q]==0:
                    data1[q] = t+1
                if self.visited[q]==1:
                    data2[q] = t+1
                self.visited[q] += 1
                next_set.append((q, t + 1))
        return -1

##################################################################################################

N, M = map(int, input().split())
graph = Graph(N, directed=True, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)
S, T = map(int, input().split())
data1 = [0]*N
data2 = [0]*N
graph.bfs(start=S, goal=T)

if data1[T-1]==0:
    print(-1)
    exit()

if data1[T-1]%3==0:
    print(data1[T-1]//3)
else:
    d = data2[T-1] - data1[T-1]
    if d%3==0:
        print(-1)
    else:
        temp = data1[T-1]
        while temp%3!=0:
            temp += d
        print(temp//3)

Submission status: Wrong Answer

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


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.visited = [0]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.visited = [0] * self.n
        p, t = start, time
        self.visited[p] = 1
        next_set = deque([(p, t)])
        i = 0
        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                i += 1
                if i > 10 ** 6:
                    return -1
                if (t+1)%3==0:
                    if self.visited[q] == 1:
                        continue
                    if q == goal:
                        return (t+1)//3
                    self.visited[q] = 1
                next_set.append((q, t + 1))
        return -1

##################################################################################################

N, M = map(int, input().split())
graph = Graph(N, directed=True, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)
S, T = map(int, input().split())
print(graph.bfs(start=S, goal=T))

Submission status: Wrong Answer

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


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.visited = [0]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.visited = [0] * self.n
        p, t = start, time
        self.visited[p] = 1
        next_set = [(p, t)]

        while next_set:
            p, t = next_set.pop()
            for q in self.edges[p]:
                if (t+1)%3==0:
                    if self.visited[q] == 1:
                        continue
                    if q == goal:
                        return (t+1)//3
                    self.visited[q] = 1
                next_set.append((q, t + 1))
        return -1

##################################################################################################

N, M = map(int, input().split())
graph = Graph(N, directed=True, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)
S, T = map(int, input().split())
print(graph.bfs(start=S, goal=T))

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**9

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

G = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int,input().split())
    u, v = u-1, v-1

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

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

dist = [INF] * (3*N)
dist[s] = 0

Q = deque([s])
while len(Q) > 0:
    u = Q.pop()
    for v in G[u]:
        if dist[v] == INF:
            dist[v] = dist[u] + 1
            Q.append(v)

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

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = set(e[i])
        for _ in range(2):
            nxt = set()
            for __ in items:
                nxt |= set(e[__])
            items = nxt
        items -= {i}
        e3[i] = list(items)

    visited = {s}

    ans = -1
    crnt = set(e3[s])
    visited |= crnt
    if t in crnt:
        print(1)
        exit()

    cnt = 1
    while crnt:
        cnt += 1
        nxt = set()
        for ci in crnt:
            nxt |= set(e3[ci])
        visited |= nxt
        crnt = nxt
        if t in crnt:
            print(cnt)
            exit()
        crnt -= visited

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [False for _ in range(n)]

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = set(e[i])
        for _ in range(2):
            nxt = set()
            for __ in items:
                for ei in e[__]:
                    nxt.add(ei)
            items = nxt
        items -= {i}
        e3[i] = list(items)

    ans = -1
    cnt = 1
    que = collections.deque(e3[s])

    visited[s] = True
    for ei in e3[s]:
        visited[ei] = True
    finflg = True

    while len(que) and finflg and cnt < 10 ** 5 + 10:
        cnt += 1
        for _ in range(len(que)):
            q = que.popleft()
            for ei in e3[q]:
                if not visited[ei]:
                    visited[ei] = True
                    que.append(ei)
                    if ei == t:
                        finflg = False
                        ans = cnt

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [False for _ in range(n)]

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = e[i]
        for _ in range(2):
            nxt = set()
            for __ in items:
                for ei in e[__]:
                    nxt.add(ei)
            items = list(nxt)
        tmp = set(items)
        tmp -= {i}
        e3[i] = list(tmp)

    ans = -1
    cnt = 1
    que = collections.deque(e3[s])

    visited[s] = True
    for ei in e3[s]:
        visited[ei] = True
    finflg = True

    while len(que) and finflg and cnt < 10 ** 5 + 10:
        cnt += 1
        for _ in range(len(que)):
            q = que.popleft()
            for ei in e3[q]:
                if not visited[ei]:
                    visited[ei] = True
                    que.append(ei)
                    if ei == t:
                        finflg = False
                        ans = cnt

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [False for _ in range(n)]

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = e[i]
        for _ in range(2):
            nxt = set()
            for __ in items:
                for ei in e[__]:
                    nxt.add(ei)
            items = list(nxt)
        tmp = set(items)
        tmp -= {i}
        e3[i] = list(tmp)

    ans = -1
    cnt = 1
    que = collections.deque(e3[s])

    visited[s] = True
    for ei in e3[s]:
        visited[ei] = True
    finflg = True

    while len(que) and finflg and cnt < 10 ** 4:
        cnt += 1
        for _ in range(len(que)):
            q = que.popleft()
            for ei in e3[q]:
                if not visited[ei]:
                    visited[ei] = True
                    que.append(ei)
                    if ei == t:
                        finflg = False
                        ans = cnt

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [False for _ in range(n)]

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = e[i]
        for _ in range(2):
            nxt = set()
            for __ in items:
                for ei in e[__]:
                    nxt.add(ei)
            items = list(nxt)
        tmp = set(items)
        tmp -= {i}
        e3[i] = list(tmp)

    ans = -1
    cnt = 1
    que = collections.deque(e3[s])

    visited[s] = True
    for ei in e3[s]:
        visited[ei] = True

    finflg = True

    while len(que) and finflg and cnt < 10 ** 5 + 1:
        cnt += 1
        for _ in range(len(que)):
            q = que.popleft()
            for ei in e3[q]:
                if not visited[ei]:
                    visited[ei] = True
                    que.append(ei)
                    if ei == t:
                        finflg = False
                        ans = cnt

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [False for _ in range(n)]

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = e[i]
        for _ in range(2):
            nxt = set()
            for __ in items:
                for ei in e[__]:
                    nxt.add(ei)
            items = list(nxt)
        tmp = set(items)
        tmp -= {i}
        e3[i] = list(tmp)

    ans = -1
    cnt = 1
    que = collections.deque(e3[s])

    visited[s] = True
    for ei in e3[s]:
        visited[ei] = True

    finflg = True

    while len(que) and finflg:
        cnt += 1
        for _ in range(len(que)):
            q = que.popleft()
            for ei in e3[q]:
                if not visited[ei]:
                    visited[ei] = True
                    que.append(ei)
                    if ei == t:
                        finflg = False
                        ans = cnt

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    e3 = [[] for _ in range(n)]
    for i in range(n):
        que = collections.deque(e[i])
        for _ in range(2):
            for __ in range(len(que)):
                tmp = que.popleft()
                for ei in e[tmp]:
                    que.append(ei)
        tmp = set(que)
        tmp -= {i}
        e3[i] = list(tmp)

    ans = -1
    cnt = 1
    que = collections.deque(e3[s])
    finflg = True

    while len(que) and finflg and cnt < 2 * 10 ** 5:
        if t in que:
            break

        cnt += 1
        for _ in range(len(que)):
            for ei in e3[que.popleft()]:
                for tmp in e3[ei]:
                    que.append(tmp)
                    if tmp == t:
                        finflg = False
                        ans = cnt

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

from heapq import heappop, heappush

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

graph = [[] for _ in range(N + 1)]
for u, v in X:
    graph[u].append(v)

INF = 10 ** 9 + 7
d = [[INF] * 3 for _ in range(N + 1)]
d[S][0] = 0
visited = [[False] * 3 for _ in range(N + 1)]
visited[S][0] = True
pq = []
heappush(pq, (0, S))

while pq:
    _, u = heappop(pq)
    for v in graph[u]:
        for i in range(3):
            if visited[v][i]:
                continue

            if d[v][(i + 1) % 3] > d[u][i] + 1:
                d[v][(i + 1) % 3] = d[u][i] + 1
                visited[v][(i + 1) % 3] = True
                heappush(pq, (d[v][(i + 1) % 3], v))

if d[T][2] == INF:
    print(-1)
else:
    print(d[T][2])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
S,T = IL()
S,T = S-1,T-1

graph3 = [set() for i in range(N)]
for x in range(N):
  for y in graph[x]:
    for z in graph[y]:
      graph3[x].add(z)
"""
graph3 = [set() for i in range(N)]
for x in range(N):
  for y in graph2[x]:
    for z in graph[y]:
      graph3[x].add(z)
"""
def bfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    for v in graph[u]:
      if d[v] != INF: continue
      d[v] = d[u] + 1
      q.append(v)
  return d

d = bfs(graph3,S)
if d[T] == INF:
  print(-1)
else:
  print(d[T])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

G2=[[] for i in range(N+1)]
for i in range(1,N+1):
  for j in G[i]:
    for k in G[j]:
      for l in G[k]:
        G2[i].append(l)

print(-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
to = [[] for _ in range(N*3)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a*3].append(b*3+1)
  to[a*3+1].append(b*3+2)
  to[a*3+2].append(b*3)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Stack = [start*3]
visit = [INF for _ in range(N*3)]
visit[start*3] = 0
while Stack:
  v = Stack.pop()
  for w in to[v]:
    if visit[w] != INF:
      continue
    visit[w] = visit[v]+1
    if w == end*3:
      print(visit[w]//3)
      exit()
    Stack.append(w) #step歩目でwにいて次vへ行く。

#print(visit)
if visit[end*3] == INF:
  ans = -1
else:
  ans = visit[end*3]//3
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
to = [[] for _ in range(N*3)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a*3].append(b*3+1)
  to[a*3+1].append(b*3+2)
  to[a*3+2].append(b*3)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Stack = [start*3]
visit = [INF for _ in range(N*3)]
visit[start*3] = 0
while Stack:
  v = Stack.pop()
  for w in to[v]:
    if visit[w] != INF:
      continue
    visit[w] = min(visit[w],visit[v]+1) 
    Stack.append(w) #step歩目でwにいて次vへ行く。

#print(visit)
if visit[end*3] == INF:
  ans = -1
else:
  ans = visit[end*3]//3
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
to = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a].append(b)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Stack = [(start,0)] #今の点、何歩目か
visit = [[INF,INF,INF] for _ in range(N)] #三歩目、一歩目、二歩目
visit[start][0] = 0
while Stack: #今の点、けんけんぱのどれか、一個前に止まった点
  v,step = Stack.pop()
  now = visit[v][step]
  step = (step+1)%3 #ここでstep+1歩目でvへ行く
  for w in to[v]:
    if visit[w][step] != INF:
      continue
    Stack.append((w,step)) #step歩目でwにいて次vへ行く。
    if step %3 == 0:
      visit[w][step] = min(visit[w][step],now+1)
    else:
      visit[w][step] = min(visit[w][step],now)
#print(visit)
if visit[end][0] == INF:
  ans = -1
else:
  ans = visit[end][0]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
E = defaultdict(list)
for i in range(M):
	u, v = rl()
	E[u-1].append(v-1)
	#E[v-1].append(u-1)
S, T = rl()
S -= 1
T -= 1

dp = [[float('inf')]*3 for i in range(N)]

def dfs(n, d):
	if n == T:
		return
	for m in E[n]:
		r = (d+1)%3
		if dp[m][r] > d+1:
			dp[m][r] = d+1
			dfs(m, d+1)

dfs(S, 0)
if dp[T][0] != float('inf'):
	print(dp[T][0]//3)
else:
	print(-1)

Submission status: Wrong Answer

Solution code:

import sys

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

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

while len(todo)>0:
    checking = todo.pop()
    next_targets = deque([checking])
    for i in range(3):
        purposes = []
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.append(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] == -10000:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

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:
            if dist % 3 == 0:
                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))