

'''simple docstring'''







__lowerCamelCase									=     {
    '''A''': ['''B''', '''C''', '''E'''],
    '''B''': ['''A''', '''D''', '''E'''],
    '''C''': ['''A''', '''F''', '''G'''],
    '''D''': ['''B'''],
    '''E''': ['''A''', '''B''', '''D'''],
    '''F''': ['''C'''],
    '''G''': ['''C'''],
}
def    UpperCAmelCase__     (   UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__					)      ->      list[str]:
       A_						       =   set()
       # keep track of all the paths to be checked
       A_						       =   [[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
              A_						       =   queue.pop(0					)
              # get the last node from the path
              A_						       =   path[-1]
              if node not in explored:
                     A_						       =   graph[node]
                     # go through all neighbour nodes, construct a new path and
                     # push it into the queue
                     for neighbour in neighbours:
                            A_						       =   list(UpperCAmelCase__					)
                            new_path.append(UpperCAmelCase__					)
                            queue.append(UpperCAmelCase__					)
                            # return path if neighbour is goal
                            if neighbour == goal:
                                   return new_path

            # mark node as explored
                     explored.add(UpperCAmelCase__					)

    # in case there's no path between the 2 nodes
       return []
def    UpperCAmelCase__     (   UpperCAmelCase__,							UpperCAmelCase__,							UpperCAmelCase__					)      ->      int:
       if not graph or start not in graph or target not in graph:
              return -1
       if start == target:
              return 0
       A_						       =   [start]
       A_						       =   set(UpperCAmelCase__					)
       # Keep tab on distances from `start` node.
       A_						       =   {start: 0, target: -1}
       while queue:
              A_						       =   queue.pop(0					)
              if node == target:
                     A_						       =   (
                         dist[node] if dist[target] == -1 else min(dist[target],							dist[node]					)
                     )
              for adjacent in graph[node]:
                     if adjacent not in visited:
                            visited.add(UpperCAmelCase__					)
                            queue.append(UpperCAmelCase__					)
                            A_						       =   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



'''simple docstring'''







from __future__ import annotations

import math
import random
from typing import Any


class        A__   :



    def __init__(       self							)    ->   None:





           '''simple docstring'''
           A_						       =   []
           A_						       =   0
           A_						       =   0



    def        snake_case_      (       self							)    ->   bool:





           '''simple docstring'''
           return self.head == self.tail



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           self.data.append(UpperCamelCase__							)
           A_						       =   self.tail + 1



    def        snake_case_      (       self							)    ->   Any:





           '''simple docstring'''
           A_						       =   self.data[self.head]
           A_						       =   self.head + 1
           return ret



    def        snake_case_      (       self							)    ->   int:





           '''simple docstring'''
           return self.tail - self.head







    def        snake_case_      (       self							)    ->   None:





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


class        A__   :



    def __init__(       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           A_						       =   data
           A_						       =   None
           A_						       =   None
           A_						       =   1



    def        snake_case_      (       self							)    ->   Any:





           '''simple docstring'''
           return self.data



    def        snake_case_      (       self							)    ->   MyNode | None:





           '''simple docstring'''
           return self.left



    def        snake_case_      (       self							)    ->   MyNode | None:





           '''simple docstring'''
           return self.right



    def        snake_case_      (       self							)    ->   int:





           '''simple docstring'''
           return self.height



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           A_						       =   data



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           A_						       =   node



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           A_						       =   node







    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           A_						       =   height

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

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


class        A__   :



    def __init__(       self							)    ->   None:





           '''simple docstring'''
           A_						       =   None



    def        snake_case_      (       self							)    ->   int:





           '''simple docstring'''
           return get_height(self.root							)



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           print("""insert:""" + str(UpperCamelCase__							)							)
           A_						       =   insert_node(self.root		,					UpperCamelCase__							)



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





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







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





           '''simple docstring'''
           A_						       =   """"""
           A_						       =   MyQueue()
           q.push(self.root							)
           A_						       =   self.get_height()
           if layer == 0:
                  return output
           A_						       =   0
           while not q.is_empty():
                  A_						       =   q.pop()
                  A_						       =   """ """ * int(math.pow(2		,					layer - 1							)							)
                  output += space
                  if node is None:
                         output += "*"
                         q.push(UpperCamelCase__							)
                         q.push(UpperCamelCase__							)
                  else:
                         output += str(node.get_data()							)
                         q.push(node.get_left()							)
                         q.push(node.get_right()							)
                  output += space
                  A_						       =   cnt + 1
                  for i in range(100							):
                         if cnt == math.pow(2		,					UpperCamelCase__							) - 1:
                                A_						       =   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()
      __lowerCamelCase									=     AVLtree()
      __lowerCamelCase									=     list(range(10))
      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))
