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())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

l = [[] for u in range(n + 1)]
for u, v in uv:
    l[u].append(v)

def bfs(v):
    q = [(x, 0) for x in list(v)]
    index = 0
    ret = set()
    while len(q) > index:
        x, step = q[index]
        index += 1
        if step == 3:
            ret.add(x)
            continue
        for y in l[x]:
            next = (y, step + 1)
            if next not in visited:
                visited.add(next)
                q.append(next)
    return ret

v = set([s])
visited = set([(s, 0)])
ret = 0
while True:
    v2 = bfs(v)
    if len(v2) == 0:
        ret = -1
        break
    ret += 1
    if t in v2:
        break
    v = v2

print(ret)

Submission status: Accepted

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

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())
queue = deque()
queue.append((S, 0))
visited = [[False] * 3 for _ in range(N+1)]
while queue:
    u, d = queue.popleft()
    if visited[u][d % 3]:
        continue
    visited[u][d % 3] = True
    if d % 3 == 0 and u == T:
        print(d // 3)
        exit()
    for v in G[u]:
        queue.append((v, d+1))
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,m=map(int,input().split())
u=[list(map(int,input().split())) for i in range(m)]
s,t=map(int,input().split())
dic=[[] for i in range(n+1)]
for i in range(m):
    a,b=u[i]
    dic[a].append(b)
# print(dic)
itta=[[0]*3 for i in range(n+1)]
d=deque([[s,0]])
itta[s][0]=1
itta[t][0]=2
while d:
    tmp=d.popleft()
    
    # print(tmp)

    p,cnt=tmp
    for i in dic[p]:
        if itta[i][(cnt+1)%3]==1:
            continue
        elif itta[i][(cnt+1)%3]==2:
            print((cnt+1)//3)
            quit()
        else:
            itta[i][(cnt+1)%3]=1
            d.append([i,cnt+1])
    # print(itta)
print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

from collections import deque
def BFS(N, graph, start):
    d = [-1 for i in range(N)]
    Q = deque([])
    Q.append(start)
    d[start] = 0
    while Q:
        v = Q.popleft()
        for u in graph[v]:
            if d[u] == -1:
                d[u] = d[v] + 1
                Q.append(u)
    return d

N, M = (int(i) for i in input().split())
graph = [[] for i in range(3*N)]
for i in range(M):
    a, b = (int(i) for i in input().split())
    graph[3*(a-1)].append(3*(b-1) + 1)
    graph[3*(a-1) + 1].append(3*(b-1) + 2)
    graph[3*(a-1) + 2].append(3*(b-1))

S, T = (int(i) for i in input().split())
ans = BFS(3*N, graph, 3*(S-1))
print(ans[3*(T-1)]//3)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
path=[[] for i in range(n*3+3)]
seen=[0]*(3*n)
for i in range(m):
  u,v=map(int,input().split())
  path[3*(u-1)].append(3*(v-1)+1)
  path[3*(u-1)+1].append(3*(v-1)+2)
  path[3*(u-1)+2].append(3*(v-1))
s,t=map(int,input().split())
s-=1
t-=1
q=deque()
q.append(s*3)
seen[s*3]=1
while q:
  x=q.popleft()
  if x%3==0 and x//3==t:
    print(seen[x]//3)
    exit()
  for i in path[x]:
    if seen[i]==0:
      seen[i]=seen[x]+1
      q.append(i)
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

g = [[] * 1 for i in range(n*3)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a * 3 + 0].append(b * 3 + 1)
    g[a * 3 + 1].append(b * 3 + 2)
    g[a * 3 + 2].append(b * 3 + 0)


s, t = map(int, input().split())
s -= 1
t -= 1
d = [-1 for i in range(n*3)]
q = deque([])
q.append(s*3+0)
d[s*3+0] = 0
while q:
    v = q.popleft()
    for to in g[v]:
        if d[to] == -1:
            d[to] = d[v] + 1
            q.append(to)

if d[t*3+0] == -1:
    print(-1)
else:
    print(d[t*3+0] // 3)

Submission status: Accepted

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

b= [[] for i in range(3*n)]
# 3で割り切れる数がもとの点
for i in range(m):
    b[3*(a[i][0]-1)].append(3*(a[i][1]-1)+1)
    b[3*(a[i][0]-1)+1].append(3*(a[i][1]-1)+2)
    b[3*(a[i][0]-1)+2].append(3*(a[i][1]-1))

import collections
from collections import deque
def tree(s,g):

    INF=-10**9
    dis = [INF for i in range(3*n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1


        return dis[g]
    return bfs()

ans=tree(3*(s-1),3*(t-1))
if ans==-10**9:
    print(-1)
else:
    print(ans//3)

Submission status: Accepted

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

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

path = [[-1] * 3 for _ in range(N + 1)]
path[S][0] = 0
node = deque([(S, 0)])
while node:
    s, d = node.popleft()
    dist = path[s][d]

    d = (d+1) % 3
    for t in edge[s]:
        if path[t][d] != -1:
            continue
        path[t][d] = dist + 1
        node.append((t, d))


ans = path[T][0]//3
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

inf = 10**6
stack = deque([[3*S,0]])
time = [inf] * (3*N)

while stack:
    x = stack.popleft()
    for y in data[x[0]]:
        if time[y] > x[1] + 1:
            time[y] = x[1] + 1
            stack.append([y,x[1] + 1])

if time[3*T] == inf:
    print(-1)
else:
    print(time[3*T]//3)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    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())
    S -= 1
    T -= 1
    DP = [[1000000000 for j in range(N)] for i in range(3)]
    q = []
    heapify(q)
    heappush(q, (0, S, 0)) #回数, 頂点, mod
    while q:
        nc, nn, nlevel = heappop(q)
        if DP[nlevel][nn] == 1000000000:
            DP[nlevel][nn] = nc
            for nextnode in Edge[nn]:
                if nlevel == 2: heappush(q, (nc + 1, nextnode, 0))
                else: heappush(q, (nc, nextnode, nlevel + 1))
    if DP[0][T] < 1000000000: print(DP[0][T])
    else: print(-1)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,m = list(map(int,input().split()))
    graph = defaultdict(list)
    uv = [list(map(int,input().split())) for i in range(m)]
    u = [uv[i][0] for i in range(m)]
    v = [uv[i][1] for i in range(m)]
    for i in range(m):
        graph[u[i]].append(v[i]+n)
        graph[u[i]+n].append(v[i]+2*n)
        graph[u[i]+2*n].append(v[i])
    s,t = map(int,input().split())
    dist = [False]*(3*n+1)

    def bfs():
        q = deque([s])
        dist[s] = 0
        while len(q):
            cur = q.popleft()
            if cur == t:
                return dist[cur] // 3
            for to in graph[cur]:
                if dist[to] == False:
                    dist[to] = dist[cur] + 1
                    q.append(to)
        return -1

    print(bfs())

if __name__ == "__main__":
    main() 
    
#endline===============================================

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
if m==0:
  print(-1)
  exit()
path=[[] for _ in range(3*n)]
for i in range(m):
  u,v=map(int,input().split())
  path[3*(u-1)].append(3*(v-1)+1)
  path[3*(u-1)+1].append(3*(v-1)+2)
  path[3*(u-1)+2].append(3*(v-1))
s,t=map(int,input().split())
s-=1
t-=1
visited=[0]*(3*m)
q=deque([3*s])
visited[3*s]=1
while q:
  x=q.popleft()
  if x%3==0 and x//3==t:
    print(visited[x]//3)
    exit()
  for i in path[x]:
    if visited[i]==0:
      visited[i]=visited[x]+1
      q.append(i)
print(-1)

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    edge =[[[] for _ in range(3)] for _ in range(N)]
    for _ in range(M):
        u,v = map(int,input().split())
        for i in range(3):
            edge[u-1][i].append((v-1,(i+1)%3))

    S,T = map(int,input().split())
    go =[[0 for _ in range(3)] for _ in range(N)]
    q = deque([(S-1,0)])
    while q:
        now,rest = q.popleft()
        for fol,fr in edge[now][rest]:
            if go[fol][fr] == 0:
                go[fol][fr] = go[now][rest]+1
                q.append((fol,fr))
                
    if go[T-1][0] != 0 and go[T-1][0]%3 == 0:
        print(go[T-1][0]//3)
        exit()
    
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    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())
    q = deque()
    go = [[False for _ in range(3)] for _ in range(N)]
    q.append((S-1,0,1))
    while q:
        now,step,d = q.popleft()
        if step == 3:
            if now == T-1:
                print(d)
                exit()
            step = 0
            d += 1
        if go[now][step]:
            continue
        go[now][step] = True
        for fol in edge[now]:
            q.append((fol,step+1,d))

    print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
# 3*N頂点あるとする
edges = [[] for _ in range(3*N + 4)] # 3-indexed
for _ in range(M):
    u, v = lr()
    u *= 3; v *= 3
    edges[u].append(v+1)
    edges[u+1].append(v+2)
    edges[u+2].append(v)

INF = 10 ** 18

def dijkstra(start):
    dist = [INF] * (3*N+4)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heappop(que)
        if dist[v] < d:
            continue
        for next in edges[v]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

S, T = lr()
dist = dijkstra(S*3)
if dist[T*3] == INF:
    print(-1)
else:
    print(dist[T*3] // 3)

Submission status: Accepted

Solution code:
import sys
from collections import deque

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)

s, t = map(int, sys.stdin.readline().split())

def main():
    dist = [inf] * (n + 1)
    can_reach = [[False] * 3 for _ in range(n + 1)]
    queue = deque([(0, s)])
    can_reach[s][0] = True
    while queue:
        d, x = queue.popleft()
        if d % 3 == 0:
            dist[x] = min(dist[x], d // 3)
        d += 1
        for y in g[x]:
            if not can_reach[y][d%3]:
                can_reach[y][d%3] = True
                queue.append((d, y))

    return dist[t] if dist[t] != inf else -1

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)

s, t = map(int, sys.stdin.readline().split())

def main():
    dist = [inf] * (n + 1)
    can_reach = [[False] * 3 for _ in range(n + 1)]
    hq = [(0, s)]
    can_reach[s][0] = True
    while hq:
        d, x = heappop(hq)
        if d % 3 == 0:
            dist[x] = min(dist[x], d // 3)
        d += 1
        for y in g[x]:
            if not can_reach[y][d%3]:
                can_reach[y][d%3] = True
                heappush(hq, (d, y))

    return dist[t] if dist[t] != inf else -1

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
for i in range(M):
  u, v = map(int, input().split())
  dic[u-1] += [v-1]
S, T = map(int, input().split())
S -= 1
T -= 1
dist = [[float('inf')]*3 for i in range(N)]
dist[S][0] = 0
q = deque([(S,0)])
flag = False
cnt = 0
while q:
  cnt += 1
  e, m = q.popleft()
  n = (m+1)%3
  for p in dic[e]:
    if p==T:
      flag = True
    if dist[p][n]>dist[e][m]+1:
      dist[p][n] = dist[e][m]+1
      q += [(p,n)]
if flag:
  ans = dist[T][0] if dist[T][0]!=float('inf') else -1
  print(ans//3)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque


data = sys.stdin.readlines()
N, M = map(int, data[0].split())
edge = [[] for _ in range(N)]
for i in range(1, M + 1):
    u, v = map(int, data[i].split())
    u -= 1
    v -= 1
    edge[u].append(v)
S, T = map(lambda x: int(x) - 1, data[M + 1].split())

visited = set()
q = deque()
q.append((0, S))
ans = 10 ** 10
while len(q) > 0:
    c, v = q.popleft()
    key = (c % 3, v)
    if key in visited:
        continue
    visited.add(key)
    if v == T and c % 3 == 0:
        ans = min(ans, c // 3)
    else:
        for e in edge[v]:
            newKey = (c + 1, e)
            q.append(newKey)

if ans == 10 ** 10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

# dp=[[inf]*3 for i in range(n)]
# dp[s][0] = 0

def disktra(g,s):
    c=1
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    hq=[]
    heapq.heappush(hq,(dist[s],s))
    while hq:
        cost,u =heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v in g[u]:
            if dist[v] <= dist[u] +c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq,(dist[v],v))
    return dist

dp=disktra(G,3*s)
print(-1 if dp[3*t]==inf else dp[3*t]//3)
# print(*dp,sep="\n")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

# dp=[[inf]*3 for i in range(n)]
# dp[s][0] = 0

def disktra(g,s):
    n=len(g)
    dist = [[inf]*3 for i in range(n)]
    dist[s][0] = 0
    hq=collections.deque(); hq.appendleft((0,s))
    while hq:
        cost,u =hq.pop()
        if dist[u][cost%3] < cost:
            continue
        for v in g[u]:
            if dist[v][(dist[u][cost%3]+1)%3] <= dist[u][cost%3] + 1:
                continue
            dist[v][(dist[u][cost%3]+1)%3] = dist[u][cost%3] + 1
            hq.appendleft((dist[v][(dist[u][cost%3]+1)%3],v))
    return dist

dp=disktra(G,s)
print(-1 if dp[t][0]==inf else dp[t][0]//3)
# print(*dp,sep="\n")

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m = inpm()
    g = [[] for _ in range(n)]
    for _ in range(m):
        u,v = inpm()
        u -= 1
        v -= 1
        g[u].append(v)
    s,t = inpm()
    s -= 1
    t -= 1
    que = deque()
    que.append(s)
    visited1 = [0 for _ in range(n)]
    visited2 = [0 for _ in range(n)]
    visited3 = [0 for _ in range(n)]
    visited3[s] = 1
    cnt = 1
    while True:
        tank1 = deque()
        tank2 = deque()
        tank3 = deque()
        while que:
            start = que.pop()
            for go in g[start]:
                if not visited1[go]:
                    visited1[go] = 1
                    tank1.append(go)
        while tank1:
            start = tank1.pop()
            for go in g[start]:
                if not visited2[go]:
                    visited2[go] = 1
                    tank2.append(go)
        while tank2:
            start = tank2.pop()
            for go in g[start]:
                if not visited3[go]:
                    visited3[go] = 1
                    tank3.append(go)
                if go == t:
                    print(cnt)
                    return
        que = tank3
        cnt += 1
        if que == deque():
            break
    print(-1)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
N,M = list(map(int, input().split()))

# node 3bai
# 0 N-1, N 2N-1, 2N 3N-1.
G = {}
for i in range(3*N):
  G[i] = []

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

q = deque()
visited = [False for i in range(3*N)]
willsearch = [False for i in range(3*N)]
dists = [-1 for i in range(3*N)]
q.append(S)
dists[S] = 0

while len(q) > 0:
  now = q.popleft()
  visited[now] = True
  for nextp in G[now]:
    if visited[nextp] or willsearch[nextp]:
      continue
    willsearch[nextp] = True
    q.append(nextp)
    dists[nextp] = dists[now] + 1
    
if dists[T] > 0:
  print(dists[T] // 3)
else:
  print(-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for i 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, 1])
    G[u + N].append([v + 2 * N, 1])
    G[u + 2 * N].append([v, 1])

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


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0
    visited = [False] * n

    # 距離・頂点
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        visited[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (visited[to]) or (distances[to] <= new_dist):
                continue

            distances[to] = new_dist
            heapq.heappush(hq, (new_dist, to))

    return distances


distances = dijkstra(G, S)
print(distances[T] // 3 if distances[T] != float('inf') else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(3*N)]
    for i in range(M):
        u,v=map(lambda x: int(x)-1,input().split())
        for k in range(3):
            edge[u*3+k].append(v*3+(k+1)%3)
    S,T=map(lambda x:int(x)-1,input().split())
    que=deque()
    que.append(S*3)
    c=[-1]*(3*N)
    c[S*3]=0
    while que:
        v=que.popleft()
        for nv in edge[v]:
            if c[nv]==-1:
                c[nv]=c[v]+1
                que.append(nv)
    print(c[T*3]//3 if c[T*3]!=-1 else -1)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

    S, T = map(int, input().split())
    S -= 1
    T -= 1
    dist = [[float('inf')] * 3 for _ in range(N)]
    dist[S][0] = 0
    q = deque([])
    q.append((S,0))
    while q:
        v, l = q.popleft()
        nl = (l + 1) % 3
        for nv in edge[v]:
            if dist[nv][nl] != float('inf'):
                continue
            dist[nv][nl] = dist[v][l] + 1
            q.append((nv,nl))
        
    
    if dist[T][0] == float('inf'):
        print(-1)
    else:
        print(dist[T][0] // 3)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
g=[[] for _ in range(N)]
gr=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    g[u-1].append(v-1)
    gr[v-1].append(u-1)
S,T=map(int,input().split())


f = [[-1,-1,-1] for _ in range(N)]
f[S-1][0] = 0
q=deque([[S-1,0]])

while q:
    d,s = q.popleft()
    s += 1
    for sd in g[d]:
        if f[sd][s%3]==-1:
            f[sd][s%3] = s//3
            q.append([sd,s])


print(f[T-1][0])

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    U = [set() for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        U[u - 1].add(v - 1)
    S, T = map(int, input().split())
    S, T = S - 1, T - 1
    V = [False] * N
    V[S] = True
    cur = set([S])
    r = 0
    while cur and T not in cur:
        r += 1
        for _ in range(3):
            nxt = set()
            for c in cur:
                nxt |= U[c]
            cur = nxt
        nxt = set()
        for c in cur:
            if not V[c]:
                V[c] = True
                nxt.add(c)
        cur = nxt
    return r if T in cur else -1

print(main())

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    d = {}
    for _ in range(M):
        u, v = map(int, input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u] = [v]
    s, t = map(int, input().split())
    cur = set([s])
    ne1 = set()
    ne2 = set()
    ne3 = set()
    c = 0
    v3 = set()
    v1 = set()
    v2 = set()
    while len(v3) < N:
        for i in cur:
            if i not in d:
                continue
            for j in d[i]:
                if j not in v1:
                    ne1.add(j)
                    v1.add(j)
        if len(ne1) == 0:
            return -1
        for i in ne1:
            if i not in d:
                continue
            for j in d[i]:
                if j not in v2:
                    ne2.add(j)
                    v2.add(j)
        if len(ne2) == 0:
            return -1
        for i in ne2:
            if i not in d:
                continue
            for j in d[i]:
                if j not in v3:
                    ne3.add(j)
                    v3.add(j)
        if len(ne3) == 0:
            return -1
        c += 1
        if t in ne3:
            return c
        cur = ne3
        ne1 = set()
        ne2 = set()
        ne3 = set()
    return -1
print(main())

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
if m==0:
  print(-1)
  exit()
edge=[[] for i in range(3*n)]
for i in range(m):
  u,v=map(int,input().split())
  edge[3*(u-1)].append(3*(v-1)+1)
  edge[3*(u-1)+1].append(3*(v-1)+2)
  edge[3*(u-1)+2].append(3*(v-1))
s,t=map(int,input().split())
s-=1
t-=1
visited=[0 for i in range(3*m)]
def bfs(edge,visited,s,t):
  q=deque([3*s])
  visited[3*s]=1
  cnt=0
  while q:
    x=q.popleft()
    if x%3==0 and x//3==t:
      return visited[x]//3
    for i in edge[x]:
      newx=i
      if visited[newx]==0:
        visited[newx]=visited[x]+1
        q.append(newx)
  return -1
print(bfs(edge,visited,s,t))

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
s,t = map(int,input().split())
visited = [[-1,-1,-1] for i in range(n+1)]
que = deque([(s,0,0)])
while que:
  x,mod,cnt = que.popleft()
  visited[x][mod] = cnt
  if x == t and mod == 0:
    break
  for y in graph[x]:
    if visited[y][(mod+1)%3] == -1:
      que.append((y,(mod+1)%3,cnt+1))
      visited[y][(mod+1)%3] = cnt+1
print(visited[t][0]//3)

Submission status: Accepted

Solution code:
from collections import  deque

class Graph(): #directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]-1].append(e[1]-1)
            self.deg[e[1]-1] += 1

import sys
input = sys.stdin.readline

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

g = Graph(N,edge)

stack = deque([(S,0)])
used = [[False]*3 for _ in range(N)]

while stack:
    node,depth = stack.popleft()
    if node == T and depth % 3 == 0:
        print(depth//3)
        break
    for adj in g.graph[node]:
        if not used[adj][(depth+1)%3]:
            used[adj][(depth+1)%3] = True
            stack.append((adj,depth+1))
else:
    print(-1)

Submission status: Accepted

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

from collections import deque

N, M = map(int, input().split())
UV = [list(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())
INF = 10 ** 15

if M == 0:
  print(-1)
  exit()

graph = [[] for _ in range(3 * M + 1)]
for u, v in UV:
  graph[u].append(v + M)
  graph[u + M].append(v + 2 * M)
  graph[u + 2 * M].append(v)

queue = deque([S])
dist = [INF] * (3 * M + 1)
dist[S] = 0

while queue:
  q = queue.popleft()
  for g in graph[q]:
    if dist[g] > dist[q] + 1:
      dist[g] = dist[q] + 1
      queue.append(g)
print(dist[T] // 3 if dist[T] != INF else -1)