

from __future__ import annotations

import time

__lowercase     : Optional[Any]       =						list[tuple[int, int]]

__lowercase     : Tuple       =						[
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

__lowercase     : Optional[Any]       =						[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right



class 						_A     :





  '''simple docstring'''



  def __init__(  self   ,SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_    ):

      '''simple docstring'''
      snake_case							:		Tuple        =		pos_x
      snake_case							:		List[str]        =		pos_y
      snake_case							:		Optional[int]        =		(pos_y, pos_x)
      snake_case							:		List[str]        =		goal_x
      snake_case							:		str        =		goal_y
      snake_case							:		int        =		parent







class 						_A     :





  '''simple docstring'''



  def __init__(  self   ,SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_    ):

      '''simple docstring'''
      snake_case							:		Union[str, Any]        =		Node(start[1]   ,start[0]   ,goal[1]   ,goal[0]   ,SCREAMING_SNAKE_CASE_    )
      snake_case							:		List[Any]        =		Node(goal[1]   ,goal[0]   ,goal[1]   ,goal[0]   ,SCREAMING_SNAKE_CASE_    )

      snake_case							:		Optional[int]        =		[self.start]
      snake_case							:		int        =		False





  def    snake_case_       (  self    ):

      '''simple docstring'''
      while self.node_queue:
          snake_case							:		Any        =		self.node_queue.pop(0    )

          if current_node.pos == self.target.pos:
              snake_case							:		List[Any]        =		True
              return self.retrace_path(SCREAMING_SNAKE_CASE_    )

          snake_case							:		Dict        =		self.get_successors(SCREAMING_SNAKE_CASE_    )

          for node in successors:
              self.node_queue.append(SCREAMING_SNAKE_CASE_    )

      if not self.reached:
          return [self.start.pos]
      return None





  def    snake_case_       (  self   ,SCREAMING_SNAKE_CASE_    ):

      '''simple docstring'''
      snake_case							:		int        =		[]
      for action in delta:
          snake_case							:		Optional[Any]        =		parent.pos_x + action[1]
          snake_case							:		Optional[Any]        =		parent.pos_y + action[0]
          if not (0 <= pos_x <= len(grid[0]    ) - 1 and 0 <= pos_y <= len(SCREAMING_SNAKE_CASE_    ) - 1):
              continue

          if grid[pos_y][pos_x] != 0:
              continue

          successors.append(
              Node(SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_   ,self.target.pos_y   ,self.target.pos_x   ,SCREAMING_SNAKE_CASE_    )    )
      return successors





  def    snake_case_       (  self   ,SCREAMING_SNAKE_CASE_    ):

      '''simple docstring'''
      snake_case							:		List[Any]        =		node
      snake_case							:		List[str]        =		[]
      while current_node is not None:
          path.append((current_node.pos_y, current_node.pos_x)    )
          snake_case							:		Any        =		current_node.parent
      path.reverse()
      return path







class 						_A     :





  '''simple docstring'''



  def __init__(  self   ,SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_    ):

      '''simple docstring'''
      snake_case							:		int        =		BreadthFirstSearch(SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_    )
      snake_case							:		Any        =		BreadthFirstSearch(SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_    )
      snake_case							:		int        =		False





  def    snake_case_       (  self    ):

      '''simple docstring'''
      while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
          snake_case							:		List[str]        =		self.fwd_bfs.node_queue.pop(0    )
          snake_case							:		Union[str, Any]        =		self.bwd_bfs.node_queue.pop(0    )

          if current_bwd_node.pos == current_fwd_node.pos:
              snake_case							:		Optional[int]        =		True
              return self.retrace_bidirectional_path(
                  SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_    )

          snake_case							:		Tuple        =		current_bwd_node
          snake_case							:		Any        =		current_fwd_node

          snake_case							:		Optional[Any]        =		{
              self.fwd_bfs: self.fwd_bfs.get_successors(SCREAMING_SNAKE_CASE_    ),
              self.bwd_bfs: self.bwd_bfs.get_successors(SCREAMING_SNAKE_CASE_    ),
          }

          for bfs in [self.fwd_bfs, self.bwd_bfs]:
              for node in successors[bfs]:
                  bfs.node_queue.append(SCREAMING_SNAKE_CASE_    )

      if not self.reached:
          return [self.fwd_bfs.start.pos]
      return None





  def    snake_case_       (  self   ,SCREAMING_SNAKE_CASE_   ,SCREAMING_SNAKE_CASE_    ):

      '''simple docstring'''
      snake_case							:		Dict        =		self.fwd_bfs.retrace_path(SCREAMING_SNAKE_CASE_    )
      snake_case							:		List[Any]        =		self.bwd_bfs.retrace_path(SCREAMING_SNAKE_CASE_    )
      bwd_path.pop()
      bwd_path.reverse()
      snake_case							:		Optional[Any]        =		fwd_path + bwd_path
      return path


if __name__ == "__main__":
     # all coordinates are given in format [y,x]
     import doctest

     doctest.testmod()
     __lowercase     : List[Any]       =						(0, 0)
     __lowercase     : Optional[int]       =						(len(grid) - 1, len(grid[0]) - 1)
     for elem in grid:
          print(elem)

     __lowercase     : Optional[int]       =						time.time()
     __lowercase     : Optional[int]       =						BreadthFirstSearch(init, goal)
     __lowercase     : Any       =						bfs.search()
     __lowercase     : List[str]       =						time.time() - start_bfs_time

     print('''Unidirectional BFS computation time : ''', bfs_time)

     __lowercase     : List[str]       =						time.time()
     __lowercase     : Dict       =						BidirectionalBreadthFirstSearch(init, goal)
     __lowercase     : Union[str, Any]       =						bd_bfs.search()
     __lowercase     : Optional[Any]       =						time.time() - start_bd_bfs_time

     print('''Bidirectional BFS computation time : ''', bd_bfs_time)










'''simple docstring'''




def 		__A		(  lowerCamelCase_			,			lowerCamelCase_	):


		"""simple docstring"""



		SCREAMING_SNAKE_CASE :				str		=			1  # To kept the Calculated Value
		# Since C(n, k) = C(n, n-k)
		if k > (n - k):
				SCREAMING_SNAKE_CASE :				Dict		=			n - k
		# Calculate C(n,k)
		for i in range(lowerCamelCase_	):
				result *= n - i
				result //= i + 1
		return result



def 		__A		(  lowerCamelCase_	):


		"""simple docstring"""



		return binomial_coefficient(2 * node_count			,			lowerCamelCase_	) // (node_count + 1)



def 		__A		(  lowerCamelCase_	):


		"""simple docstring"""



		if n < 0:
				raise ValueError("""factorial() not defined for negative values"""	)
		SCREAMING_SNAKE_CASE :				Dict		=			1
		for i in range(1			,			n + 1	):
				result *= i
		return result



def 		__A		(  lowerCamelCase_	):


		"""simple docstring"""



		return catalan_number(lowerCamelCase_	) * factorial(lowerCamelCase_	)


if __name__ == "__main__":
							__UpperCAmelCase            =       int(input("""Enter the number of nodes: """).strip() or 0)
							if node_count <= 0:
														raise ValueError("""We need some nodes to work with.""")
							print(
							    f'''Given {node_count} nodes, there are {binary_tree_count(node_count)} '''
							    f'''binary trees and {catalan_number(node_count)} binary search trees.'''
							)



