


'''simple docstring'''







from collections import deque






def 				lowerCAmelCase__	(    lowerCamelCase					:      int       ):
       _A					:     Dict     = len(lowerCamelCase       )
       _A					:     Any     = deque()
       _A					:     Union[str, Any]     = [False for _ in range(lowerCamelCase       )]
       _A					:     str     = [-1 for _ in range(lowerCamelCase       )]
       _A					:     List[Any]     = index_of[:]

       def strong_connect(lowerCamelCase					:      List[str]  ,lowerCamelCase					:      Tuple  ,lowerCamelCase					:      str       ):
              _A					:     Tuple     = index  # the number when this node is seen
              _A					:     Dict     = index  # lowest rank node reachable from here
              index += 1
              stack.append(lowerCamelCase       )
              _A					:     str     = True

              for w in g[v]:
                     if index_of[w] == -1:
                            _A					:     Tuple     = strong_connect(lowerCamelCase  ,lowerCamelCase  ,lowerCamelCase       )
                            _A					:     Optional[int]     = (
                                lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
                            )
                     elif on_stack[w]:
                            _A					:     int     = (
                                lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
                            )

              if lowlink_of[v] == index_of[v]:
                     _A					:     Any     = []
                     _A					:     Optional[Any]     = stack.pop()
                     _A					:     List[Any]     = False
                     component.append(lowerCamelCase       )
                     while w != v:
                            _A					:     Tuple     = stack.pop()
                            _A					:     Union[str, Any]     = False
                            component.append(lowerCamelCase       )
                     components.append(lowerCamelCase       )
              return index

       _A					:     int     = []
       for v in range(lowerCamelCase       ):
              if index_of[v] == -1:
                     strong_connect(lowerCamelCase  ,0  ,lowerCamelCase       )

       return components






def 				lowerCAmelCase__	(    lowerCamelCase					:      List[str]  ,lowerCamelCase					:      Union[str, Any]       ):
       _A					:     List[Any]     = [[] for _ in range(lowerCamelCase       )]
       for u, v in edges:
              g[u].append(lowerCamelCase       )
       return g


if __name__ == "__main__":
   # Test
   A				:					Dict     =			7
   A				:					Optional[int]     =			[0, 0, 1, 2, 3, 3, 4, 4, 6]
   A				:					Union[str, Any]     =			[1, 3, 2, 0, 1, 4, 5, 6, 5]
   A				:					Union[str, Any]     =			[(u, v) for u, v in zip(source, target)]
   A				:					int     =			create_graph(n_vertices, edges)

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










'''simple docstring'''







class 			__lowerCamelCase			:  # Public class to implement a graph
    """simple docstring"""


    def __init__(  self      :							Optional[Any]				,							SCREAMING_SNAKE_CASE      :							int				,							SCREAMING_SNAKE_CASE      :							int				,							SCREAMING_SNAKE_CASE      :							list[list[bool]]):
           _A					:     List[Any]     = row
           _A					:     Union[str, Any]     = col
           _A					:     List[str]     = graph


    def        A   (  self      :							Any				,							SCREAMING_SNAKE_CASE      :							int				,							SCREAMING_SNAKE_CASE      :							int				,							SCREAMING_SNAKE_CASE      :							list[list[bool]]):
           return (
               0 <= i < self.ROW
               and 0 <= j < self.COL
               and not visited[i][j]
               and self.graph[i][j]
           )


    def        A   (  self      :							Tuple				,							SCREAMING_SNAKE_CASE      :							int				,							SCREAMING_SNAKE_CASE      :							int				,							SCREAMING_SNAKE_CASE      :							list[list[bool]]):
           # Checking all 8 elements surrounding nth element
           _A					:     Tuple     = [-1, -1, -1, 0, 0, 1, 1, 1]  # Coordinate order
           _A					:     Dict     = [-1, 0, 1, -1, 1, -1, 0, 1]
           _A					:     List[Any]     = True  # Make those cells visited
           for k in range(8):
                  if self.is_safe(i + row_nbr[k]				,							j + col_nbr[k]				,							SCREAMING_SNAKE_CASE):
                         self.diffs(i + row_nbr[k]				,							j + col_nbr[k]				,							SCREAMING_SNAKE_CASE)


    def        A   (  self      :							int):  # And finally, count all islands.
           _A					:     Dict     = [[False for j in range(self.COL)] for i in range(self.ROW)]
           _A					:     Union[str, Any]     = 0
           for i in range(self.ROW):
                  for j in range(self.COL):
                         if visited[i][j] is False and self.graph[i][j] == 1:
                                self.diffs(SCREAMING_SNAKE_CASE				,							SCREAMING_SNAKE_CASE				,							SCREAMING_SNAKE_CASE)
                                count += 1
           return count






