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

Solution code:
n, m = map(int, input().split())

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

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

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

from heapq import heappush, heappop


def dijkstra(graph: list, n: int, start: int, INF: int = float('inf')) -> list:
    # graph[node] = [(cost, to)]
    dist = [INF] * n
    num = [0] * n

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        _, v_from = heappop(heap)
        for v_to in graph[v_from]:
            dist_cand = dist[v_from] + 1
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist
    # dist = [costs to nodes]


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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(4100000)

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

already_reach = [-1]*(N+1)
already_reach_1st = [-1]*(N+1)
already_reach_2nd = [-1]*(N+1)
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split(' '))
    graph[u].append(v)
S,T = map(int,input().split(' '))

next_list = []
def search(S_list,current_count=0):
    next_list = []
    for s in S_list:
        for i1 in graph[s]:
            #print(already_reach_1st)
            if already_reach_1st[i1] != -1:
                continue
            already_reach_1st[i1] = 0
            for i2 in graph[i1]:
                #print(already_reach_2nd)
                if already_reach_2nd[i2] != -1:
                    continue
                already_reach_2nd[i2] = 0
                for i3 in graph[i2]:
                    if already_reach[i3] == -1: #はじめての到達
                        already_reach[i3] = current_count+1
                        next_list.append(i3)
    if len(next_list) > 0:
        search(next_list,current_count+1)
search([S])
print(already_reach[T])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
data=[[] for i in range(3*n+1)]
for i in range(m):
    u,v=map(int,input().split())
    data[u].append(v+n)
    data[u+n].append(v+2*n)
    data[u+2*n].append(v)
s,t=map(int,input().split())
inf=float("inf") 
flag=[inf]*(3*n+1)
flag[s]=0
que=[s]
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==inf:
                flag[v]=flag[u]+1
                h.append(v)
    que=h
if flag[t]==inf:
    print(-1)
else:
    print(flag[t]//3)

Submission status: Accepted

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


n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    _from, to = map(int, input().split())
    edges[_from-1].append(to-1)

start, goal = map(int, input().split())

todo = deque([])
seen = [[False] * n for i in range(3)]
seen[0][start-1] = True
for to in edges[start-1]:
    dim = 1
    dist = 1
    todo.append([to, dim, dist])

while todo:
    node, dim, dist = todo.popleft()
    if seen[dim][node]:
        continue
    seen[dim][node] = True
    dim += 1
    if dim == 3:
        dim = 0
    for to in edges[node]:
        if seen[dim][to]:
            continue
        todo.append([to, dim, dist+1])
        if to == goal-1 and dim == 0:
            print((dist+1)//3)
            exit()

print(-1)

Submission status: Accepted

Solution code:
from collections import deque as dq
n,m = list(map(int,input().split()))
graph = [[] for i in range(n)]
for i in range(m):
    a,b = list(map(int,input().split()))
    a -= 1;b -= 1
    graph[a].append(b)
s,t = list(map(int,input().split()))
s -= 1;t -= 1
check = [[-1,-1,-1] for i in range(n)]
que = dq()
que.appendleft([s,0])
check[s][0] = 0
while (que):
    v,l = que.pop()
    for i in graph[v]:
        if check[i][(l+1)%3] == -1:
            que.appendleft([i,(l+1)%3])
            check[i][(l+1)%3] = check[v][l] + 1
if check[t][0] == -1:
    print(-1)
else:
    print(check[t][0] // 3)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
G = [[] for _ in range(n)]
for x, y in LIR(m):
    G[x - 1] += [y - 1]

dist = [[INF] * n for _ in range(3)]
s, t = LI()
dist[0][s - 1] = 0
dq = deque([(0, s - 1)])
while dq:
    cost, u = dq.popleft()
    for v in G[u]:
        if cost + 1 < dist[(cost + 1) % 3][v]:
            dist[(cost + 1) % 3][v] = cost + 1
            dq += [(cost + 1, v)]


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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    x, y = LI()
    G[x - 1] += [y - 1]

dist = [[INF] * n for _ in range(3)]
s, t = LI()
dist[0][s - 1] = 0
dq = deque([(0, s - 1)])
while dq:
    cost, u = dq.popleft()
    for v in G[u]:
        if cost + 1 < dist[(cost + 1) % 3][v]:
            dist[(cost + 1) % 3][v] = cost + 1
            dq += [(cost + 1, v)]


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

Submission status: Accepted

Solution code:
from collections import deque
import sys
n,m=map(int,input().split())
g=[[] for _ in range(3*n)]
for _ in range(m):
  u,v=map(int, sys.stdin.readline().split())
  u-=1
  v-=1
  g[u].append(n+v)
  g[u+n].append(v+2*n)
  g[u+2*n].append(v)
s,t=map(int,input().split())
s-=1
t-=1
vit=set([s])
ans=[-3]*3*n
q=deque([s])
ans[s]=0
while q:
  a=q.popleft()
  for b in g[a]:
    if b in vit:
      continue
    vit.add(b)
    ans[b]=ans[a]+1 
    q.append(b)
print(ans[t]//3)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

Edge = [[] for _ in range(3*N)]

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

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

Q = deque([S])
visited = set([S])
dist = [-3]*(3*N)
dist[S] = 0


while Q:
    vn = Q.pop()
    for vf in Edge[vn]:
        if vf in visited:
            continue
        visited.add(vf)
        dist[vf] = dist[vn] + 1
        Q.appendleft(vf)

print(dist[T]//3)

Submission status: Accepted

Solution code:
#editorial参照
import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int, input().split( ))
Ad = [[[] for _ in range(3)] for i in range(n)]

#移動回数込みで移動可能かの情報をグラフの接続として記録
for i in range(m):
    ui,vi = map(int,input().split( ))
    ui -= 1
    vi -= 1
    Ad[ui][0].append((vi,1))
    Ad[ui][1].append((vi,2))
    Ad[ui][2].append((vi,0))


s,t = map(int, input().split( ))
s -= 1
t -= 1
Q = deque()
Q.append((s,0))
Visit = [[-1 for _ in range(3)] for i in range(n)]
Visit[s][0] = 0
while Q:
    v,i = Q.popleft()
    for u,j in Ad[v][i]:
        if Visit[u][j]<0:
            Visit[u][j] = Visit[v][i] + 1
            Q.append((u,j))
        if u==t and j==0:
            Q.clear()
            break
#print(Visit)
print(Visit[t][0]//3)

Submission status: Accepted

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

n, m = map(int, input().split())
INF = 10**9
to = [ [] for _ in range(n) ]
dist = [ [INF]*n for _ in range(3) ]
for _ in range(m):
    u, v = map(int, input().split())
    to[u-1].append(v-1)
s, t = map(int, input().split())
s -= 1; t -= 1

dist[0][s] = 0
que = deque([(s, 0)])
while que:
    u, prv = que.popleft()
    d = dist[prv][u]
    cur = (prv+1) % 3
    if prv == 2:
        d += 1
    for v in to[u]:
        if dist[cur][v] != INF:
            continue
        que.append((v, cur))
        dist[cur][v] = d
print( dist[0][t] if dist[0][t] < INF else -1 )

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(3*n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[3*u].append(3*v+1)
        E[3*u+1].append(3*v+2)
        E[3*u+2].append(3*v)
    s,t=map(int,input().split())
    s-=1; t-=1

    # BFS (startは0、goalは3n-3)
    from collections import deque
    d=[-1]*(3*n)
    d[3*s]=0
    Q=deque()
    Q.append(3*s)
    while(Q):
        v=Q.popleft()
        for nv in E[v]:
            if(d[nv]!=-1): continue
            d[nv]=d[v]+1
            Q.append(nv)
    ans=d[3*t]
    print(ans//3 if(ans!=-1) else -1)
resolve()

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
node = [[10**9]*3 for i in range(N)]
KENPA = 3
side = [[]for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    side[u-1].append(v-1)
S,T = map(int,input().split())
node[S-1][2] = 0
queue = deque([[S-1,2]])
while queue:
    x,y = queue.popleft()
    y2 = (y+1)%KENPA
    for i in side[x]:
        if node[i][y2] > node[x][y]+1:
            node[i][y2] = node[x][y]+1
            queue.append([i,y2])
if node[T-1][2] == 10**9:
    print(-1)
else:
    print(node[T-1][2] // 3)

Submission status: Accepted

Solution code:
import collections
N,M = map(int,input().split())
edge = collections.defaultdict(list)
for _ in range(M):
    u,v = map(int,input().split())
    edge[u-1].append(v-1)
S,T = map(int,input().split())
dp = [[-3 for _ in range(3)] for _ in range(N)]
dp[S-1][0] = 0
q = collections.deque()
q.append((S-1,0))
while q:
    p,step = q.popleft()
    next_step = (step+1)%3
    for e in edge[p]:
        if dp[e][next_step] == -3:
            dp[e][next_step] = dp[p][step] + 1
            q.append((e,next_step))
            if e == T-1 and next_step == 0:
                break
print(dp[T-1][0] // 3)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            if W[ne] == -1:
                W[ne] = nowv+1
                len[ne] = nowlen+1
                que.append(ne)
    return W
#############################################################

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M = LI()
V = [[] for i in range(3*N)]
#print(V)
for i in range(M):
    u, v = LI()
    V[u-1].append(N+v-1)
    V[N+u-1].append(2*N+v-1)
    V[2*N+u-1].append(v-1)
cou = []
S, T = LI()
#print(V)

cou = bfs(3*N, S-1, V)
#print(cou)
ans = cou[T-1]//3
print(ans)

Submission status: Accepted

Solution code:
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue



# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())


def main():
    n, m = map(int, raw_input().split())
    G = [[] for i in range(n+1)]
    ss = set()
    for i in range(m):
        a, b = map(int, raw_input().split())
        G[a].append(b)
    s, t = map(int, raw_input().split())
    t = t<<2
    q = deque()
    q.append((s<<2, 0))
    ss.add(s<<2)
    while q:
        st, step = q.popleft()
        point, mod = st>>2, st&3
        # print point, step, mod
        if st == t:
            print step/3
            return

        for adj in G[point]:
            new_st = (adj<<2) + (mod+1)%3
            if new_st not in ss:
                ss.add(new_st)
                q.append((new_st, step+1))
    print -1

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,*UV,S,T = map(int,read().split())

it = iter(UV)
G = [[] for _ in range(1+N+N+N)]
for x, y in zip(it, it):
    x1=x+N; x2=x1+N;
    y1=y+N; y2=y1+N;
    G[x].append(y1)
    G[x1].append(y2)
    G[x2].append(y)

INF = 10 ** 15
dist = [INF] * (N+N+N+1)
dist[S] = 0
q = [S]
while q:
    qq = []
    for x in q:
        for y in G[x]:
            if dist[y] != INF:
                continue
            qq.append(y)
            dist[y] = dist[x] + 1
            if y == T:
                break
    q = qq

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)

Submission status: Accepted

Solution code:
from itertools import count
N,M = map(int,input().split())

adj = [list() for _ in range(N)]


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

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

visited = [False]*(N*3)
visited[S] = True
q = [S]

for step in count(1):
    offset = N*(step % 3)
    nq = []
    for u in q:
        for v in adj[u]:
            if not visited[v+offset]:
                nq.append(v)
                visited[v+offset] = True
    q = nq

    if visited[T] or not q:
        break
if visited[T]:
    print(step//3)
else:
    print(-1)

Submission status: Accepted

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

n,m=map(int,input().split())
G=[[] for _ in range(3*(n+1))]
for _ in range(m):
    u,v=map(int,input().split())
    G[3*u].append(3*v+2)
    G[3*u+1].append(3*v)
    G[3*u+2].append(3*v+1)
s,t=map(int,input().split())

Q=deque()
Q.append(s*3)
D=[-3 for _ in range(3*(n+1))]
D[s*3]=0

while Q:
    q=Q.popleft()
    for i in G[q]:
        if D[i]==-3:
            D[i]=D[q]+1
            Q.append(i)

print(D[t*3]//3)

Submission status: Accepted

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

N, M = map(int, input().split())
# N-1辺表示をグラフ表示に
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
S, T = map(lambda x:int(x)-1, input().split())


q = {S}
checked = [False]*N
checked[S] = True

ok = False
c = 0
while q:
    c += 1
    qq = set()
    if c % 3 == 0:
        for p in q:
            for np in graph[p]:
                if np == T:
                    ok = True
                    break
                if not checked[np]:
                    qq.add(np)
                    checked[np] = True
    else:
        for p in q:
            for np in graph[p]:
                qq.add(np)
    if ok:
        break
    q = qq

if ok:
    print(c//3)
else:
    print(-1)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, S, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.dist = [INF] * N
		self.visit = ["No"] * N
		self.Q.put(S)
		self.dist[S] = 0
		self.visit[S] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"

#処理内容
def main():
	#入力処理
	N, M = getlist()
	G = Graph()
	for i in range(M):
		u, v = getlist()
		G.add_edge(u - 1, v - 1 + N)
		G.add_edge(u - 1 + N, v - 1 + 2 * N)
		G.add_edge(u - 1 + 2 * N, v - 1)

	S, T = getlist()
	S -= 1
	T -= 1
	#BFS
	BF = BFS(G, S, 3 * N)
	D = BF.dist
	if D[T] == INF:
		print(-1)
	else:
		print(D[T] // 3)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,*UV,S,T = map(int,read().split())

it = iter(UV)
graph = [[] for _ in range(1+N+N+N)]
for x,y in zip(it,it):
    x1=x+N; x2=x1+N
    y1=y+N; y2=y1+N
    graph[x].append(y1)
    graph[x1].append(y2)
    graph[x2].append(y)   

INF = 10**15
dist = [INF] * (N+N+N+1)
dist[S] = 0
q = [S]
while q:
    qq = []
    for x in q:
        for y in graph[x]:
            if dist[y] != INF:
                continue
            qq.append(y)
            dist[y] = dist[x] + 1
            if y == T:
                break
    q = qq

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,*UV,S,T = map(int,read().split())

it = iter(UV)
graph = [[] for _ in range(1+N+N+N)]
for x,y in zip(it,it):
    x1=x+N; x2=x1+N
    y1=y+N; y2=y1+N
    graph[x].append(y1)
    graph[x1].append(y2)
    graph[x2].append(y)   

INF = 10**15
dist = [INF] * (N+N+N+1)
dist[S] = 0
q = [S]
while q:
    qq = []
    for x in q:
        for y in graph[x]:
            if dist[y] != INF:
                continue
            qq.append(y)
            dist[y] = dist[x] + 1
    q = qq

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
UVST = list(map(int,read().split()))
S,T = UVST[-2:]
UV = UVST[:-2]; U = UV[::2]; V = UV[1::2]

graph = [[] for _ in range(1+N+N+N)]
for x,y in zip(U,V):
    x1=x+N; x2=x1+N
    y1=y+N; y2=y1+N
    graph[x].append(y1)
    graph[x1].append(y2)
    graph[x2].append(y)   

INF = 10**15
dist = [INF] * (N+N+N+1)
dist[S] = 0
q = [S]
while q:
    qq = []
    for x in q:
        for y in graph[x]:
            if dist[y] != INF:
                continue
            qq.append(y)
            dist[y] = dist[x] + 1
    q = qq

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
L = [[int(u) for u in input().split()] for i in range(M)]
S,T = map(int, input().split())

edge = [[] for i in range(N+1)]
for i in range(M):
    edge[L[i][0]].append(L[i][1])
    
q = [S]
INF = 10**9
visited = [[INF+1, INF+1, INF+1] for i in range(N+1)]
visited[S][0] = 0
cnt = 1
while len(q) > 0:
    length = len(q)
    for j in range(length):
        temp = q.pop(0)
        for i in range(len(edge[temp])):
            if visited[edge[temp][i]][cnt%3] > INF:
                q.append(edge[temp][i])
                visited[edge[temp][i]][cnt%3] = cnt
    cnt += 1
    
if visited[T][0] < INF:
    print(visited[T][0]//3)
else:
    print(-1)

Submission status: Accepted

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

connection=[[] for i in range(3*n)]
for i in range(m):
  connection[l[i][0]-1].append(l[i][1]-1+n)
  connection[l[i][0]-1+n].append(l[i][1]-1+2*n)
  connection[l[i][0]-1+2*n].append(l[i][1]-1)

def bfs(v):
  distance=[-1]*(3*n)
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*(3*n)
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=3*n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

if bfs(s-1)[t-1]==-1 or bfs(s-1)[t-1]%3!=0:
  print(-1)
else:
  print(bfs(s-1)[t-1]//3)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]
from collections import deque
vs = set()
def bfs(v,d,t,N):
    queue=deque([v])
    dist = [0] * (N+1)
    while True:
        if len(queue) == 0:
            break
        v = queue.popleft()
        for u in d[v]:
            if u in vs:
                continue
            vs.add(u)
            dist[u] = dist[v] + 1
            if u == t:
                return dist[u]//3
            queue.append(u)
    return -1

d = [set() for _ in range(3*N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(N+b)
    d[N+a].add(2*N+b)
    d[2*N+a].add(b)

s, t = [int(x) for x in input().strip().split(" ")]
print(bfs(s, d, t, 3*N+1))

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    s,e=map(int,input().split())
    graph[s-1].append(e+n-1)
    graph[s+n-1].append(e+2*n-1)
    graph[s+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
queue=deque([s])
length=0
dist=[-1]*(3*n)
dist[s]=0
while queue:
    v=queue.popleft()
    for i in graph[v]:
        if dist[i]!=-1:continue
        dist[i]=dist[v]+1
        queue.append(i)
print(dist[t]//3)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    s,e=map(int,input().split())
    graph[s-1].append(e+n-1)
    graph[s+n-1].append(e+2*n-1)
    graph[s+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
queue=deque([s])
length=0
dist=[-1]*(3*n)
dist[s]=0
while queue:
    v=queue.popleft()
    for i in graph[v]:
        if dist[i]!=-1:continue
        dist[i]=dist[v]+1
        queue.append(i)
print(dist[t] if dist[t]==1 else dist[t]//3)

Submission status: Accepted

Solution code:
def main():
	from collections import deque
	N,M,*L,S,T = map(int,open(0).read().split())
	G = [[] for _ in range(N)]
	step = [False]*(3*N)
	step[(S-1)*3] = True
	for u,v in zip(*[iter(L)]*2):
		G[u-1].append(v-1)
	q = deque([(S-1,0)])
	while q:
		cur,d = q.popleft()
		for nxt in G[cur]:
			if nxt==T-1 and (d+1)%3==0:
				print((d+1)//3)
				exit()
			if not step[nxt*3+(d+1)%3]:
				step[nxt*3+(d+1)%3] = True
				q.append((nxt,d+1))
	print(-1)
	
if __name__=="__main__":main()

Submission status: Accepted

Solution code:
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
step = [0 for _ in range(N)]
step[S-1] = 1
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if not step[nxt] & 1<<((d+1)%3):
			step[nxt] |= 1<<(d+1)%3
			q.append((nxt,d+1))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
step = [False for _ in range(3*N)]
step[(S-1)*3] = 0
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if not step[nxt*3+(d+1)%3]:
			step[nxt*3+(d+1)%3] = True
			q.append((nxt,d+1))
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
step = [[-1]*3 for _ in range(N)]
step[S-1][0] = 0
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if step[nxt][(d+1)%3] < 0:
			step[nxt][(d+1)%3] = d+1
			q.append((nxt,d+1))
print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
graph = [[] for _ in range(n)]
for u, v in LIR(m):
    graph[u - 1] += [v - 1]


s, t = LI()
dist = [[INF for _ in range(3)] for _ in range(n)]
dist[s - 1][0] = 0
que = deque([(s - 1, 0)])
while que:
    cur, cost = que.popleft()
    for nxt in graph[cur]:
        if cost + 1 < dist[nxt][(cost + 1) % 3]:
            dist[nxt][(cost + 1) % 3] = cost + 1
            que += [(nxt, cost + 1)]



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

Submission status: Accepted

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

g = [set() for _ in range(3 * n)]

for u, v in uv:
    a = u - 1
    b = v - 1
    g[a].add(n + b)
    g[n+a].add(n*2 + b)
    g[n*2+a].add(b)

#print(g)

s -= 1
t -= 1
ans = 0
temp = set()
temp.add(s)
while 1:
    ans += 1
    next = set()
    for x in temp:
        for y in g[x]:
            next.add(y)
        g[x] = []
    if len(next) == 0:
        print(-1)
        exit()
    if t in next:
        print(ans // 3)
        exit()
    temp = next

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline


class Data :
    def __init__():
        pass
    def __init__(self, pos, step, cost):
        self.pos = pos
        self.step = step
        self.cost = cost
    def __lt__(self, right):
        return self.cost < right.cost

def dijkstra(N, S, T, edges):
    inf = 10 ** 9 + 7
    dis = []
    for i in range(N + 1):
        dis.append([inf, inf, inf])

    que = []
    dis[S][0] = 0
    heappush(que, Data(S, 0, 0))
    while (len(que)):
        now_d = heappop(que)
        if dis[now_d.pos][now_d.step] < now_d.cost:
            continue

        for edge in edges[now_d.pos] :
            next_d = Data(edge[0], (now_d.step + 1) % 3, now_d.cost + edge[1])
            if dis[next_d.pos][next_d.step] > next_d.cost:
                dis[next_d.pos][next_d.step] = next_d.cost
                heappush(que, next_d)
    
    if (dis[T][0] == 10 ** 9 + 7):
        return -1
    else :
        return dis[T][0] // 3

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

Submission status: Accepted

Solution code:


import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


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

graph = [[] for _ in range(3*N)]

for i in range(M):
	u, v = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u%(3*N)].append((v + N)%(3*N))
	graph[(u + N) % (3 * N)].append((v+2*N)%(3*N))
	graph[(u + 2*N) % (3 * N)].append(v % (3 * N))
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print(dist[T]//3)
else:
	print(-1)