import math
class    A_ :

  def __init__(		self :      List[str]     ,							__SCREAMING_SNAKE_CASE :      Union[str, Any]=0       ):  # a graph with Node 0,1,...,N-1
   __a       =  n
   __a       =  [
       [math.inf for j in range(0     ,							__SCREAMING_SNAKE_CASE       )] for i in range(0     ,							__SCREAMING_SNAKE_CASE       )
   ]  # adjacency matrix for weight
   __a       =  [
       [math.inf for j in range(0     ,							__SCREAMING_SNAKE_CASE       )] for i in range(0     ,							__SCREAMING_SNAKE_CASE       )
   ]  # dp[i][j] stores minimum distance from i to j

  def 		_UpperCAmelCase   (		self :      List[str]     ,							__SCREAMING_SNAKE_CASE :      str     ,							__SCREAMING_SNAKE_CASE :      Tuple     ,							__SCREAMING_SNAKE_CASE :      Tuple       ):
   __a       =  w

  def 		_UpperCAmelCase   (		self :      List[Any]       ):
   for k in range(0     ,							self.n       ):
    for i in range(0     ,							self.n       ):
     for j in range(0     ,							self.n       ):
      __a       =  min(self.dp[i][j]     ,							self.dp[i][k] + self.dp[k][j]       )

  def 		_UpperCAmelCase   (		self :      Optional[Any]     ,							__SCREAMING_SNAKE_CASE :      Tuple     ,							__SCREAMING_SNAKE_CASE :      Dict       ):
   return self.dp[u][v]


if __name__ == "__main__":
  SCREAMING_SNAKE_CASE :	Tuple							     =		Graph(5)
  graph.add_edge(0, 2, 9)
  graph.add_edge(0, 4, 10)
  graph.add_edge(1, 3, 5)
  graph.add_edge(2, 3, 7)
  graph.add_edge(3, 0, 10)
  graph.add_edge(3, 1, 2)
  graph.add_edge(3, 2, 1)
  graph.add_edge(3, 4, 6)
  graph.add_edge(4, 1, 3)
  graph.add_edge(4, 2, 4)
  graph.add_edge(4, 3, 9)
  graph.floyd_warshall()
  graph.show_min(1, 4)
  graph.show_min(0, 3)



from __future__ import annotations

SCREAMING_SNAKE_CASE :	Optional[int]							     =		[]



def   __A		(			_A							,				_A							,				_A					):



 """simple docstring"""


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



def   __A		(			_A							,				_A					):



 """simple docstring"""


 if row >= len(_A					):
  solution.append(_A					)
  printboard(_A					)
  print()
  return True
 for i in range(len(_A					)					):
  if is_safe(_A							,				_A							,				_A					):
   __a       =  1
   solve(_A							,				row + 1					)
   __a       =  0
 return False



def   __A		(			_A					):



 """simple docstring"""


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


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






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


