



"""simple docstring"""





from __future__ import annotations

import math
import random
from typing import Any



class    _lowerCAmelCase    :





		"""simple docstring"""






		def __init__(					self   ) ->						None:







								'''simple docstring'''

								snake_case_   : list[Any]						=			[]
								snake_case_   : int						=			0
								snake_case_   : int						=			0





		def    UpperCAmelCase__							(					self   ) ->						bool:







								'''simple docstring'''

								return self.head == self.tail





		def    UpperCAmelCase__							(					self							,    _lowercase   ) ->						None:







								'''simple docstring'''

								self.data.append(_lowercase   )
								snake_case_   : Union[str, Any]						=			self.tail + 1





		def    UpperCAmelCase__							(					self   ) ->						Any:







								'''simple docstring'''

								snake_case_   : List[str]						=			self.data[self.head]
								snake_case_   : Any						=			self.head + 1
								return ret





		def    UpperCAmelCase__							(					self   ) ->						int:







								'''simple docstring'''

								return self.tail - self.head





		def    UpperCAmelCase__							(					self   ) ->						None:







								'''simple docstring'''

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




class    _lowerCAmelCase    :





		"""simple docstring"""






		def __init__(					self							,    _lowercase   ) ->						None:







								'''simple docstring'''

								snake_case_   : Optional[int]						=			data
								snake_case_   : MyNode | None						=			None
								snake_case_   : MyNode | None						=			None
								snake_case_   : int						=			1





		def    UpperCAmelCase__							(					self   ) ->						Any:







								'''simple docstring'''

								return self.data





		def    UpperCAmelCase__							(					self   ) ->						MyNode | None:







								'''simple docstring'''

								return self.left





		def    UpperCAmelCase__							(					self   ) ->						MyNode | None:







								'''simple docstring'''

								return self.right





		def    UpperCAmelCase__							(					self   ) ->						int:







								'''simple docstring'''

								return self.height





		def    UpperCAmelCase__							(					self							,    _lowercase   ) ->						None:







								'''simple docstring'''

								snake_case_   : List[str]						=			data





		def    UpperCAmelCase__							(					self							,    _lowercase   ) ->						None:







								'''simple docstring'''

								snake_case_   : int						=			node





		def    UpperCAmelCase__							(					self							,    _lowercase   ) ->						None:







								'''simple docstring'''

								snake_case_   : int						=			node





		def    UpperCAmelCase__							(					self							,    _lowercase   ) ->						None:







								'''simple docstring'''

								snake_case_   : Union[str, Any]						=			height




def 	__lowerCAmelCase						(		__UpperCamelCase      :			MyNode | None    ):


						'''simple docstring'''






						if node is None:
												return 0
						return node.get_height()
def 	__lowerCAmelCase						(		__UpperCamelCase      :			int					, __UpperCamelCase      :			int    ):


						'''simple docstring'''






						if a > b:
												return a
						return b
def 	__lowerCAmelCase						(		__UpperCamelCase      :			MyNode    ):


						'''simple docstring'''






						print("""left rotation node:"""					, node.get_data()    )
						snake_case_   : List[str]						=			node.get_left()
						assert ret is not None
						node.set_left(ret.get_right()    )
						ret.set_right(__UpperCamelCase    )
						snake_case_   : List[str]						=			my_max(get_height(node.get_right()    )					, get_height(node.get_left()    )    ) + 1
						node.set_height(__UpperCamelCase    )
						snake_case_   : Tuple						=			my_max(get_height(ret.get_right()    )					, get_height(ret.get_left()    )    ) + 1
						ret.set_height(__UpperCamelCase    )
						return ret
def 	__lowerCAmelCase						(		__UpperCamelCase      :			MyNode    ):


						'''simple docstring'''






						print("""right rotation node:"""					, node.get_data()    )
						snake_case_   : Tuple						=			node.get_right()
						assert ret is not None
						node.set_right(ret.get_left()    )
						ret.set_left(__UpperCamelCase    )
						snake_case_   : List[Any]						=			my_max(get_height(node.get_right()    )					, get_height(node.get_left()    )    ) + 1
						node.set_height(__UpperCamelCase    )
						snake_case_   : List[Any]						=			my_max(get_height(ret.get_right()    )					, get_height(ret.get_left()    )    ) + 1
						ret.set_height(__UpperCamelCase    )
						return ret
def 	__lowerCAmelCase						(		__UpperCamelCase      :			MyNode    ):


						'''simple docstring'''






						snake_case_   : List[str]						=			node.get_left()
						assert left_child is not None
						node.set_left(left_rotation(__UpperCamelCase    )    )
						return right_rotation(__UpperCamelCase    )
def 	__lowerCAmelCase						(		__UpperCamelCase      :			MyNode    ):


						'''simple docstring'''






						snake_case_   : Optional[int]						=			node.get_right()
						assert right_child is not None
						node.set_right(right_rotation(__UpperCamelCase    )    )
						return left_rotation(__UpperCamelCase    )
def 	__lowerCAmelCase						(		__UpperCamelCase      :			MyNode | None					, __UpperCamelCase      :			Any    ):


						'''simple docstring'''






						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
																		snake_case_   : int						=			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
																								snake_case_   : Optional[Any]						=			right_rotation(__UpperCamelCase    )
																		else:
																								snake_case_   : List[str]						=			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:
																		snake_case_   : Optional[Any]						=			node.get_right()
																		assert right_child is not None
																		if data < right_child.get_data():
																								snake_case_   : Optional[Any]						=			rl_rotation(__UpperCamelCase    )
																		else:
																								snake_case_   : int						=			left_rotation(__UpperCamelCase    )
						snake_case_   : Optional[Any]						=			my_max(get_height(node.get_right()    )					, get_height(node.get_left()    )    ) + 1
						node.set_height(__UpperCamelCase    )
						return node
def 	__lowerCAmelCase						(		__UpperCamelCase      :			MyNode    ):


						'''simple docstring'''






						while True:
												snake_case_   : Union[str, Any]						=			root.get_right()
												if right_child is None:
																		break
												snake_case_   : List[Any]						=			right_child
						return root.get_data()
def 	__lowerCAmelCase						(		__UpperCamelCase      :			MyNode    ):


						'''simple docstring'''






						while True:
												snake_case_   : List[str]						=			root.get_left()
												if left_child is None:
																		break
												snake_case_   : str						=			left_child
						return root.get_data()
def 	__lowerCAmelCase						(		__UpperCamelCase      :			MyNode					, __UpperCamelCase      :			Any    ):


						'''simple docstring'''






						snake_case_   : List[str]						=			root.get_left()
						snake_case_   : List[Any]						=			root.get_right()
						if root.get_data() == data:
												if left_child is not None and right_child is not None:
																		snake_case_   : Tuple						=			get_left_most(__UpperCamelCase    )
																		root.set_data(__UpperCamelCase    )
																		root.set_right(del_node(__UpperCamelCase					, __UpperCamelCase    )    )
												elif left_child is not None:
																		snake_case_   : str						=			left_child
												elif right_child is not None:
																		snake_case_   : Optional[Any]						=			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()    ):
																		snake_case_   : List[Any]						=			left_rotation(__UpperCamelCase    )
												else:
																		snake_case_   : Optional[int]						=			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()    ):
																		snake_case_   : Union[str, Any]						=			right_rotation(__UpperCamelCase    )
												else:
																		snake_case_   : Union[str, Any]						=			lr_rotation(__UpperCamelCase    )
						snake_case_   : List[str]						=			my_max(get_height(root.get_right()    )					, get_height(root.get_left()    )    ) + 1
						root.set_height(__UpperCamelCase    )
						return root



class    _lowerCAmelCase    :





		"""simple docstring"""






		def __init__(					self   ) ->						None:







								'''simple docstring'''

								snake_case_   : MyNode | None						=			None





		def    UpperCAmelCase__							(					self   ) ->						int:







								'''simple docstring'''

								return get_height(self.root   )





		def    UpperCAmelCase__							(					self							,    _lowercase   ) ->						None:







								'''simple docstring'''

								print("""insert:""" + str(_lowercase   )   )
								snake_case_   : List[str]						=			insert_node(self.root							,    _lowercase   )





		def    UpperCAmelCase__							(					self							,    _lowercase   ) ->						None:







								'''simple docstring'''

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





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







								'''simple docstring'''

								snake_case_   : Dict						=			""""""
								snake_case_   : List[Any]						=			MyQueue()
								q.push(self.root   )
								snake_case_   : Optional[Any]						=			self.get_height()
								if layer == 0:
														return output
								snake_case_   : Union[str, Any]						=			0
								while not q.is_empty():
														snake_case_   : str						=			q.pop()
														snake_case_   : Dict						=			""" """ * int(math.pow(2							,    layer - 1   )   )
														output += space
														if node is None:
																				output += "*"
																				q.push(_lowercase   )
																				q.push(_lowercase   )
														else:
																				output += str(node.get_data()   )
																				q.push(node.get_left()   )
																				q.push(node.get_right()   )
														output += space
														snake_case_   : Tuple						=			cnt + 1
														for i in range(1_0_0   ):
																				if cnt == math.pow(2							,    _lowercase   ) - 1:
																										snake_case_   : List[Any]						=			layer - 1
																										if layer == 0:
																																output += "\n*************************************"
																																return output
																										output += "\n"
																										break
								output += "\n*************************************"
								return output




def 	__lowerCAmelCase						(		):


						'''simple docstring'''






						import doctest

						doctest.testmod()


if __name__ == "__main__":
					_test()
					__lowerCAmelCase       :					Dict      					=					AVLtree()
					__lowerCAmelCase       :					List[str]      					=					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))






"""simple docstring"""





def 	__lowerCAmelCase						(		__UpperCamelCase      :			Union[str, Any]    ):


						'''simple docstring'''






						snake_case_   : int						=			[0] * len(__UpperCamelCase    )
						snake_case_   : List[str]						=			[]
						snake_case_   : Any						=			[1] * len(__UpperCamelCase    )

						for values in graph.values():
												for i in values:
																		indegree[i] += 1

						for i in range(len(__UpperCamelCase    )    ):
												if indegree[i] == 0:
																		queue.append(__UpperCamelCase    )

						while queue:
												snake_case_   : Optional[int]						=			queue.pop(0    )
												for x in graph[vertex]:
																		indegree[x] -= 1

																		if long_dist[vertex] + 1 > long_dist[x]:
																								snake_case_   : Union[str, Any]						=			long_dist[vertex] + 1

																		if indegree[x] == 0:
																								queue.append(__UpperCamelCase    )

						print(max(__UpperCamelCase    )    )


# Adjacency list of Graph
__lowerCAmelCase       :					str      					=					{0: [2, 3, 4], 1: [2, 7], 2: [5], 3: [5, 7], 4: [7], 5: [6], 6: [7], 7: []}






longest_distance(graph)

