from __future__ import annotations


class 	lowerCamelCase_     :






    '''simple docstring'''






    def __init__(	self , __lowercase)       ->	None:
        __UpperCamelCase     :str			  =		data
        __UpperCamelCase     :Any			  =		None
        __UpperCamelCase     :Optional[int]			  =		None



def lowerCamelCase  (   SCREAMING_SNAKE_CASE	):  # In Order traversal of the tree
    '''simple docstring'''







    if tree:
        display(tree.left	)
        print(tree.data	)
        display(tree.right	)



def lowerCamelCase  (   SCREAMING_SNAKE_CASE	):
    '''simple docstring'''







    return 1 + max(depth_of_tree(tree.left	)  ,			depth_of_tree(tree.right	)	) if tree else 0



def lowerCamelCase  (   SCREAMING_SNAKE_CASE	):
    '''simple docstring'''







    if not tree:
        return True
    if tree.left and tree.right:
        return is_full_binary_tree(tree.left	) and is_full_binary_tree(tree.right	)
    else:
        return not tree.left and not tree.right



def lowerCamelCase  (   ):  # Main function for testing.
    '''simple docstring'''







    __UpperCamelCase     :List[Any]			  =		Node(1	)
    __UpperCamelCase     :List[Any]			  =		Node(2	)
    __UpperCamelCase     :List[str]			  =		Node(3	)
    __UpperCamelCase     :int			  =		Node(4	)
    __UpperCamelCase     :Optional[Any]			  =		Node(5	)
    __UpperCamelCase     :int			  =		Node(6	)
    __UpperCamelCase     :int			  =		Node(7	)
    __UpperCamelCase     :Any			  =		Node(8	)
    __UpperCamelCase     :str			  =		Node(9	)

    print(is_full_binary_tree(SCREAMING_SNAKE_CASE__	)	)
    print(depth_of_tree(SCREAMING_SNAKE_CASE__	)	)
    print('''Tree is: '''	)
    display(SCREAMING_SNAKE_CASE__	)


if __name__ == "__main__":
    main()









_A		       =						{0: [2, 3], 1: [0], 2: [1], 3: [4], 4: []}

_A		       =						{0: [1, 2, 3], 1: [2], 2: [0], 3: [4], 4: [5], 5: [3]}

def 						_UpperCAmelCase				(			SCREAMING_SNAKE_CASE__			:					dict[int, list[int]]			,     SCREAMING_SNAKE_CASE__			:					int			,     SCREAMING_SNAKE_CASE__			:					list[bool]				):
     __UpperCamelCase    							=True
     __UpperCamelCase    							=[]

     for neighbour in graph[vert]:
          if not visited[neighbour]:
               order += topology_sort(SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__				)

     order.append(SCREAMING_SNAKE_CASE__				)

     return order

def 						_UpperCAmelCase				(			SCREAMING_SNAKE_CASE__			:					dict[int, list[int]]			,     SCREAMING_SNAKE_CASE__			:					int			,     SCREAMING_SNAKE_CASE__			:					list[bool]				):
     __UpperCamelCase    							=True
     __UpperCamelCase    							=[vert]

     for neighbour in reversed_graph[vert]:
          if not visited[neighbour]:
               component += find_components(SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__				)

     return component





def 						_UpperCAmelCase				(			SCREAMING_SNAKE_CASE__			:					dict[int, list[int]]				):
     __UpperCamelCase    							=len(SCREAMING_SNAKE_CASE__				) * [False]
     __UpperCamelCase    							={vert: [] for vert in range(len(SCREAMING_SNAKE_CASE__				)				)}

     for vert, neighbours in graph.items():
          for neighbour in neighbours:
               reversed_graph[neighbour].append(SCREAMING_SNAKE_CASE__				)

     __UpperCamelCase    							=[]
     for i, was_visited in enumerate(SCREAMING_SNAKE_CASE__				):
          if not was_visited:
               order += topology_sort(SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__				)

     __UpperCamelCase    							=[]
     __UpperCamelCase    							=len(SCREAMING_SNAKE_CASE__				) * [False]

     for i in range(len(SCREAMING_SNAKE_CASE__				)				):
          __UpperCamelCase    							=order[len(SCREAMING_SNAKE_CASE__				) - i - 1]
          if not visited[vert]:
               __UpperCamelCase    							=find_components(SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__				)
               components_list.append(SCREAMING_SNAKE_CASE__				)

     return components_list





