






'''simple docstring'''

from collections import deque



def 				snake_case       (  a_				:			int						)							->					Any:





      """simple docstring"""

      UpperCamelCase_					: Dict            =				len(a_						)
      UpperCamelCase_					: Optional[Any]            =				deque()
      UpperCamelCase_					: Optional[Any]            =				[False for _ in range(a_						)]
      UpperCamelCase_					: int            =				[-1 for _ in range(a_						)]
      UpperCamelCase_					: Any            =				index_of[:]

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

            for w in g[v]:
                  if index_of[w] == -1:
                        UpperCamelCase_					: Optional[int]            =				strong_connect(a_     , a_     , a_						)
                        UpperCamelCase_					: Dict            =				(
                            lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
                        )
                  elif on_stack[w]:
                        UpperCamelCase_					: List[Any]            =				(
                            lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
                        )

            if lowlink_of[v] == index_of[v]:
                  UpperCamelCase_					: List[str]            =				[]
                  UpperCamelCase_					: Tuple            =				stack.pop()
                  UpperCamelCase_					: Optional[int]            =				False
                  component.append(a_						)
                  while w != v:
                        UpperCamelCase_					: Dict            =				stack.pop()
                        UpperCamelCase_					: Optional[int]            =				False
                        component.append(a_						)
                  components.append(a_						)
            return index

      UpperCamelCase_					: Union[str, Any]            =				[]
      for v in range(a_						):
            if index_of[v] == -1:
                  strong_connect(a_     , 0     , a_						)

      return components



def 				snake_case       (  a_				:			List[str]     , a_				:			Union[str, Any]						)							->					Optional[int]:





      """simple docstring"""

      UpperCamelCase_					: Any            =				[[] for _ in range(a_						)]
      for u, v in edges:
            g[u].append(a_						)
      return g


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

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














'''simple docstring'''

from __future__ import annotations



def 				snake_case       (  a_				:			list[int]     , a_				:			list[int]     , a_				:			list[int]     , a_				:			list[list[str]]     , a_				:			int     , )							->					None:





      """simple docstring"""

      UpperCamelCase_					: List[Any]            =				len(a_						)

      # If row is equal to the size of the board it means there are a queen in each row in
      # the current board (possible_board)
      if row == n:
            # We convert the variable possible_board that looks like this: [1, 3, 0, 2] to
            # this: ['. Q . . ', '. . . Q ', 'Q . . . ', '. . Q . ']
            boards.append([""". """ * i + """Q """ + """. """ * (n - 1 - i) for i in possible_board]						)
            return

      # We iterate each column in the row to find all possible results in each row
      for col in range(a_						):
            # We apply that we learned previously. First we check that in the current board
            # (possible_board) there are not other same value because if there is it means
            # that there are a collision in vertical. Then we apply the two formulas we
            # learned before:
            #
            # 45º: y - x = b or 45: row - col = b
            # 135º: y + x = b or row + col = b.
            #
            # And we verify if the results of this two formulas not exist in their variables
            # respectively.  (diagonal_right_collisions, diagonal_left_collisions)
            #
            # If any or these are True it means there is a collision so we continue to the
            # next value in the for loop.
            if (
                col in possible_board
                or row - col in diagonal_right_collisions
                or row + col in diagonal_left_collisions
            ):
                  continue

            # If it is False we call dfs function again and we update the inputs
            depth_first_search(
                [*possible_board, col]     , [*diagonal_right_collisions, row - col]     , [*diagonal_left_collisions, row + col]     , a_     , a_     , )



def 				snake_case       (  a_				:			int						)							->					None:





      """simple docstring"""

      UpperCamelCase_					: list[list[str]]            =				[]
      depth_first_search([]     , []     , []     , a_     , a_						)

      # Print all the boards
      for board in boards:
            for column in board:
                  print(a_						)
            print(""""""						)

      print(len(a_						)     , """solutions were found."""						)


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      n_queens_solution(4)






