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


"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    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]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    layers = [set() for _ in range(3)]
    
    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    if root not in layers[i]:
                        layers[i].add(root)
                        purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()

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

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

Solution (Python):
from heapq import heappush, heappop

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from collections import deque
n,m=map(int,input().split())
edges=[[] for i in range(n)]
for i in range(m):
    u,v=map(int,input().split())
    edges[u-1].append(v-1)
s,t=map(int,input().split())
inf=100000000000
score=[[inf]*3 for i in range(n)]
now=deque()
now.append(s-1)
score[s-1][0]=0
def bfs(dep,l):
    global n,m,edges,s,t,score,inf,now
    f=False
    for i in range(l):
        ne=now.popleft()
        for j in edges[ne]:
            if score[j][dep%3]==inf:
                score[j][dep%3]=dep
                now.append(j)
    l_ne=len(now)
    if l_ne:bfs(dep+1,l_ne)
bfs(1,1)
if score[t-1][0]!=inf:
    print(score[t-1][0]//3)
else:
    print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from collections import deque
n,m=map(int,input().split())
edges=[[] for i in range(n)]
for i in range(m):
    u,v=map(int,input().split())
    edges[u-1].append(v-1)
s,t=map(int,input().split())
inf=100000000000
score=[[inf]*3 for i in range(n)]
now=deque()
now.append(s-1)
score[s-1][0]=0
def bfs(dep,l):
    global n,m,edges,s,t,score,inf,now
    f=False
    for i in range(l):
        ne=now.popleft()
        for j in edges[ne]:
            if score[j][dep%3]==inf:
                score[j][dep%3]=dep
                now.append(j)
    l_ne=len(now)
    if l_ne:bfs(dep+1,l_ne)
bfs(1,1)
if score[t-1][0]!=inf:
    print(score[t-1][0]//3)
else:
    print(-1)

Solution (Python):
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    edges[u-1].append(v-1)

S, T = map(int, sys.stdin.readline().split())
S -= 1
T -= 1

visited = {}
q = deque()
q.append((S, 0))
d = -1
while q:
    s, c = q.popleft()
    if s in visited and (c % 3) in visited[s]:
        continue
    if s not in visited:
        visited[s] = set()
    visited[s].add(c % 3)
    for n in edges[s]:
        if n == T and c % 3 == 2:
            d = c + 1
            break
        q.append((n, c+1))

    if d % 3 == 0:
        break

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

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

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

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

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






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

def build_tree_dis(N, edge_list):

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

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

    
    leaves = []
    for i in range(N):
        if len(G[i]) == 1:
            leaves.append(i)

    return G

edges = build_tree_dis(N, query)

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

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

while len(pos) > 0:
    u, t = pos.popleft()
    t += 1
    j = t % 3
    for i in edges[u]:
        if ignore[i][j] == -1:
            ignore[i][j] = t
            pos.append([i, t])

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

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

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

    def dfs():
        q=deque([(0,S)])
        visited=[[False]*N for _ in range(3)]
        while len(q):
            
            d,e=q.popleft()
            
            if visited[d%3][e]:continue
            elif d%3==0:
                if e==T:
                    print(d//3)
                    return 
            visited[d%3][e]=True
            
            for ne in edge[e]:
                q.append((d+1,ne))
        print(-1)
    dfs()
    




if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
def bfs(start, g, visited, goal):
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        for next_node in g[curr_node]:
            if visited[next_node] >= 0: continue
            visited[next_node] = visited[curr_node] + 1
            if next_node == goal: return
            q.append(next_node)


n,m = map(int, input().split())
g = [ [] for _ in range(3*n)]

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

s,t = map(int, input().split())
visited = [-3]*(3*n)
bfs(s*3-3, g, visited, t*3-3)
print(visited[t*3-3]//3)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    dist = [[f_inf] * 3 for _ in range(n)]
    que = deque([])
    que.append([s - 1, 0])
    dist[s - 1][0] = 0
    while que:
        v, l = que.popleft()
        for u in edge[v]:
            nl = (l + 1) % 3
            if dist[u][nl] == f_inf:
                dist[u][nl] = dist[v][l] + 1
                que.append([u, nl])

    res = dist[t - 1][0]
    print(-1 if res == f_inf else res // 3)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque

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
ctr = [[INF] * (N + 1) for _ in range(3)]
ctr[0][S] = 0
stack = deque()
stack.append((0, S))
while stack:
    i, u = stack.popleft()
    j = (i + 1) % 3
    for v in graph[u]:
        if ctr[j][v] > ctr[i][u] + 1:
            ctr[j][v] = ctr[i][u] + 1
            stack.append((j, v))
            
if ctr[0][T] < INF:
    print(ctr[0][T] // 3)
else:
    print(-1)

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

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

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

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

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

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

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

Solution (Python):
from collections import defaultdict, deque

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

'''
頂点を%3で考える(1つの頂点にを3つに分解する)
(u,0)->(v,1)
(v,1)->(u,2)
(u,2)->(v,0)
'''

S, T = map(int, input().split())
q = deque([[S, 0]])
dist = [[-3]*3 for _ in range(N+1)]
dist[S][0] = 0
while q:
    u, c = q.popleft()
    for v in e[u]:
        step = (c+1) % 3
        if dist[v][step] < 0:
            dist[v][step] = c+1
            q.append([v, c+1])

print(dist[T][0]//3)

Solution (Python):
from collections import defaultdict, deque


def kenkenpa(s, visited):
    res = []
    for v1 in e[s]:
        if visited[v1][1]:
            continue
        visited[v1][1] = True
        for v2 in e[v1]:
            if visited[v2][2]:
                continue
            visited[v2][2] = True
            for v3 in e[v2]:
                if visited[v3][0]:
                    continue
                visited[v3][0] = True
                res.append(v3)
    return res


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

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

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for i in range(n+1)]
    for _ in range(m):
        u,v = map(int,ipt().split())
        way[u].append(v)
    dist = [[-1]*3 for _ in range(n+1)]
    s,t = map(int,ipt().split())
    dist[s][0] = 0
    q = queue.Queue()
    q.put((s,0))
    while not q.empty():
        pi,pd = q.get()
        for i in way[pi]:
            if dist[i][(pd+1)%3] == -1:
                dist[i][(pd+1)%3] = (pd+1)//3
                q.put((i,pd+1))
    print(dist[t][0])

    return

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
INF = 10 ** 10


def dijkstra(n, adj, s, t):
    dist = [INF for _ in range(n)]
    dist[s] = 0
    h = [(0, s)]
    while len(h) > 0:
        d, node = heapq.heappop(h)
        for next_node in adj[node]:
            next_d = d + 1
            if next_d < dist[next_node]:
                dist[next_node] = next_d
                heapq.heappush(h, (next_d, next_node))
    return dist[t]


def main():
    N, M = list(map(int, input().split(' ')))
    adj = [[] for _ in range(3 * N)]
    for _ in range(M):
        u, v = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[3 * u].append(3 * v + 1)
        adj[3 * u + 1].append(3 * v + 2)
        adj[3 * u + 2].append(3 * v)
    S, T = list(map(lambda x: int(x) - 1, input().split(' ')))
    d = dijkstra(3 * N, adj, 3 * S, 3 * T)
    if d == INF:
        print(-1)
    else:
        print(d // 3)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    G = [set() for i in range(N)]
    G2 = [set() for i in range(N*3)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        G[u].add(v)
    S, T = map(int, input().split())
    S -= 1
    T -= 1

    import collections
    q = collections.deque()
    q.append((S, 0))
    D = [-1]*N*3
    D[3*S] = 0
    while(q):
        x, d = q.popleft()
        for y in G[x]:
            if D[y*3+(d+1) % 3] < 0:
                
                q.append((y, d+1))
                D[y*3 + (d+1) % 3] = d+1

    if D[T*3] > 0:
        print(D[T*3] // 3)

    else:
        print(-1)


main()

Solution (Python):
import sys
from collections import *
I=sys.stdin.readlines()
N,M=map(int,I[0].split())
E=[]
for i in range(M):
  E.append(list(map(lambda x:x-1,(list(map(int,I[i+1].split()))))))
S,T=map(int,I[M+1].split())
G=[[] for i in range(3*N)]
for i in range(M):
  G[E[i][0]].append(E[i][1]+N)
  G[E[i][0]+N].append(E[i][1]+N+N)
  G[E[i][0]+N+N].append(E[i][1])
D=deque()
Z=set()
def qao(x):
  global D,Z
  if x in Z:
    return False
  D.append(x)
  Z.add(x)
  return True

def bfs():
  global D,G,N
  v=0
  for i in range(len(D)):
    v=D.popleft()
    for j in range(len(G[v])):
      qao(G[v][j])
  return len(D)==0

qao(S-1)
for i in range(3*N):
  bfs()
  if T-1 in Z:
    print((i+1)//3)
    exit()
print(-1)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, readline().split())
        G[u - 1].append(v - 1)
    S, T = map(int, readline().split())
    S -= 1
    T -= 1

    dist = [[-1] * 3 for _ in range(N)]
    dist[S][0] = 0
    queue = deque([(S, 0)])
    while queue:
        v, step = queue.popleft()
        if step == 0 and v == T:
            break

        for nv in G[v]:
            if dist[nv][(step - 1) % 3] != -1:
                continue
            dist[nv][(step - 1) % 3] = dist[v][step] + 1
            queue.append((nv, (step - 1) % 3))

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, readline().split())
        G[u - 1].append(v - 1)
    S, T = map(int, readline().split())
    S -= 1
    T -= 1

    dist = [[-1] * 3 for _ in range(N)]
    dist[S][0] = 0
    queue = deque([(S, 0)])
    while queue:
        v, step = queue.popleft()
        if step == 0 and v == T:
            break

        for nv in G[v]:
            if dist[nv][(step - 1) % 3] != -1:
                continue
            dist[nv][(step - 1) % 3] = dist[v][step] + 1
            queue.append((nv, (step - 1) % 3))

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

n, m = map(int, input().split())
g = [[] for _ in range(3*n)]
for i 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

from collections import deque
q = deque()
visit = [-1]*(3*n)
q.append(s)
visit[s] = 0
while q:
    u = q.popleft()
    for v in g[u]:
        if visit[v] == -1:
            visit[v] = visit[u]+1
            q.append(v)
if visit[t] == -1:
    print(-1)
else:
    print(visit[t]//3)

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

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

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

print(dist[t][0])

Solution (Python):


import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  



N, M = read_ints()
graph = defaultdict(lambda: [])
for _ in range(M):
    u, v = mina(*read_ints())
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)

S, T = mina(*read_ints())

pq = deque([])
D = [-3] * (N * 3)
D[S] = 0
pq.append((0, S))  
while pq:
    d, v = pq.popleft()
    for to in graph[v]:
        if D[to] != -3:
            continue
        D[to] = d + 1
        pq.append((D[to], to))

print(D[T] // 3)

Solution (Python):
import heapq

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

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

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

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

D=[10**6 for i in range(3*N)]
D[~-S]=0
A=[(0,~-S)]
heapq.heapify(A)

while len(A)>0:
  d,v=heapq.heappop(A)
  if D[v]<d:
    continue
  for i in L[v]:
    if D[i]>D[v]+1:
      D[i]=D[v]+1
      heapq.heappush(A,(D[v]+1, i))

print(D[~-T]//3 if D[~-T]!=10**6 else -1)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
K = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    K[a-1].append(b-1)
S, T = map(int, input().split())
used = [[0]*3 for _ in range(N)]

q = deque([[S-1, 0, 0]])
used[S-1][0] = 1
ans = [[-3]*3 for _ in range(N)]
while(len(q)>0):
    u, v, c = q.popleft()
    v_n = (v + 1) % 3
    for j in K[u]:
        if used[j][v_n] == 0:
            used[j][v_n] = 1
            ans[j][v_n] = c+1
            q.append([j, v_n, c+1])

print(ans[T-1][0]//3)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10000000)

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

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

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

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

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

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

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
G=[[] for i in range(3*n)]
for i in range(m):
  u,v=map(int,input().split())
  for j in range(3):
    G[u+n*j-1].append(v+n*((j+1)%3)-1)
s,g=map(int,input().split())
s=s-1
g=g-1
D=deque([s])
V=[0]*3*n
V[s]=1
DD=[0]*3*n
while len(D)>0:
  x=D[0]
  D.popleft()
  for y in G[x]:
    if V[y]==0:
      V[y]=1
      D.append(y)
      DD[y]=DD[x]+1
if DD[g]==0:
  print(-1)
else:
  print(DD[g]//3)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



def main():
    
    
    

    

    
    
    
    
    
    
    

    

    N, M = map(int, readline().split())
    to = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, readline().split())
        u-=1
        v-=1
        to[u].append(v)
    S, T = map(int, readline().split())
    S-=1
    T-=1

    INF = int(1e9)
    
    dist = [[INF for _ in range(3)] for _ in range(N)]     

    
    from collections import deque
    dq = deque()
    dq.append((S, 0))
    dist[S][0] = 0
    while len(dq)>0:
        v, r = dq.popleft() 
        for nxv in to[v]:
            nxr = (r+1)%3
            if dist[nxv][nxr] != INF:
                continue
            dist[nxv][nxr] = dist[v][r] + 1
            dq.append((nxv, nxr))

    if dist[T][0] == INF:
        print(-1)
    else:
        print(dist[T][0]//3)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N,M,*f = map(int, open(0).read().split())
uv = [f[i:i+2] for i in range(0, len(f)-2, 2)]
S = f[-2]
T = f[-1]
connected = [[] for _ in range(N+1)]
for u, v in uv:
    connected[u].append(v)
dist = [[-1] * 3 for _ in range(N+1)]
dist[S][0] = 0
ans = 0
d = deque([(S,0)])
while d:
    temp = d.popleft()
    for edge in connected[temp[0]]:
        if edge == T and temp[1] == 2:
            print((dist[temp[0]][2]+1)//3)
            break
        else:
            if dist[edge][(temp[1]+1)%3] < 0:
                dist[edge][(temp[1]+1)%3] = dist[temp[0]][temp[1]] + 1
                d.append((edge,(temp[1]+1)%3))
    else:
        continue
    break
else:
    print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(300000)
from collections import deque

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


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

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

Solution (Python):
from collections import deque
def bfs(G,s,N):
    dist=[[-1]*N for i in range(3)]
    d=deque()
    dist[0][s]=0
    d.append((0,s))
    while(len(d)!=0):
        p,v=d.popleft()
        for np,nv in G[p][v]:
            if(dist[np][nv]!=-1):
                continue
            dist[np][nv]=dist[p][v]+1
            d.append((np,nv))
    return dist

N,M=map(int,input().split())
G=[[[] for i in range(N)] for i in range(3)]
for i in range(M):
    u,v=map(lambda x:int(x)-1,input().split())
    G[0][u].append((1,v))
    G[1][u].append((2,v))
    G[2][u].append((0,v))
S,T=map(lambda x:int(x)-1,input().split())
dist=bfs(G,S,N)
ans=dist[0][T]
print(ans//3 if ans!=-1 else ans)

Solution (Python):
n,m=map(int,input().split())
uv=[list(map(int, input().split())) for _ in range(m)]
s,t=map(int,input().split())

graph = [[] for _ in range(n)]
for v in uv:
    graph[v[0]-1].append(v[1]-1)

s-=1
t-=1

is_checked=[[0]*3 for _ in range(n)]
is_checked[s][0]=1

ans=-1

from collections import deque
q=deque()
q.append([s,0])

while q:
    v, cnt=q.popleft()
    if v==t and cnt%3==0:
        ans=cnt//3
        break
    for i in graph[v]:
        if is_checked[i][(cnt+1)%3]==0:
            q.append([i, cnt+1])
            is_checked[i][(cnt+1)%3]=1

print(ans)