
from __future__ import annotations

from queue import Queue


class 			UpperCamelCase_				:




      '''simple docstring'''







      def __init__( self):
            lowerCAmelCase_						=      {}







      def lowercase__		( self):







            for i in self.vertices:
                  print(__SCREAMING_SNAKE_CASE					,					''' : '''					,					''' -> '''.join([str(__SCREAMING_SNAKE_CASE) for j in self.vertices[i]]))







      def lowercase__		( self					,					_UpperCAmelCase					,					_UpperCAmelCase):







            if from_vertex in self.vertices:
                  self.vertices[from_vertex].append(__SCREAMING_SNAKE_CASE)
            else:
                  lowerCAmelCase_						=      [to_vertex]







      def lowercase__		( self					,					_UpperCAmelCase):
            lowerCAmelCase_						=      set()

            # create a first in first out queue to store all the vertices for BFS
            lowerCAmelCase_						=      Queue()

            # mark the source node as visited and enqueue it
            visited.add(__SCREAMING_SNAKE_CASE)
            queue.put(__SCREAMING_SNAKE_CASE)

            while not queue.empty():
                  lowerCAmelCase_						=      queue.get()

                  # loop through all adjacent vertex and enqueue it if not yet visited
                  for adjacent_vertex in self.vertices[vertex]:
                        if adjacent_vertex not in visited:
                              queue.put(__SCREAMING_SNAKE_CASE)
                              visited.add(__SCREAMING_SNAKE_CASE)
            return visited


if __name__ == "__main__":
 from doctest import testmod

 testmod(verbose=True)

 _snake_case		  =   Graph()
 g.add_edge(0, 1)
 g.add_edge(0, 2)
 g.add_edge(1, 2)
 g.add_edge(2, 0)
 g.add_edge(2, 3)
 g.add_edge(3, 3)

 g.print_graph()
 # 0  :  1 -> 2
 # 1  :  2
 # 2  :  0 -> 3
 # 3  :  3

 assert sorted(g.bfs(2)) == [0, 1, 2, 3]







def 	_lowerCamelCase  (		A_  :	Union[str, Any]							,  A_  :	Optional[int]      )			->			Dict:

   '''simple docstring'''






   if len(str(A_      )      ) == 1 or len(str(A_      )      ) == 1:
      return a * b

   UpperCamelCase__ :			Any 						=max(len(str(A_      )      )							,  len(str(A_      )      )      )
   UpperCamelCase__ :			Optional[int] 						=ma // 2

   UpperCamelCase__						,	UpperCamelCase__ :			Dict 						=divmod(A_							,  1_0**ma      )
   UpperCamelCase__						,	UpperCamelCase__ :			Union[str, Any] 						=divmod(A_							,  1_0**ma      )

   UpperCamelCase__ :			List[Any] 						=karatsuba(A_							,  A_      )
   UpperCamelCase__ :			Dict 						=karatsuba((aa + aa)							,  (ba + ba)      )
   UpperCamelCase__ :			Optional[int] 						=karatsuba(A_							,  A_      )

   return (z * 1_0 ** (2 * ma)) + ((y - z - x) * 1_0 ** (ma)) + (x)
def 	_lowerCamelCase  (		)			->			Any:

   '''simple docstring'''






   print(karatsuba(1_5_4_6_3							,  2_3_4_8_9      )      )


if __name__ == "__main__":
     main()

