




from heapq import heappop, heappush

import numpy as np







def lowerCamelCase__  (     _lowercase					,		_lowercase					,		_lowercase					,		_lowercase					,		):

     '''simple docstring'''


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

     UpperCAmelCase_,       UpperCAmelCase_     :				Any  =     [(0, source)], set()
     UpperCAmelCase_     :				int  =     np.full((rows, cols)					,		np.inf )
     UpperCAmelCase_     :				Tuple  =     0
     UpperCAmelCase_     :				List[str]  =     np.empty((rows, cols)					,		dtype=_lowercase )
     UpperCAmelCase_     :				Tuple  =     None

     while queue:
          ((UpperCAmelCase_),       (UpperCAmelCase_))     :				Dict  =     heappop(_lowercase )
          if (x, y) in visited:
               continue
          visited.add((x, y) )

          if (x, y) == destination:
               UpperCAmelCase_     :				Optional[Any]  =     []
               while (x, y) != source:
                    path.append((x, y) )
                    UpperCAmelCase_,       UpperCAmelCase_     :				Union[str, Any]  =     predecessors[x, y]
               path.append(_lowercase )  # add the source manually
               path.reverse()
               return matrix[destination], path

          for i in range(len(_lowercase ) ):
               UpperCAmelCase_,       UpperCAmelCase_     :				Optional[Any]  =     x + dx[i], y + dy[i]
               if 0 <= nx < rows and 0 <= ny < cols:
                    UpperCAmelCase_     :				Tuple  =     grid[nx][ny]
                    if next_node == 1 and matrix[nx, ny] > dist + 1:
                         heappush(_lowercase					,		(dist + 1, (nx, ny)) )
                         UpperCAmelCase_     :				str  =     dist + 1
                         UpperCAmelCase_     :				List[str]  =     (x, y)

     return np.inf, []


if __name__ == "__main__":
     import doctest

     doctest.testmod()






_lowercase		:  Any			       ={"""a""": ["""c""", """b"""], """b""": ["""d""", """e"""], """c""": [], """d""": [], """e""": []}
_lowercase		:  Union[str, Any]			       =["""a""", """b""", """c""", """d""", """e"""]


def 		_SCREAMING_SNAKE_CASE     ( lowerCAmelCase__							,lowerCAmelCase__							,lowerCAmelCase__						):
		lowerCamelCase_	:     int 						=      start
		# add current to visited
		visited.append(lowerCAmelCase__						)
		lowerCamelCase_	:     Optional[int] 						=      edges[current]
		for neighbor in neighbors:
				# if neighbor not in visited, visit
				if neighbor not in visited:
						lowerCamelCase_	:     Dict 						=      topological_sort(lowerCAmelCase__							,lowerCAmelCase__							,lowerCAmelCase__						)
    # if all neighbors visited add current to sort
		sort.append(lowerCAmelCase__						)
		# if all vertices haven't been visited select a new one to visit
		if len(lowerCAmelCase__						) != len(lowerCAmelCase__						):
				for vertice in vertices:
						if vertice not in visited:
								lowerCamelCase_	:     Any 						=      topological_sort(lowerCAmelCase__							,lowerCAmelCase__							,lowerCAmelCase__						)
    # return sort
		return sort


if __name__ == "__main__":
		_lowercase		:  str			       =topological_sort("""a""", [], [])
		print(sort)
