



"""simple docstring"""






from __future__ import annotations

import time

snake_case   					=				list[tuple[int, int]]

snake_case   					=				[
    [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],
]

snake_case   					=				[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right



class     UpperCAmelCase    :



   def __init__(       self    :	Any							,       __lowerCamelCase    :	int							,       __lowerCamelCase    :	int							,       __lowerCamelCase    :	int							,       __lowerCamelCase    :	int							,       __lowerCamelCase    :	Node | None				):



     """simple docstring"""
     _snake_case   	=      pos_x
     _snake_case   	=      pos_y
     _snake_case   	=      (pos_y, pos_x)
     _snake_case   	=      goal_x
     _snake_case   	=      goal_y
     _snake_case   	=      parent



class     UpperCAmelCase    :



   def __init__(       self    :	List[str]							,       __lowerCamelCase    :	tuple[int, int]							,       __lowerCamelCase    :	tuple[int, int]				):



     """simple docstring"""
     _snake_case   	=      Node(start[1]							,       start[0]							,       goal[1]							,       goal[0]							,       __lowerCamelCase				)
     _snake_case   	=      Node(goal[1]							,       goal[0]							,       goal[1]							,       goal[0]							,       __lowerCamelCase				)

     _snake_case   	=      [self.start]
     _snake_case   	=      False



   def    __UpperCAmelCase    (       self    :	int				):



     """simple docstring"""
     while self.node_queue:
       _snake_case   	=      self.node_queue.pop(0				)

       if current_node.pos == self.target.pos:
         _snake_case   	=      True
         return self.retrace_path(__lowerCamelCase				)

       _snake_case   	=      self.get_successors(__lowerCamelCase				)

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

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



   def    __UpperCAmelCase    (       self    :	str							,       __lowerCamelCase    :	Node				):



     """simple docstring"""
     _snake_case   	=      []
     for action in delta:
       _snake_case   	=      parent.pos_x + action[1]
       _snake_case   	=      parent.pos_y + action[0]
       if not (0 <= pos_x <= len(grid[0]				) - 1 and 0 <= pos_y <= len(__lowerCamelCase				) - 1):
         continue

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

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





   def    __UpperCAmelCase    (       self    :	str							,       __lowerCamelCase    :	Node | None				):



     """simple docstring"""
     _snake_case   	=      node
     _snake_case   	=      []
     while current_node is not None:
       path.append((current_node.pos_y, current_node.pos_x)				)
       _snake_case   	=      current_node.parent
     path.reverse()
     return path



class     UpperCAmelCase    :



   def __init__(       self    :	Tuple							,       __lowerCamelCase    :	List[Any]							,       __lowerCamelCase    :	Optional[int]				):



     """simple docstring"""
     _snake_case   	=      BreadthFirstSearch(__lowerCamelCase							,       __lowerCamelCase				)
     _snake_case   	=      BreadthFirstSearch(__lowerCamelCase							,       __lowerCamelCase				)
     _snake_case   	=      False



   def    __UpperCAmelCase    (       self    :	List[str]				):



     """simple docstring"""
     while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
       _snake_case   	=      self.fwd_bfs.node_queue.pop(0				)
       _snake_case   	=      self.bwd_bfs.node_queue.pop(0				)

       if current_bwd_node.pos == current_fwd_node.pos:
         _snake_case   	=      True
         return self.retrace_bidirectional_path(
             __lowerCamelCase							,       __lowerCamelCase				)

       _snake_case   	=      current_bwd_node
       _snake_case   	=      current_fwd_node

       _snake_case   	=      {
           self.fwd_bfs: self.fwd_bfs.get_successors(__lowerCamelCase				),
           self.bwd_bfs: self.bwd_bfs.get_successors(__lowerCamelCase				),
       }

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

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





   def    __UpperCAmelCase    (       self    :	Union[str, Any]							,       __lowerCamelCase    :	Node							,       __lowerCamelCase    :	Node				):



     """simple docstring"""
     _snake_case   	=      self.fwd_bfs.retrace_path(__lowerCamelCase				)
     _snake_case   	=      self.bwd_bfs.retrace_path(__lowerCamelCase				)
     bwd_path.pop()
     bwd_path.reverse()
     _snake_case   	=      fwd_path + bwd_path
     return path


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

     doctest.testmod()
     snake_case   					=				(0, 0)
     snake_case   					=				(len(grid) - 1, len(grid[0]) - 1)
     for elem in grid:
          print(elem)

     snake_case   					=				time.time()
     snake_case   					=				BreadthFirstSearch(init, goal)
     snake_case   					=				bfs.search()
     snake_case   					=				time.time() - start_bfs_time

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

     snake_case   					=				time.time()
     snake_case   					=				BidirectionalBreadthFirstSearch(init, goal)
     snake_case   					=				bd_bfs.search()
     snake_case   					=				time.time() - start_bd_bfs_time

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












'''simple docstring'''




def 			_lowerCAmelCase     (    __snake_case    :					Optional[Any]     )	->	Optional[Any]:  # noqa: E741
     __A		:					Tuple						=			len(__snake_case     )
     __A		:					Optional[int]						=			0
     __A		:					str						=			[0] * n
     __A		:					int						=			[False] * n
     __A		:					Tuple						=			[False] * n

     def dfs(__snake_case    :					List[str]					,				__snake_case    :					List[Any]					,				__snake_case    :					Optional[Any]					,				__snake_case    :					int     ):
          if parent == root:
               out_edge_count += 1
          __A		:					str						=			True
          __A		:					Tuple						=			at

          for to in l[at]:
               if to == parent:
                    pass
               elif not visited[to]:
                    __A		:					Optional[int]						=			dfs(__snake_case					,				__snake_case					,				__snake_case					,				__snake_case     )
                    __A		:					int						=			min(low[at]					,				low[to]     )

                    # AP found via bridge
                    if at < low[to]:
                         __A		:					Tuple						=			True
                    # AP found via cycle
                    if at == low[to]:
                         __A		:					Optional[Any]						=			True
               else:
                    __A		:					Any						=			min(low[at]					,				__snake_case     )
          return out_edge_count

     for i in range(__snake_case     ):
          if not visited[i]:
               __A		:					Tuple						=			0
               __A		:					List[Any]						=			dfs(__snake_case					,				__snake_case					,				-1					,				__snake_case     )
               __A		:					Union[str, Any]						=			out_edge_count > 1

     for x in range(len(__snake_case     )     ):
          if is_art[x] is True:
               print(__snake_case     )


# Adjacency list of graph
lowercase__       : Tuple         =       {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3, 5],
    3: [2, 4],
    4: [3],
    5: [2, 6, 8],
    6: [5, 7],
    7: [6, 8],
    8: [5, 7],
}







compute_ap(data)