
"""simple docstring"""







from collections import deque
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE )  ->     str:







							"""simple docstring"""


							__snake_case     			=       len(lowercase_ )
							__snake_case     			=       deque()
							__snake_case     			=       [False for _ in range(lowercase_ )]
							__snake_case     			=       [-1 for _ in range(lowercase_ )]
							__snake_case     			=       index_of[:]

							def strong_connect(SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE ):
														__snake_case     			=       index  # the number when this node is seen
														__snake_case     			=       index  # lowest rank node reachable from here
														index += 1
														stack.append(lowercase_ )
														__snake_case     			=       True

														for w in g[v]:
																					if index_of[w] == -1:
																												__snake_case     			=       strong_connect(lowercase_							,    lowercase_							,    lowercase_ )
																												__snake_case     			=       (
																												    lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
																												)
																					elif on_stack[w]:
																												__snake_case     			=       (
																												    lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
																												)

														if lowlink_of[v] == index_of[v]:
																					__snake_case     			=       []
																					__snake_case     			=       stack.pop()
																					__snake_case     			=       False
																					component.append(lowercase_ )
																					while w != v:
																												__snake_case     			=       stack.pop()
																												__snake_case     			=       False
																												component.append(lowercase_ )
																					components.append(lowercase_ )
														return index

							__snake_case     			=       []
							for v in range(lowercase_ ):
														if index_of[v] == -1:
																					strong_connect(lowercase_							,    0							,    lowercase_ )

							return components
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE )  ->     Optional[int]:







							"""simple docstring"""


							__snake_case     			=       [[] for _ in range(lowercase_ )]
							for u, v in edges:
														g[u].append(lowercase_ )
							return g


if __name__ == "__main__":
		# Test
		_SCREAMING_SNAKE_CASE	       =      7
		_SCREAMING_SNAKE_CASE	       =      [0, 0, 1, 2, 3, 3, 4, 4, 6]
		_SCREAMING_SNAKE_CASE	       =      [1, 3, 2, 0, 1, 4, 5, 6, 5]
		_SCREAMING_SNAKE_CASE	       =      [(u, v) for u, v in zip(source, target)]
		_SCREAMING_SNAKE_CASE	       =      create_graph(n_vertices, edges)

		assert [[5], [6], [4], [3, 2, 1, 0]] == tarjan(g)


"""simple docstring"""







from heapq import heappop, heappush

import numpy as np
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    )  ->     tuple[float | int, list[tuple[int, int]]]:







							"""simple docstring"""


							__snake_case			,   __snake_case     			=       grid.shape
							__snake_case     			=       [-1, 1, 0, 0]
							__snake_case     			=       [0, 0, -1, 1]
							if allow_diagonal:
														dx += [-1, -1, 1, 1]
														dy += [-1, 1, -1, 1]

							__snake_case			,   __snake_case     			=       [(0, source)], set()
							__snake_case     			=       np.full((rows, cols)							,    np.inf )
							__snake_case     			=       0
							__snake_case     			=       np.empty((rows, cols)							,    dtype=SCREAMING_SNAKE_CASE )
							__snake_case     			=       None

							while queue:
														((__snake_case)			,   (__snake_case))     			=       heappop(SCREAMING_SNAKE_CASE )
														if (x, y) in visited:
																					continue
														visited.add((x, y) )

														if (x, y) == destination:
																					__snake_case     			=       []
																					while (x, y) != source:
																												path.append((x, y) )
																												__snake_case			,   __snake_case     			=       predecessors[x, y]
																					path.append(SCREAMING_SNAKE_CASE )  # add the source manually
																					path.reverse()
																					return matrix[destination], path

														for i in range(len(SCREAMING_SNAKE_CASE ) ):
																					__snake_case			,   __snake_case     			=       x + dx[i], y + dy[i]
																					if 0 <= nx < rows and 0 <= ny < cols:
																												__snake_case     			=       grid[nx][ny]
																												if next_node == 1 and matrix[nx, ny] > dist + 1:
																																			heappush(SCREAMING_SNAKE_CASE							,    (dist + 1, (nx, ny)) )
																																			__snake_case     			=       dist + 1
																																			__snake_case     			=       (x, y)

							return np.inf, []


if __name__ == "__main__":
		import doctest

		doctest.testmod()
