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())
pst = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  pst[a].append(b)
s,t = map(int,input().split())
s -= 1
t -= 1
cnt = [[0,0,0] for _ in range(n)]
cnt[s][0] = 1
now = [s]
time = 0
while now:
  time += 1
  last = now
  now = []
  for x in last:
    for y in pst[x]:
      if cnt[y][time%3] == 0:
        cnt[y][time%3] = 1
        now.append(y)
  #print(time,cnt,now)
  if cnt[t][0] == 1:
    print(time//3)
    break
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

edges = [[] for _ in range(n + 1)]

for _ in range(m):
	u, v = list(map(int, input().split()))
	edges[u].append(v)

s, t = list(map(int, input().split()))
visited = [[] for _ in range(n + 1)]

q = deque()
q.append((s, 0))

while q:
	node, cnt = q.popleft()

	if cnt % 3 in visited[node]:
		continue
	
	if node == t and cnt % 3 == 0:
		print(cnt // 3)
		sys.exit()
	
	else:
		visited[node].append(cnt % 3)
		for e in edges[node]:
			q.append((e, cnt + 1))
	
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

edges = [[[] for _ in range(3)] for _ in range(n + 1)]

for _ in range(m):
	u, v = list(map(int, input().split()))
	edges[u][0].append((v, 1))
	edges[u][1].append((v, 2))
	edges[u][2].append((v, 0))

s, t = list(map(int, input().split()))
visited = [[[] for _ in range(3)] for _ in range(n + 1)]

q = deque()
q.append((s, 0, 0))

while q:
	node, div, cnt = q.popleft()

	if visited[node][div] == 1:
		continue
	
	if (node, div) == (t, 0):
		print(cnt // 3)
		sys.exit()
	
	else:
		visited[node][div] = 1
		for e in edges[node][div]:
			q.append((e[0], e[1], cnt + 1))
	
print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

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

graph = defaultdict(list)

for edge in edges:
	u, v = edge
	graph[u].append(v + n)
	graph[u + n].append(v + 2*n)
	graph[u + 2*n].append(v)

def bfs(s, t, graph):
	vis_set = set()
	dist = defaultdict(lambda: int(-1))
	dist[s] = 0
	que = queue.Queue()
	que.put(s)
	vis_set.add(s)	

	while not que.empty():
		vert = que.get()
		for nxt in graph[vert]:
			if nxt not in vis_set:
				dist[nxt] = dist[vert] + 1
				vis_set.add(nxt)
				que.put(nxt)
				if nxt == t:
					return dist[nxt]//3
	return -1
ans = bfs(s, t, graph)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
g = {}
for v in range(1,N*3+1):
    g[v] = []

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

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

visiting = [S]
visited = {S:0}
while visiting:
    v = visiting.pop(0)
    if v == T:
        break

    for v2 in g[v]:
        if v2 not in visited:
            visiting.append(v2)
            visited[v2] = visited[v]+1

if T in visited:
    print(visited[T] // 3)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = {}
for v in range(1,N*3+1):
    E[v] = []
for _ in range(M):
    u, v = map(int, input().split())
    E[u].append(v+N)
    E[u+N].append(v+2*N)
    E[u+2*N].append(v)
S, T = map(int, input().split())
dist = [-1 for _ in range(3*N)]
dist[S-1] = 0

q = []
q.append(S)
while q:
    n = q.pop(0)
    if n == T:
        break
    for t in E[n]:
        if dist[t-1] < 0:
            dist[t-1] = dist[n-1] + 1
            q.append(t)
print(-1 if dist[T-1] < 0 else dist[T-1] // 3)

Submission status: Accepted

Solution code:
#52 ABC132E
class Dijkstra():
    class Edge():
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数
    @property
    def E(self):
        return self._E
    @property
    def V(self):
        return self._V
    def add(self, _from, _to, _cost):
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
    def shortest_path(self, s):
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する
        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue
            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

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

djk=Dijkstra(3*n+1)
for u,v in uv:
	djk.add(u,v+n,1)
	djk.add(u+n,v+n*2,1)
	djk.add(u+n*2,v,1)
d = djk.shortest_path(s)
print(d[t]//3 if d[t]!=float("inf") else -1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
E = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    E[u].append(v+N)
    E[u+N].append(v+2*N)
    E[u+2*N].append(v)
S, T = map(int, input().split())
R = [-1 for _ in range(3*N)]
R[S-1] = 0

q = deque()
q.append(S)
while q:
    n = q.popleft()
    if n == T:
        break
    for t in E[n]:
        if R[t-1] < 0:
            R[t-1] = R[n-1] + 1
            q.append(t)
print(-1 if R[T-1] < 0 else R[T-1] // 3)

Submission status: Accepted

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

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

from heapq import heappush, heappop
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

from collections import defaultdict
graph = defaultdict(lambda: {})

for a,b in UV:
    graph[a][b+N] = 1
    graph[a+N][b+N*2] = 1
    graph[a+N*2][b] = 1
    
shortest = dijkstra(graph, S, N*3)
#print(shortest)
if shortest[T] % 3 == 0 and shortest[T] != 0:
    print(shortest[T]//3)
else:
    print(-1)

Submission status: Accepted

Solution code:
def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

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

S-=1;T-=1
E = [[] for _ in [0]*3*N]
for u,v in UV:
    u-=1;v-=1
    for i in range(3):
        v = (v+N)%(3*N)
        E[u+i*N].append(v)

print(dist_bfs(3*N,E,S)[T]//3)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
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[3 * u + 0].append(3 * v + 1)
    G[3 * u + 1].append(3 * v + 2)
    G[3 * u + 2].append(3 * v + 0)
S, T = map(int, input().split())
S, T = S - 1, T - 1
INF = float('inf')
d = [INF] * (3 * N)
d[3 * S] = 0


que = deque([3 * S])
while que:
    u = que.popleft()
    for w in G[u]:
        if d[w] == INF:
            d[w] = d[u] + 1
            que.append(w)


ans = d[3 * T]
if ans == INF:
    print(-1)
else:
    print(ans // 3)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
edge=[[] for i in range(3*n)]
for i in range(m):
  u,v=map(int,input().split())
  for j in range(3):
    edge[u-1+j*n].append([1,(v-1+(j+1)*n)%(3*n)])
import heapq
def dijkstra_heap(s):
  d=[float("inf")]*(3*n)
  used=[True]*(3*n)
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d
s,t=map(int,input().split())
ans=dijkstra_heap(s-1)[t-1]
print(ans//3 if ans%3==0 else -1)

Submission status: Accepted

Solution code:
#行けるかどうかは判断できる、回数は判断できない
#-->回数を数えるように変更
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

#辺の管理(1-index)s
edge = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v = map(int, input().split())
    edge[u] += [v]
# print (edge)
INF = 10 ** 9
used1 = [INF] * (N + 1) #1手目で行けたところ
used2 = [INF] * (N + 1) #2手目で行けたところ
used3 = [INF] * (N + 1) #3手目で行けたところ

def solve(s): #スタート地点s
    from collections import deque
    used3[s] = 0
    
    #ここまで最初の準備
    from1 = deque() #used1から向かう辺のdeque
    from2 = deque() #used2から向かう辺のdeque
    from3 = deque() #used3から向かう辺のdeque

    f1append = from1.append
    f2append = from2.append
    f3append = from3.append

    f1pop = from1.popleft
    f2pop = from2.popleft
    f3pop = from3.popleft

    for i in edge[s]:
        # print (i)
        f3append(i)

    #deque: 空のとき = False
    count = 0
    while from1 or from2 or from3: #どれかが空ではないとき
        count += 1
        #from3 --> from1 -->from2の順にすべて処理
        for _ in range(len(from3)):
            # print ('from3', count)
            v = f3pop()
            if used1[v] == INF:
                used1[v] = count
                for i in edge[v]:
                    f1append(i)
        
        for _ in range(len(from1)): #中にある分すべてを処理する
            # print ('from1', count)
            v = f1pop()
            if used2[v] == INF:
                used2[v] = count
                for i in edge[v]:
                    f2append(i)
        
        for _ in range(len(from2)):
            # print ('from2', count)
            v = f2pop()
            if used3[v] == INF:
                used3[v] = count
                for i in edge[v]:
                    f3append(i)
        
    return


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

solve(S)
# print (1, used1)
# print (2, used2)
# print (3, used3)

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

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
R = [[] for i in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    R[a].append(b)
S,T = map(int, input().split())
answer = -1
queue =  deque()
queue.append([S,0])
visited = {}
visited[S] = 1
visited2 = {}
while queue != deque():
    tmp = queue.popleft()
    if tmp[0] == T:
        answer = tmp[1]
        break
    tmp_queue = deque()
    tmp_queue.append(tmp[0])
    for i in range(3):
        tmp2_queue = tmp_queue
        tmp_queue = deque()
        for j in tmp2_queue:
            if (j, i) in visited2:
                continue
            else:
                visited2[j,i] = 1
                tmp_queue += R[j]
    for i in tmp_queue:
        if i in visited:
            continue
        else:
            visited[i] = 1
            queue.append([i,tmp[1]+1])
            
print(answer)

Submission status: Accepted

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

INF = float('inf')

def bfsMinCosts(adjList, vSt):
    numV = len(adjList)
    costs = [INF] * numV
    costs[vSt] = 0
    Q = deque([vSt])
    while Q:
        vNow = Q.popleft()
        cNow = costs[vNow]
        for v2 in adjList[vNow]:
            if costs[v2] == INF:
                costs[v2] = cNow + 1
                Q.append(v2)
    return costs

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

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

costs = bfsMinCosts(adjL, 3*S+0)

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

dq = deque()
dq.append((S, 0))

while dq:
    v = dq.popleft()
    if v == (T, 0):
        break
    for u in edge[v]:
        if dist[u] < inf: continue
        dq.append(u)
        dist[u] = dist[v] + 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
e = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    e[(a, 0)].append((b, 1))
    e[(a, 1)].append((b, 2))
    e[(a, 2)].append((b, 0))

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

d = deque()
d.appendleft((S, 0))

inf = float('inf')
dist = defaultdict(lambda: inf)
dist[(S, 0)] = 0

while d:
    next_node = d.pop()
    for v in e[next_node]:
        if(dist[v] > dist[next_node] + 1):
            dist[v] = dist[next_node] + 1
            if(v == (T, 0)):
                break
            d.appendleft(v)

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

Submission status: Accepted

Solution code:
from collections import deque

inf = float('inf')

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

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

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

dq = deque()
dq.append(s)

dist = [inf] * (n * 3)
dist[s] = 0
while dq:
    v = dq.popleft()
    if v == t:
        break
    for u in g[v]:
        if dist[u] < inf: continue
        dq.append(u)
        dist[u] = dist[v] + 1

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

Submission status: Accepted

Solution code:
def add_edge(s, d, edges):
    if s in edges:
        edges[s].append(d)
    else:
        edges[s] = [d]


N, M = [int(x) for x in input().split()]
edges = {}
for _ in range(M):
    s, d = [int(x) for x in input().split()]
    add_edge(s*3 + 0, d*3 + 1, edges)
    add_edge(s*3 + 1, d*3 + 2, edges)
    add_edge(s*3 + 2, d*3 + 0, edges)
S, T = [int(x)*3 + 0 for x in input().split()]

reached = set()
curs = [S]
count = 0
success = False

while curs:
    if T in curs:
        success = True
        break
    nexts = []
    for c in curs:
        if not c in edges:
            continue
        ns = edges[c]
        for n in ns:
            if not n in reached:
                reached.add(n)
                nexts.append(n)
    curs = nexts
    count += 1

if success:
    print(count // 3)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

visited = [[False]*3 for _ in range(N)]
dq = deque()
dq.append((S,0,0))
visited[S][0] = True

while dq:
    v,j,d = dq.popleft()
    nd = d + 1
    for nv,nj in ad[v][j]:
        if (nv,nj) == (T,0):
            print(nd//3)
            exit()
        if visited[nv][nj]:
            continue
        visited[nv][nj] = True
        dq.append((nv,nj,nd))
        
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
n, m = map(int, input().split())

edges = defaultdict(lambda: [])
for i in range(m):
    u, v = map(int, input().split())
    u1, v1 = (0, u), (1, v)
    u2, v2 = (1, u), (2, v)
    u3, v3 = (2, u), (0, v)
    edges[u1].append(v1)
    edges[u2].append(v2)
    edges[u3].append(v3)
    #u1, v1 = (0, v), (1, u)
    #u2, v2 = (1, v), (2, u)
    #u3, v3 = (2, v), (0, u)
    #edges[u1].append(v1)
    #edges[u2].append(v2)
    #edges[u3].append(v3)

#print(edges)
s, t = map(int, input().split())
s = (0, s)
t = (0, t)
#print(edges)
dist = {}
dist[s] = 0
visiting = deque()
visiting.append(s)
while len(visiting) > 0:
    #print(visiting)
    v = visiting.popleft()
    # check neighbors of v
    neighbors = edges[v]
    for neighbor in neighbors:
        if neighbor in dist:
            continue
        visiting.append(neighbor)
        if neighbor in dist:
            dist[neighbor] = min([dist[neighbor], dist[v] + 1])
        else:
            dist[neighbor] = dist[v] + 1
        
#print(dist)
#print(dist)
if t not in dist:
    print(-1)
else:
    if dist[t] % 3 == 0:
        print(dist[t] // 3 )
    else:
        print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque
N, M = map(int, input().split())
e = dd(list)
inf = 10 ** 9
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v + N)
  e[u + N].append(v + 2 * N)
  e[u + 2 * N].append(v)
S, T = map(int, input().split())
S += 2 * N
T += 2 * N
stopped = [inf] * (3 * (N + 1))
Q = deque()
Q.append(S)
stopped[S] = 0
while len(Q) != 0:
  p = Q.popleft()
  if stopped[p] >= stopped[T]:
    break
  for q in e[p]:
    if stopped[q] > stopped[p] + 1:
      Q.append(q)
      stopped[q] = stopped[p] + 1
if stopped[T] == inf:
  print(-1)
else:
  print(stopped[T] // 3)

Submission status: Accepted

Solution code:
import copy
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(b)]
s,t=map(int,input().split())
s=3*s
t=3*t
dd=[[]for i in range(a+1)]
for i in range(b):
  da=c[i][0]
  db=c[i][1]
  dd[da].append(db)
  

d=[[]for i in range(3*(a+1))]
for i in range(len(dd)):
  for j in dd[i]:
      d[3*i].append(3*j+1)
      d[3*i+1].append(3*j+2)
      d[3*i+2].append(3*j)
e=[-1 for i in range(3*a+3)]
f=[s]
h=0
for i in range(1,3*a+3):
  g=[]
  for j in f:
    for k in d[j]:
      if e[k]==-1:
        e[k]=1
        g.append(k)
        if k==t:
          print(i//3)
          h=1
          break
    if h==1:
      break
  if h==1:
    break
  if g==[]:
    print(-1)
    break
  f=copy.copy(g)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

def bfs(start, end, V, E):
    V[start] = 0
    Q = deque()
    Q.append(start)
    while(len(Q) > 0 and V[end] < 0):
        q = Q.popleft()
        d = V[q] + 1
        for v in E[q]:
            if V[v] > 0:
                continue
            V[v] = d
            Q.append(v)
    return V

n, m = map(int, input().split())
E = defaultdict(list)
for i in range(m):
    u, v = map(int, input().split())
    E[u].append(n + v)
    E[n + u].append(2 * n + v)
    E[2 * n + u].append(v)
s, t = map(int, input().split())
V = [-1] * (3 * n + 1)
V = bfs(s, t, V, E)
if V[t] < 0:
    print(-1)
else:
    print(V[t] // 3)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N, M, to, start, goal):
    costs = [float('inf')] * (3*N+3)
    costs[start] = 0

    q = deque([start])

    while len(q) != 0:
        u = q.popleft()
        for v in to[u]:
            if costs[u] + 1 < costs[v]:
                costs[v] = costs[u] + 1
                if v == goal: return costs[v] // 3
                q.append(v)
    return -1



def main():
    N, M = map(int, input().split())
    to = [ [] for _ in range(3*N+3) ]
    for _ in range(M):
        u, v = map(int, input().split())
        for i in range(3):
            to[u + (N+1)*i].append(v + (N+1) * ((i+1)%3))
    S, T = map(int, input().split())
    print(solve(N, M, to, S, T))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

inf = float('inf')

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

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

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

dq = deque()
dq.append(s)

can = False
dist = [inf] * (n * 3)
dist[s] = 0

while dq:
    v = dq.popleft()
    if v == t:
        can = True
        break
    for nv in es[v]:
        if dist[nv] == inf:
            dq.append(nv)
            dist[nv] = dist[v] + 1

if not can:
    print(-1)
else:
    print(dist[t] // 3)

Submission status: Accepted

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

edges = []
for i in range(M):
  edges.append([u[i]*3-3, v[i]*3-2])
  edges.append([u[i]*3-2, v[i]*3-1])
  edges.append([u[i]*3-1, v[i]*3-3])

def edges_to_pt(edges,n):
  '''
  input
    edges: 枝の[始点,終点]を格納した2次元配列　edges=[[0,1],[1,2],[2,0]]
    n:  頂点数 n=3

  output
    pt: 各点との結合場所を格納した2次元配列 pt=[[1],[2],[0]]
  '''
  pt = [[] for i in range(n)]
  while edges:
    temp_edge = edges.pop()
    pt[temp_edge[0]].append(temp_edge[1])
  return pt

def bfs(pt,v):
  '''
  input
    pt: 各点との結合場所を格納した2次元配列　pt=[[1, 2, 3], [0], [5, 0], [6, 0], [6], [2], [3, 4]]
    v: 初期点 v=0

  output
    d: 初期点からの距離を格納した配列 d=[0, 1, 1, 1, 3, 2, 2]
  '''
  n=len(pt)
  d=[-1]*n
  d[v]=0
  q=[v]
  c=1
  while q:
    q1=[]
    for i in q:
      for j in pt[i]:
        if d[j]==-1:
          d[j]=c
          q1.append(j)
    q=q1
    c+=1
  return d

pt = edges_to_pt(edges,3*N)
ans = bfs(pt,3*S-3)[3*T-3] // 3

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
G=[[] for i in range(3*N)]
L=[-2 for i in range(3*N)]
for i in range(0,M):
  u,v=map(int,input().split())
  G[N*0+u-1].append(N*1+v-1)
  G[N*1+u-1].append(N*2+v-1)
  G[N*2+u-1].append(N*0+v-1)
  
  
#print(G)
S,T=map(int,input().split())
S=S-1
T=T-1
L[S]=0
Now=[S]
while Now:
  x=Now.pop(0)
  for i in range(len(G[x])):
    #print(x,"x",Now,"Now")
    #print(L)
    g=G[x]
    if L[g[i]]<0:
      L[g[i]]=L[x]+1
      Now.append(g[i])
print(L[T]//3)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())

g = [[] for i in range(n)]

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

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

visited = [[-1]*3 for j in range(n)]

l = 0
queue = deque([[s, l]])
visited[s][l] = 0
while queue:
  x, l = queue.popleft()
  if [x, l] == [t, 0]:
    print(visited[x][l]//3)
    exit()
  for x_ in g[x]:
    new_x, new_l = x_, (l+1)%3
    if visited[new_x][new_l] == -1:
      visited[new_x][new_l] = visited[x][l]+1
      queue.append([new_x, new_l])
    
print(visited[t][0])

Submission status: Accepted

Solution code:
from collections import deque


def inpl():
    return list(map(int, input().split()))


N, M = inpl()
UV = [inpl() for i in range(M)]
S, T = inpl()
S -= 1
T -= 1

ans = [[-1, -1, -1] for i in range(N)]

uv = [[] for i in range(N)]
for u, v in UV:
    u -= 1
    v -= 1
    uv[u].append(v)

ans[S][0] = 0
que = deque()
que.append((S, 0))
t = 0
while que:
    v, t = que.popleft()
    nt = (t + 1) % 3
    for nv in uv[v]:
        if ans[nv][nt] != -1:
            continue
        elif nv == T and nt == 0:
            ans[nv][nt] = (ans[v][t] + 1) // 3
            break
        ans[nv][nt] = ans[v][t] + 1
        que.append((nv, nt))

print(ans[T][0])