






"""simple docstring"""






from __future__ import annotations

UpperCAmelCase_  :					Optional[Any]       =					[]



def    _A     (__a       ,							__a       ,							__a				)					->			bool:
    """simple docstring"""






    for i in range(len(_lowerCamelCase				)				):
        if board[row][i] == 1:
            return False
    for i in range(len(_lowerCamelCase				)				):
        if board[i][column] == 1:
            return False
    for i, j in zip(range(_lowerCamelCase       ,							-1       ,							-1				)       ,							range(_lowerCamelCase       ,							-1       ,							-1				)				):
        if board[i][j] == 1:
            return False
    for i, j in zip(range(_lowerCamelCase       ,							-1       ,							-1				)       ,							range(_lowerCamelCase       ,							len(_lowerCamelCase				)				)				):
        if board[i][j] == 1:
            return False
    return True



def    _A     (__a       ,							__a				)					->			bool:
    """simple docstring"""






    if row >= len(_lowerCamelCase				):
        solution.append(_lowerCamelCase				)
        printboard(_lowerCamelCase				)
        print()
        return True
    for i in range(len(_lowerCamelCase				)				):
        if is_safe(_lowerCamelCase       ,							_lowerCamelCase       ,							_lowerCamelCase				):
            SCREAMING_SNAKE_CASE_ :    Dict       		=						1
            solve(_lowerCamelCase       ,							row + 1				)
            SCREAMING_SNAKE_CASE_ :    Union[str, Any]       		=						0
    return False



def    _A     (__a				)					->			None:
    """simple docstring"""






    for i in range(len(_lowerCamelCase				)				):
        for j in range(len(_lowerCamelCase				)				):
            if board[i][j] == 1:
                print('''Q'''       ,							end=''' '''				)
            else:
                print('''.'''       ,							end=''' '''				)
        print()


# n=int(input("The no. of queens"))
UpperCAmelCase_  :					Tuple       =					8
UpperCAmelCase_  :					Any       =					[[0 for i in range(n)] for j in range(n)]
solve(board, 0)





print("""The total no. of solutions are :""", len(solution))




"""simple docstring"""






class 			lowercase					:






			def __init__(self  :	Dict			)       ->	List[Any]:





				"""simple docstring"""


				lowerCAmelCase												=  {}






			def 					UpperCAmelCase							(self  :	Union[str, Any]			)       ->	None:





				"""simple docstring"""


				print(self.vertex			)
				for i in self.vertex:
					print(SCREAMING_SNAKE_CASE_      ,''' -> '''      ,''' -> '''.join([str(SCREAMING_SNAKE_CASE_			) for j in self.vertex[i]]			)			)






			def 					UpperCAmelCase							(self  :	Optional[Any]      ,SCREAMING_SNAKE_CASE_  :	int      ,SCREAMING_SNAKE_CASE_  :	int			)       ->	None:





				"""simple docstring"""


				if from_vertex in self.vertex:
					self.vertex[from_vertex].append(SCREAMING_SNAKE_CASE_			)
				else:
					# else make a new vertex
					lowerCAmelCase												=  [to_vertex]






			def 					UpperCAmelCase							(self  :	List[str]			)       ->	None:





				"""simple docstring"""


				lowerCAmelCase												=  [False] * len(self.vertex			)

				# call the recursive helper function
				for i in range(len(self.vertex			)			):
					if not visited[i]:
						self.dfs_recursive(SCREAMING_SNAKE_CASE_      ,SCREAMING_SNAKE_CASE_			)






			def 					UpperCAmelCase							(self  :	Optional[Any]      ,SCREAMING_SNAKE_CASE_  :	int      ,SCREAMING_SNAKE_CASE_  :	list			)       ->	None:





				"""simple docstring"""


				lowerCAmelCase												=  True

				print(SCREAMING_SNAKE_CASE_      ,end=''' '''			)

				# Recur for all the vertices that are adjacent to this node
				for i in self.vertex:
					if not visited[i]:
						self.dfs_recursive(SCREAMING_SNAKE_CASE_      ,SCREAMING_SNAKE_CASE_			)


if __name__ == "__main__":
					UpperCAmelCase        =				Graph()
					g.add_edge(0, 1)
					g.add_edge(0, 2)
					g.add_edge(1, 2)
					g.add_edge(2, 0)
					g.add_edge(2, 3)
					g.add_edge(3, 3)

					g.print_graph()
					print("""DFS:""")
					g.dfs()

					# OUTPUT:
					# 0  ->  1 -> 2
					# 1  ->  2
					# 2  ->  0 -> 3
					# 3  ->  3
					# DFS:
					#  0 1 2 3


