


'''simple docstring'''







lowerCAmelCase     :  str											=    {
    """A""": ["""B""", """C""", """E"""],
    """B""": ["""A""", """D""", """E"""],
    """C""": ["""A""", """F""", """G"""],
    """D""": ["""B"""],
    """E""": ["""A""", """B""", """D"""],
    """F""": ["""C"""],
    """G""": ["""C"""],
}






def       lowercase					(_A ,    _A ,    _A       ):







       """simple docstring"""







       _lowerCAmelCase     :				Optional[Any]       =							set()
       # keep track of all the paths to be checked
       _lowerCAmelCase     :				Any       =							[[start]]

       # return path if start is goal
       if start == goal:
              return [start]

       # keeps looping until all possible paths have been checked
       while queue:
              # pop the first path from the queue
              _lowerCAmelCase     :				List[str]       =							queue.pop(0       )
              # get the last node from the path
              _lowerCAmelCase     :				Optional[int]       =							path[-1]
              if node not in explored:
                     _lowerCAmelCase     :				int       =							graph[node]
                     # go through all neighbour nodes, construct a new path and
                     # push it into the queue
                     for neighbour in neighbours:
                            _lowerCAmelCase     :				List[str]       =							list(_A       )
                            new_path.append(_A       )
                            queue.append(_A       )
                            # return path if neighbour is goal
                            if neighbour == goal:
                                   return new_path

            # mark node as explored
                     explored.add(_A       )

    # in case there's no path between the 2 nodes
       return []






def       lowercase					(_A ,    _A ,    _A       ):







       """simple docstring"""







       if not graph or start not in graph or target not in graph:
              return -1
       if start == target:
              return 0
       _lowerCAmelCase     :				Tuple       =							[start]
       _lowerCAmelCase     :				int       =							set(_A       )
       # Keep tab on distances from `start` node.
       _lowerCAmelCase     :				Union[str, Any]       =							{start: 0, target: -1}
       while queue:
              _lowerCAmelCase     :				str       =							queue.pop(0       )
              if node == target:
                     _lowerCAmelCase     :				List[Any]       =							(
                         dist[node] if dist[target] == -1 else min(dist[target] ,    dist[node]       )
                     )
              for adjacent in graph[node]:
                     if adjacent not in visited:
                            visited.add(_A       )
                            queue.append(_A       )
                            _lowerCAmelCase     :				str       =							dist[node] + 1
       return dist[target]


if __name__ == "__main__":
       print(bfs_shortest_path(demo_graph, """G""", """D"""))  # returns ['G', 'C', 'A', 'B', 'D']
       print(bfs_shortest_path_distance(demo_graph, """G""", """D"""))  # returns 4





from __future__ import annotations

import math
import random
from typing import Any







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self  ):

						'''simple docstring'''


						UpperCamelCase__       =							[]
						UpperCamelCase__       =							0
						UpperCamelCase__       =							0




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.head == self.tail




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						self.data.append(snake_case  )
						UpperCamelCase__       =							self.tail + 1




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						UpperCamelCase__       =							self.data[self.head]
						UpperCamelCase__       =							self.head + 1
						return ret




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.tail - self.head







			def 					snake_case__					(				self  ):

						'''simple docstring'''


						print(self.data  )
						print("**************"  )
						print(self.data[self.head : self.tail]  )







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							data
						UpperCamelCase__       =							None
						UpperCamelCase__       =							None
						UpperCamelCase__       =							1




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.data




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.left




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.right




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.height




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							data




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							node




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							node







			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							height



def 							UpperCamelCase_(					_A :MyNode | None	)->		int:
			if node is None:
						return 0
			return node.get_height()
def 							UpperCamelCase_(					_A :int					,  _A :int	)->		int:
			if a > b:
						return a
			return b
def 							UpperCamelCase_(					_A :MyNode	)->		MyNode:
			print("left rotation node:"					,  node.get_data()	)
			UpperCamelCase__       =							node.get_left()
			assert ret is not None
			node.set_left(ret.get_right()	)
			ret.set_right(_A	)
			UpperCamelCase__       =							my_max(get_height(node.get_right()	)					,  get_height(node.get_left()	)	) + 1
			node.set_height(_A	)
			UpperCamelCase__       =							my_max(get_height(ret.get_right()	)					,  get_height(ret.get_left()	)	) + 1
			ret.set_height(_A	)
			return ret
def 							UpperCamelCase_(					_A :MyNode	)->		MyNode:
			print("right rotation node:"					,  node.get_data()	)
			UpperCamelCase__       =							node.get_right()
			assert ret is not None
			node.set_right(ret.get_left()	)
			ret.set_left(_A	)
			UpperCamelCase__       =							my_max(get_height(node.get_right()	)					,  get_height(node.get_left()	)	) + 1
			node.set_height(_A	)
			UpperCamelCase__       =							my_max(get_height(ret.get_right()	)					,  get_height(ret.get_left()	)	) + 1
			ret.set_height(_A	)
			return ret
def 							UpperCamelCase_(					_A :MyNode	)->		MyNode:
			UpperCamelCase__       =							node.get_left()
			assert left_child is not None
			node.set_left(left_rotation(_A	)	)
			return right_rotation(_A	)
def 							UpperCamelCase_(					_A :MyNode	)->		MyNode:
			UpperCamelCase__       =							node.get_right()
			assert right_child is not None
			node.set_right(right_rotation(_A	)	)
			return left_rotation(_A	)
def 							UpperCamelCase_(					_A :MyNode | None					,  _A :Any	)->		MyNode | None:
			if node is None:
						return MyNode(_A	)
			if data < node.get_data():
						node.set_left(insert_node(node.get_left()					,  _A	)	)
						if (
						    get_height(node.get_left()	) - get_height(node.get_right()	) == 2
						):  # an unbalance detected
									UpperCamelCase__       =							node.get_left()
									assert left_child is not None
									if (
									    data < left_child.get_data()
									):  # new node is the left child of the left child
												UpperCamelCase__       =							right_rotation(_A	)
									else:
												UpperCamelCase__       =							lr_rotation(_A	)
			else:
						node.set_right(insert_node(node.get_right()					,  _A	)	)
						if get_height(node.get_right()	) - get_height(node.get_left()	) == 2:
									UpperCamelCase__       =							node.get_right()
									assert right_child is not None
									if data < right_child.get_data():
												UpperCamelCase__       =							rl_rotation(_A	)
									else:
												UpperCamelCase__       =							left_rotation(_A	)
			UpperCamelCase__       =							my_max(get_height(node.get_right()	)					,  get_height(node.get_left()	)	) + 1
			node.set_height(_A	)
			return node
def 							UpperCamelCase_(					_A :MyNode	)->		Any:
			while True:
						UpperCamelCase__       =							root.get_right()
						if right_child is None:
									break
						UpperCamelCase__       =							right_child
			return root.get_data()
def 							UpperCamelCase_(					_A :MyNode	)->		Any:
			while True:
						UpperCamelCase__       =							root.get_left()
						if left_child is None:
									break
						UpperCamelCase__       =							left_child
			return root.get_data()
def 							UpperCamelCase_(					_A :MyNode					,  _A :Any	)->		MyNode | None:
			UpperCamelCase__       =							root.get_left()
			UpperCamelCase__       =							root.get_right()
			if root.get_data() == data:
						if left_child is not None and right_child is not None:
									UpperCamelCase__       =							get_left_most(_A	)
									root.set_data(_A	)
									root.set_right(del_node(_A					,  _A	)	)
						elif left_child is not None:
									UpperCamelCase__       =							left_child
						elif right_child is not None:
									UpperCamelCase__       =							right_child
						else:
									return None
			elif root.get_data() > data:
						if left_child is None:
									print("No such data"	)
									return root
						else:
									root.set_left(del_node(_A					,  _A	)	)
			else:  # root.get_data() < data
						if right_child is None:
									return root
						else:
									root.set_right(del_node(_A					,  _A	)	)

			if get_height(_A	) - get_height(_A	) == 2:
						assert right_child is not None
						if get_height(right_child.get_right()	) > get_height(right_child.get_left()	):
									UpperCamelCase__       =							left_rotation(_A	)
						else:
									UpperCamelCase__       =							rl_rotation(_A	)
			elif get_height(_A	) - get_height(_A	) == -2:
						assert left_child is not None
						if get_height(left_child.get_left()	) > get_height(left_child.get_right()	):
									UpperCamelCase__       =							right_rotation(_A	)
						else:
									UpperCamelCase__       =							lr_rotation(_A	)
			UpperCamelCase__       =							my_max(get_height(root.get_right()	)					,  get_height(root.get_left()	)	) + 1
			root.set_height(_A	)
			return root







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self  ):

						'''simple docstring'''


						UpperCamelCase__       =							None




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return get_height(self.root  )




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						print("insert:" + str(snake_case  )  )
						UpperCamelCase__       =							insert_node(self.root   ,    snake_case  )




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						print("delete:" + str(snake_case  )  )
						if self.root is None:
									print("Tree is empty!"  )
									return
						UpperCamelCase__       =							del_node(self.root   ,    snake_case  )







			def __str__(				self   ,    ):  # a level traversale, gives a more intuitive look on the tree

						'''simple docstring'''


						UpperCamelCase__       =							""
						UpperCamelCase__       =							MyQueue()
						q.push(self.root  )
						UpperCamelCase__       =							self.get_height()
						if layer == 0:
									return output
						UpperCamelCase__       =							0
						while not q.is_empty():
									UpperCamelCase__       =							q.pop()
									UpperCamelCase__       =							" " * int(math.pow(2   ,    layer - 1  )  )
									output += space
									if node is None:
												output += "*"
												q.push(snake_case  )
												q.push(snake_case  )
									else:
												output += str(node.get_data()  )
												q.push(node.get_left()  )
												q.push(node.get_right()  )
									output += space
									UpperCamelCase__       =							cnt + 1
									for i in range(100  ):
												if cnt == math.pow(2   ,    snake_case  ) - 1:
															UpperCamelCase__       =							layer - 1
															if layer == 0:
																		output += "\n*************************************"
																		return output
															output += "\n"
															break
						output += "\n*************************************"
						return output



def 							UpperCamelCase_(					)->		None:
			import doctest

			doctest.testmod()


if __name__ == "__main__":
						_test()
						__UpperCamelCase     		=							AVLtree()
						__UpperCamelCase     		=							list(range(1_0))
						random.shuffle(lst)
						for i in lst:
												t.insert(i)
												print(str(t))
						random.shuffle(lst)
						for i in lst:
												t.del_node(i)
												print(str(t))


