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

Solution (Python):
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]
i = 0
while queue != []:
    i += 1
    hoge = []
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > i:
                D[s][i%3] = i
                if not s in hoge:
                    hoge.append(s)
    queue = hoge[:]
    if D[T-1][0] != float('inf'):
        break
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)

Solution (Python):


import sys

v1mask= set()
v2mask= set()

def getVertex(i,e):
    global v1mask, v2mask
    v= set()
    for v1 in e[i]:
        if v1 in v1mask: continue
        v1mask.add( v1 )
        for v2 in e[v1]:
            if v2 in v2mask: continue
            v2mask.add( v2 )
            for v3 in e[v2]: v.add( v3 )
    
    return v

n,m = [ int(x) for x in sys.stdin.readline().split() ]
e = { i:[] for i in range(n) }
for _ in range(m):
    u,v = [ int(x) for x in sys.stdin.readline().split() ]
    e[u-1].append( v-1 )
s,t = [ int(x)-1 for x in sys.stdin.readline().split() ]

hop= 0
now = {s}
visit = {s}
while True:
    hop+= 1
    n= set()
    for i in now:
        n |= getVertex(i,e) - visit
        if t in n: break
    
    if t in n: break
    if not n:
        hop= -1
        break
    now = n
    visit|= n

print( hop )

Solution (Python):

import sys
import heapq
from collections import defaultdict


def solve(N: int, M: int, U: "List[int]", V: "List[int]", S: int, T: int):
    S -= 1
    T -= 1
    adj = [[] for i in range(N)]
    for u, v in zip(U, V):
        adj[u-1].append(v-1)
    color = [[0, 0, 0] for i in range(N)]
    color[S][0] = 1
    Q = [(0, S)]

    while len(Q) > 0:
        d, u = heapq.heappop(Q)
        if u == T and d % 3 == 0:
            print(d // 3)
            return
        for v in adj[u]:
            if color[v][(d+1) % 3] == 1:
                continue
            heapq.heappush(Q, (d+1, v))
            color[v][(d+1) % 3] = 1

    print(-1)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    u = [int()] * (M)  
    v = [int()] * (M)  
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  
    T = int(next(tokens))  
    solve(N, M, u, v, S, T)

if __name__ == '__main__':
    main()

Solution (Python):
import queue

n,m = map(int, input().split())
a = [[] for i in range(n)]

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

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

inf = float('inf')
d = [[inf, inf, inf] for i in range(n)]
d[s][0]=0

q = queue.Queue()
for i in range(len(a[s])):
    q.put(a[s][i])
    d[a[s][i]][1]=1


while not q.empty():
    p = q.get()
    for i in range(len(a[p])):
        r = a[p][i]
        c = []
        if d[r][0]==inf:
            c.append(0)
        if d[r][1]==inf:
            c.append(1)
        if d[r][2]==inf:
            c.append(2)
        if not c:
            continue

        flag = False
        for j in range(len(c)):
            if c[j]==0:
                if d[p][2]!=inf:
                    break
            elif c[j]==1:
                if d[p][0]!=inf:
                    break
            elif c[j]==2:
                if d[p][1]!=inf:
                    break
            if j==len(c)-1:
                flag=True
        if flag:
            continue

        q.put(r)
        for j in range(len(c)):
            if c[j]==0:
                d[r][0] = d[p][2] + 1
            elif c[j]==1:
                d[r][1] = d[p][0] + 1
            elif c[j]==2:
                d[r][2] = d[p][1] + 1

        if r==t and d[r][0]!=inf:
            print(d[r][0]//3)
            exit()
print(-1)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
E = {u: set() for u in range(1, N+1)}
for i in range(M):
    u, v = map(int, input().split())
    E[u].add(v)
S, T = map(int, input().split())

X = {}
for u in E:
    for i in range(3):
        X[(u, i)] = set([(v, (i + 1) % 3) for v in E[u]])


queue = deque()
queue.append(((S, 0), 0))
visited = set()

while len(queue) > 0:
    u, n = queue.popleft()
    if u in visited:
        continue
    visited.add(u)
    if u == (T, 0):
        print(n // 3)
        exit()
    for v in X[u]:
        queue.append((v, n + 1))

print(-1)

Solution (Python):



import sys
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
edge = [[] for _ in range(N+1)]
for _ in range(M):
  u,v = map(int,input().split())
  edge[u].append(v)
S,T = map(int,input().split())

INF = 10 ** 9
dist = [[INF,INF,INF] for _ in range(N+1)]

d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in edge[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq

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

Solution (Python):

import sys
import copy
sys.setrecursionlimit(4100000)

n,m = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for i in range(m)]
t = [int(i) for i in input().split()]
from collections import defaultdict
steps = defaultdict(list)
for a,b in l:
    steps[a].append(b)
seen = set()
counter = 0
queue = [t[0]]
nextqueue = []
ans = False
depth = 0
while queue:
    current = queue.pop(0)
    if counter == 0 and current == t[1]:
        ans = True
        break
    if counter == 3 and current == t[1]:
        ans = True
        break
    for a in steps[current]:
        if (a,counter+1) not in seen:
            seen.add((a,counter+1))
            nextqueue.append(a)
    if queue == []:
        if counter == 3:
            counter = 1
        else:
            counter += 1
        queue = copy.deepcopy(nextqueue)
        nextqueue = []
        depth += 1

if ans is True:
    print(depth//3)
else:
    print(-1)

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = [[] for _ in range(N)]
    for _ in range(M):
        u,v = MI_()
        edge[u].append(v)
    S, T = MI_()

    queue = [S]
    checked = set()
    for i in range(1,max(3*N+1,3*M+2)):
        tmp = set()
        while queue:
            s = queue.pop()
            if i % 3 == 0:
                if s in checked:
                    continue
                else:
                    checked.add(s)
            for to in edge[s]:
                if to == T:
                    if i%3==0:
                        print(i//3)
                        exit()
                tmp.add(to)
        queue = tmp
    print(-1)
            

if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
c=[[0]*(n+1) for i in range(3)]
s,t=map(int,input().split())
c[2][s]=1
q=[s]
def ken(a):
    tl=[]
    for i in q:
        for j in edge[i]:
            if not c[a][j]:
                tl.append(j)
                c[a][j]=1
    return tl
for i in range(n):
    q=ken(0)
    q=ken(1)
    q=ken(2)
    if c[2][t]==1:
        print(i+1)
        break
else:
    print(-1)

Solution (Python):
import heapq
N, M = map(int, input().split())

edges = [set() for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    edges[u-1].add(v-1)

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

cost = [-1 for _ in range(N)]
q = []
heapq.heappush(q, (0, S))

step1memo = set()
step2memo = set()
step3memo = set()

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for u1 in edges[u]:
        if u1 in step1memo:
            continue
        step1memo.add(u1)
        for u2 in edges[u1]:
            if u2 in step2memo:
                continue
            step2memo.add(u2)
            for u3 in edges[u2]:
                heapq.heappush(q, (c+1, u3))

print(cost[T])

Solution (Python):
import sys
from collections import deque  
from collections import defaultdict  
from heapq import heapify, heappush, heappop, heappushpop  
from bisect import bisect_left, bisect_right  



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.popleft()
        if b & bit[i] == b:
            continue
        if i == T and (b & 1) == 1:
            print(c//3)
            return
        bit[i] |= b
        b2 = bit[i] << 1
        if b2 >= 8:
            b2 -= 7
        for j in to[i]:
            q.append((j, b2, c+1))
    print(-1)

main()

Solution (Python):
import heapq

n, m = [int(i) for i in input().split()]
U = [[int(i) for i in input().split()] for j in range(m)]
s, t = [int(i) for i in input().split()]

E = [[] for i in range(n + 1)]

for u, v in U:
    E[u].append(v)

visited = [[False] * 3 for i in range(n + 1)]

V = []
heapq.heappush(V, (0, s))

while V:
    c, v = heapq.heappop(V)
    if v == t and c % 3 == 0:
        print(c // 3)
        exit()
    if visited[v][c % 3]:
        continue
    visited[v][c % 3] = True

    for to in E[v]:
        heapq.heappush(V, (c + 1, to))

print(-1)

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import random
import collections
import math
import itertools
import bisect

def real_main():
    n, m = read_int_array()
    g = [[] for _ in range(n)]
    for _ in range(m):
        f, t = read_int_array()
        g[f-1].append(t-1)

    vis = [[False]*3 for _ in range(n)]

    s, t = read_int_array()
    if s == t:
        print(0)
        return
    s -= 1
    t -= 1
    q = [(s, 0)]
    vis[s][0] = True
    level = 0
    while q:
        level += 1
        next_q = []
        for n, dmod in q:
            next_dmod = (dmod + 1) % 3
            for c in g[n]:
                if not vis[c][next_dmod]:
                    if c == t and next_dmod == 0:
                        print(level // 3)
                        return
                    vis[c][next_dmod] = True
                    next_q.append((c, next_dmod))
        q = next_q
    print(-1)



def solve():
    pass


def main():
    if False and 'PYCHARM_HOSTED' in os.environ:
        main_pycharm()
    else:
        real_main()


from copy import deepcopy
def main_pycharm():
    solution = solve

    test_inputs = None
    test_outputs = None
    judge = None
    slow_solution = None
    if solution is not None:
        if test_outputs is not None:
            test_with_answers(solution, test_inputs, test_outputs)
        if judge is not None:
            test_with_judge(solution, test_inputs, judge)
        if slow_solution is not None:
            test_with_slow_solution(solution, test_inputs, slow_solution)


def test_with_answers(solution, inputs, answers):
    total, wrong = 0, 0
    for args, test_ans in zip(inputs, answers):
        ans = solution(*deepcopy(args))
        if ans != test_ans:
            print('WRONG! ans=%s, test_ans=%s, args=%s' % (ans, test_ans, args))
            wrong += 1
        else:
            print('GOOD')
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_judge(solution, inputs_gen, judge):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        if not judge(deepcopy(ans), *deepcopy(args)):
            print('WRONG! ans=%s, args=%s' % (ans, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_slow_solution(solution, inputs_gen, solution_slow):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        slow = solution_slow(*deepcopy(args))
        if ans != slow:
            print('WRONG! ans=%s, slow=%s, args=%s' % (ans, slow, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))

def generate_nums(n, min, max, check_if_good=None):
    while True:
        nums = [random.randint(min, max) for _ in range(n)]
        if check_if_good is None or check_if_good(nums):
            return nums



def mergesort(A, key=lambda x: x, reverse=False):
    C = A
    A = list(range(len(A)))
    B = list(A)

    n = len(A)
    for i in range(0, n - 1, 2):
        if key(C[A[i]]) > key(C[A[i ^ 1]]):
            A[i], A[i ^ 1] = A[i ^ 1], A[i]

    width = 2
    while width < n:
        for i in range(0, n, 2 * width):
            R1, R2 = min(i + width, n), min(i + 2 * width, n)
            j, k = R1, i
            while i < R1 and j < R2:
                if key(C[A[i]]) > key(C[A[j]]):
                    B[k] = A[j]
                    j += 1
                else:
                    B[k] = A[i]
                    i += 1
                k += 1
            while i < R1:
                B[k] = A[i]
                k += 1
                i += 1
            while k < R2:
                B[k] = A[k]
                k += 1
        A, B = B, A
        width *= 2

    if reverse:
        A.reverse()
    return A

def mergesort_simple(A, reverse=False):
    C = A
    A = list(range(len(A)))
    B = list(A)

    n = len(A)
    for i in range(0, n - 1, 2):
        if C[A[i]] > C[A[i ^ 1]]:
            A[i], A[i ^ 1] = A[i ^ 1], A[i]

    width = 2
    while width < n:
        for i in range(0, n, 2 * width):
            R1, R2 = min(i + width, n), min(i + 2 * width, n)
            j, k = R1, i
            while i < R1 and j < R2:
                if C[A[i]] > C[A[j]]:
                    B[k] = A[j]
                    j += 1
                else:
                    B[k] = A[i]
                    i += 1
                k += 1
            while i < R1:
                B[k] = A[i]
                k += 1
                i += 1
            while k < R2:
                B[k] = A[k]
                k += 1
        A, B = B, A
        width *= 2

    if reverse:
        A.reverse()
    return A




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    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(b"\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()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    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()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

def read():
    return input()

def read_int():
    return int(input())

def read_array(sep=None, maxsplit=-1):
    return input().split(sep, maxsplit)

def read_int_array():
    return [int(a) for a in read_array()]



if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
visited = [[False,False,False] for _ in range(n)]
ren = [[] for _ in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    ren[u-1].append(v)
s,t = map(int,input().split())

Q = [(s,0)]
visited[s-1][2]=True
ans = -1

while len(Q)>0:
    curs,curcount = Q.pop(0)
    if curs == t:
        ans = curcount
        break
    for i in ren[curs-1]:
        if not visited[i-1][0]:
            visited[i-1][0]=True
            for j in ren[i-1]:
                if not visited[j-1][1]:
                    visited[j-1][1]=True
                    for k in ren[j-1]:
                        if not visited[k-1][2]:
                            visited[k-1][2]=True
                            Q.append((k,curcount+1))

print(ans)

Solution (Python):
n,m=map(int,input().split())
u,v=[],[]
path=[[] for i in range(n)]
for i in range(m):
    ui,vi=[int(x)-1 for x in input().split()]
    path[ui].append(vi)
    
s,t=[int(x)-1 for x in input().split()]
from collections import deque
q=deque()
q.append((s,0))

check=[[False]*n for x in [0,1,2]]
while q:
    
    p,num=q.popleft()
    if check[num%3][p]==True:
        continue
    if num%3!=0:
        for i in path[p]:
            q.append((i,num+1))
        check[num%3][p]=True
        continue
    elif p==t:
        print(num//3)
        import sys
        sys.exit()
    else:
        for i in path[p]:
            q.append((i,num+1))
        check[0][p]=True
print(-1)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10000000)

readline = sys.stdin.readline

N, M = map(int, readline().split())
uv = [list(map(int, readline().split())) for i in range(M)]
S, T = map(int, readline().split())

S, T = S - 1, T - 1

nodes = [{} for i in range(N)]
for u, v in uv:
    nodes[u - 1][v - 1] = 1

visited = [[False] * N for i in range(3)]

def kenken(u, rem):
    if rem != 3 and visited[rem][u]:
        return deque()
    
    if rem != 3:
        visited[rem][u] = True
    if rem > 0:
        a = deque()
        for v in nodes[u]:
            a.extend(kenken(v, rem - 1))
        return a
    else:
        return deque([u])
    

q = deque()

q.append([S, 0])

_count = -1
while len(q) != 0:
    u, count = q.popleft()

    ret = kenken(u, 3)
    if any(T == r for r in ret):
        _count = count + 1
        break
    q.extend([r, count + 1] for r in ret)


print(_count)

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline


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

    abcde = [list(map(int, input().split())) for i in range(edge_num)]

    for i in range(edge_num):
        a, b = abcde[i]
        graph_data[a].add(b)

    start, goal = map(int, input().split())
    visit_flg = [0] * (node_num + 1)
    visit_flg2 = [0] * (node_num + 1)
    visit_flg3 = [0] * (node_num + 1)
    visit_flg[start] = 1

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

    ans = 0

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

        if visit_flg[goal]:
            break

        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:
                    if i == 1 and visit_flg2[search_now_node]:
                        continue
                    elif i == 1:
                        visit_flg2[search_now_node] = 1
                    if i == 2 and visit_flg3[search_now_node]:
                        continue
                    elif i == 2:
                        visit_flg3[search_now_node] = 1
                    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

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

Solution (Python):
from collections import deque

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

G = dict()

for i in range(1, 3 * N + 1):
    G[i] = dict()

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

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

dist_S = [3 * N + 1] * (3 * N + 1)
dist_S[S] = 0


queue = deque([S])
while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if dist_S[p] + 1 < dist_S[q]:
            dist_S[q] = dist_S[p] + 1
            queue.append(q)

if dist_S[T] < 3 * N + 1:
    print(dist_S[T] // 3)
else:
    print(-1)

Solution (Python):
n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    u,v=map(int,input().split())
    graph[u-1].append(v-1)
s,t=map(int,input().split())
s=s-1
t=t-1
from collections import deque
que=deque([])
que.append(s)
check0=[-1]*n
check1=[-1]*n
check2=[-1]*n
check0[s]=0
while len(que)>0:
    now=que.popleft()
    for i in graph[now]:
        if check1[i]==-1:
            if check0[now]!=-1:
                check1[i]=check0[now]+1
                que.append(i)
        if check2[i]==-1:
            if check1[now]!=-1:
                check2[i]=check1[now]+1
                que.append(i)
        if check0[i]==-1:
            if check2[now]!=-1:
                check0[i]=check2[now]+1
                que.append(i)
if check0[t]==-1:
    print(-1)
else:
    print(check0[t]//3)

Solution (Python):
N, M = map(int, input().strip().split())

vs = [[] for _ in range(N + 1)]
for _ in range(M):
	v, u = map(int, input().strip().split())
	vs[v].append(u)

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

def search(vs, S, T):
	queue = [(S, 0)]
	dists = [[-1] * (N + 1) for _ in range(3)]
	while queue:
		n, d = queue.pop(0)
		d += 1
		dr = d % 3
		dists_tmp = dists[dr]
		for n2 in vs[n]:
			if dr == 0 and n2 == T:





				return d // 3
			if dists_tmp[n2] < 0:
				dists_tmp[n2] = d
				queue.append((n2, d))
	return -1

print(search(vs, S, T))

Solution (Python):
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(S)

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)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
m = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v = map(int, input().split())
    m[u].append(v)
S, T = map(int, input().split())

l = [[-1, -1, -1] for _ in range(N + 1)]

q = deque()
q.append((S, 0, 0))
while len(q):
    i, n, mod = q.popleft()
    for j in m[i]:
        if j == T and mod == 2:
            print((n + 1) // 3)
            exit()
        if l[j][(mod + 1) % 3] != -1:
            continue
        l[j][(mod + 1) % 3] = n + 1
        q.append((j, n + 1, (mod + 1) % 3))

print(-1)

Solution (Python):
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): 
	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


weight = [INF]*(N*3)
weight[S] = 0
q = [[0,S]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)

ans = weight[T]

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

Solution (Python):
import heapq
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)

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

dist=[[10**10 for i in range(3)] for i in range(N)]
dist[S][0]=0
q=[]
heapq.heappush(q,(dist[S][0],S,0))
while(len(q)>0):
    d,r,j=heapq.heappop(q)
    if dist[r][j]<d:
        continue
    for p in G[r]:
        if dist[p][(j+1)%3]>dist[r][j]+1:
            dist[p][(j+1)%3]=dist[r][j]+1
            heapq.heappush(q,(dist[p][(j+1)%3],p,(j+1)%3))

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

Solution (Python):
from collections import deque

N, M = map(int, input().split())
A, B = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)
S, T = map(int, input().split())

G = [set() for _ in range(N + 1)]
for x, y in zip(A, B):
    G[x].add(y)

INF = 10**10

dp = [[INF for j in range(3)] for i in range(N + 1)]

q = deque()
q.append((S, 0))
dp[S][0] = 0

while q:
    i, k = q.popleft()
    L = (k + 1) % 3
    for x in G[i]:
        if dp[x][L] == INF:
            dp[x][L] = dp[i][k] + (k + 1) // 3
            q.append((x, L))

ans = (
    -1 if dp[T][0] == INF else
    dp[T][0]
)

print(ans)

Solution (Python):

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())

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

dist = [[False]*3 for i in range(n)]
cnt = [[0]*3 for i in range(n)]
s, t = map(int, input().split())
s -= 1
t -= 1
q = deque()

q.append((s, 0, 0))
while q:
    now, d, c = q.popleft()
    if dist[now][d] and cnt[now][d] <= c:
        continue
    dist[now][d] = True
    cnt[now][d] = c
    next_d = (d+1)%3
    next_c = c+1
    for to in edges[now]:
        if not dist[to][next_d] or cnt[to][next_d] > c:
            q.append((to, next_d,next_c))
if dist[t][0]:
    print(cnt[t][0]//3)
else:
    print(-1)