





from collections.abc import Iterable
from typing import Any


class       __lowerCAmelCase					:


	'''simple docstring'''





	def __init__(						self:						List[str],					lowerCamelCase_:						int | None = None			):
			lowercase__					:      List[str]      =		value
			lowercase__					:      Node | None      =		None  # Added in order to delete a node easier
			lowercase__					:      Node | None      =		None
			lowercase__					:      Node | None      =		None





	def __repr__(						self:						Any			):
			from pprint import pformat

			if self.left is None and self.right is None:
					return str(self.value			)
			return pformat({F"""{self.value}""": (self.left, self.right)},					indent=1			)


class       __lowerCAmelCase					:


	'''simple docstring'''





	def __init__(						self:						Optional[int],					lowerCamelCase_:						Node | None = None			):
			lowercase__					:      Dict      =		root

	def __str__(						self:						Union[str, Any]			):
			return str(self.root			)

	def    snake_case__(						self:						Tuple,					lowerCamelCase_:						Node,					lowerCamelCase_:						Node | None			):
			if new_children is not None:  # reset its kids
					lowercase__					:      Tuple      =		node.parent
			if node.parent is not None:  # reset its parent
					if self.is_right(lowerCamelCase_			):  # If it is the right children
							lowercase__					:      Any      =		new_children
					else:
							lowercase__					:      Dict      =		new_children
			else:
					lowercase__					:      Union[str, Any]      =		new_children

	def    snake_case__(						self:						List[Any],					lowerCamelCase_:						Node			):
			if node.parent and node.parent.right:
					return node == node.parent.right
			return False

	def    snake_case__(						self:						Any			):
			return self.root is None

	def    snake_case__(						self:						int,					lowerCamelCase_:						str			):
			lowercase__					:      Union[str, Any]      =		Node(lowerCamelCase_			)  # create a new Node
			if self.empty():  # if Tree is empty
					lowercase__					:      Dict      =		new_node  # set its root
			else:  # Tree is not empty
					lowercase__					:      List[Any]      =		self.root  # from root
					if parent_node is None:
							return
					while True:  # While we don't get to a leaf
							if value < parent_node.value:  # We go left
									if parent_node.left is None:
											lowercase__					:      List[Any]      =		new_node  # We insert the new node in a leaf
											break
									else:
											lowercase__					:      Dict      =		parent_node.left
							else:
									if parent_node.right is None:
											lowercase__					:      Optional[int]      =		new_node
											break
									else:
											lowercase__					:      Any      =		parent_node.right
					lowercase__					:      Union[str, Any]      =		parent_node

	def    snake_case__(						self:						str,					*lowerCamelCase_:						Union[str, Any]			):
			for value in values:
					self.__insert(lowerCamelCase_			)

	def    snake_case__(						self:						Any,					lowerCamelCase_:						Union[str, Any]			):
			if self.empty():
					raise IndexError('Warning: Tree is empty! please use another.'			)
			else:
					lowercase__					:      List[Any]      =		self.root
					# use lazy evaluation here to avoid NoneType Attribute error
					while node is not None and node.value is not value:
							lowercase__					:      List[Any]      =		node.left if value < node.value else node.right
					return node

	def    snake_case__(						self:						Union[str, Any],					lowerCamelCase_:						Node | None = None			):
			if node is None:
					if self.root is None:
							return None
					lowercase__					:      str      =		self.root

			if not self.empty():
					while node.right is not None:
							lowercase__					:      int      =		node.right
			return node

	def    snake_case__(						self:						Dict,					lowerCamelCase_:						Node | None = None			):
			if node is None:
					lowercase__					:      List[str]      =		self.root
			if self.root is None:
					return None
			if not self.empty():
					lowercase__					:      List[Any]      =		self.root
					while node.left is not None:
							lowercase__					:      Any      =		node.left
			return node

	def    snake_case__(						self:						Any,					lowerCamelCase_:						int			):
			lowercase__					:      Tuple      =		self.search(lowerCamelCase_			)  # Look for the node with that label
			if node is not None:
					if node.left is None and node.right is None:  # If it has no children
							self.__reassign_nodes(lowerCamelCase_,					lowerCamelCase_			)
					elif node.left is None:  # Has only right children
							self.__reassign_nodes(lowerCamelCase_,					node.right			)
					elif node.right is None:  # Has only left children
							self.__reassign_nodes(lowerCamelCase_,					node.left			)
					else:
							lowercase__					:      List[str]      =		self.get_max(
							    node.left			)  # Gets the max value of the left branch
							self.remove(tmp_node.value			)  # type: ignore
							lowercase__					:      int      =		(
							    tmp_node.value  # type: ignore
							)  # Assigns the value to the node to delete and keep tree structure

	def    snake_case__(						self:						Tuple,					lowerCamelCase_:						Node | None			):
			if node is not None:
					yield node  # Preorder Traversal
					yield from self.preorder_traverse(node.left			)
					yield from self.preorder_traverse(node.right			)

	def    snake_case__(						self:						List[str],					lowerCamelCase_:						Union[str, Any]=None			):
			if traversal_function is None:
					return self.preorder_traverse(self.root			)
			else:
					return traversal_function(self.root			)

	def    snake_case__(						self:						Any,					lowerCamelCase_:						list,					lowerCamelCase_:						Node | None			):
			if node:
					self.inorder(lowerCamelCase_,					node.left			)
					arr.append(node.value			)
					self.inorder(lowerCamelCase_,					node.right			)





	def    snake_case__(						self:						int,					lowerCamelCase_:						int,					lowerCamelCase_:						Node			):
			lowercase__					:      list[int]      =		[]
			self.inorder(lowerCamelCase_,					lowerCamelCase_			)  # append all values to list using inorder traversal
			return arr[k - 1]


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : Node | None			)   ->							list[Node]:




		'''simple docstring'''
		lowercase__					:      Optional[int]      =		[]
		if curr_node is not None:
				lowercase__					:      int      =		postorder(curr_node.left			) + postorder(curr_node.right			) + [curr_node]
		return node_list


def       SCREAMING_SNAKE_CASE__  (       )   ->							None:




		'''simple docstring'''
		lowercase__					:      Tuple      =		(8, 3, 6, 1, 10, 14, 13, 4, 7)
		lowercase__					:      Optional[Any]      =		BinarySearchTree()
		for i in testlist:
				t.insert(_lowercase			)

		# Prints all the elements of the list in order traversal
		print(_lowercase			)

		if t.search(6			) is not None:
				print('The value 6 exists'			)
		else:
				print('The value 6 doesn\'t exist'			)

		if t.search(-1			) is not None:
				print('The value -1 exists'			)
		else:
				print('The value -1 doesn\'t exist'			)

		if not t.empty():
				print('Max Value: '   ,    t.get_max().value			)  # type: ignore
				print('Min Value: '   ,    t.get_min().value			)  # type: ignore

		for i in testlist:
				t.remove(_lowercase			)
				print(_lowercase			)


if __name__ == "__main__":
			import doctest

			doctest.testmod(verbose=True)









from __future__ import annotations


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : list[float]   ,    _lowercase     : Tuple			)   ->							int:




		'''simple docstring'''
		print(f"""Vertex\tShortest Distance from vertex {src}"""			)
		for i, d in enumerate(_lowercase			):
				print(f"""{i}\t\t{d}"""			)


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : list[dict[str, int]]   ,    _lowercase     : list[float]   ,    _lowercase     : int			)   ->							Any:




		'''simple docstring'''
		for j in range(_lowercase			):
				lowercase__   ,				lowercase__   ,				lowercase__					:      Dict      =		(graph[j][k] for k in ['src', 'dst', 'weight'])
				if distance[u] != float('inf'			) and distance[u] + w < distance[v]:
						return True
		return False


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : list[dict[str, int]]   ,    _lowercase     : int   ,    _lowercase     : int   ,    _lowercase     : int			)   ->							list[float]:




		'''simple docstring'''
		lowercase__					:      Dict      =		[float('inf'			)] * vertex_count
		lowercase__					:      Dict      =		0.0

		for _ in range(vertex_count - 1			):
				for j in range(_lowercase			):
						lowercase__   ,				lowercase__   ,				lowercase__					:      int      =		(graph[j][k] for k in ['src', 'dst', 'weight'])

						if distance[u] != float('inf'			) and distance[u] + w < distance[v]:
								lowercase__					:      str      =		distance[u] + w

		lowercase__					:      str      =		check_negative_cycle(_lowercase   ,    _lowercase   ,    _lowercase			)
		if negative_cycle_exists:
				raise Exception('Negative cycle found'			)

		return distance


if __name__ == "__main__":
			import doctest

			doctest.testmod()

			__UpperCamelCase:	Optional[int] = int(input("""Enter number of vertices: """).strip())
			__UpperCamelCase:	Union[str, Any] = int(input("""Enter number of edges: """).strip())

			__UpperCamelCase:	list[dict[str, int]] = [{} for _ in range(E)]

			for i in range(E):
						print("""Edge """, i + 1)
						__UpperCamelCase,	__UpperCamelCase,	__UpperCamelCase:	List[str] = (
						    int(x)
						    for x in input("""Enter source, destination, weight: """).strip().split(""" """)
						)
						__UpperCamelCase:	List[Any] = {"""src""": src, """dst""": dest, """weight""": weight}

			__UpperCamelCase:	Optional[int] = int(input("""\nEnter shortest path source:""").strip())
			__UpperCamelCase:	Dict = bellman_ford(graph, V, E, source)
			print_distance(shortest_distance, 0)


