




from __future__ import annotations

import unittest
from collections.abc import Iterator



class     a  :

					'''simple docstring'''





					def __init__(			self     :    Union[str, Any]      ,					__snake_case     :    int      ,					__snake_case     :    Node | None       ):
									UpperCAmelCase_											=  label
									UpperCAmelCase_											=  parent
									UpperCAmelCase_											=  None
									UpperCAmelCase_											=  None



class     a  :

					'''simple docstring'''





					def __init__(			self     :    Dict       ):
									UpperCAmelCase_											=  None
					def 						lowerCamelCase_     (			self     :    str       ):
									UpperCAmelCase_											=  None
					def 						lowerCamelCase_     (			self     :    Optional[int]       ):
									return self.root is None
					def 						lowerCamelCase_     (			self     :    Optional[Any]      ,					__snake_case     :    int       ):
									UpperCAmelCase_											=  self._put(self.root      ,					__snake_case       )
					def 						lowerCamelCase_     (			self     :    Optional[Any]      ,					__snake_case     :    Node | None      ,					__snake_case     :    int      ,					__snake_case     :    Node | None = None       ):







									if node is None:
													UpperCAmelCase_											=  Node(__snake_case      ,					__snake_case       )
									else:
													if label < node.label:
																	UpperCAmelCase_											=  self._put(node.left      ,					__snake_case      ,					__snake_case       )
													elif label > node.label:
																	UpperCAmelCase_											=  self._put(node.right      ,					__snake_case      ,					__snake_case       )
													else:
																	UpperCAmelCase_											=  F'Node with label {label} already exists'
																	raise Exception(__snake_case       )

									return node
					def 						lowerCamelCase_     (			self     :    Tuple      ,					__snake_case     :    int       ):
									return self._search(self.root      ,					__snake_case       )
					def 						lowerCamelCase_     (			self     :    List[str]      ,					__snake_case     :    Node | None      ,					__snake_case     :    int       ):







									if node is None:
													UpperCAmelCase_											=  F'Node with label {label} does not exist'
													raise Exception(__snake_case       )
									else:
													if label < node.label:
																	UpperCAmelCase_											=  self._search(node.left      ,					__snake_case       )
													elif label > node.label:
																	UpperCAmelCase_											=  self._search(node.right      ,					__snake_case       )

									return node
					def 						lowerCamelCase_     (			self     :    Any      ,					__snake_case     :    int       ):
									UpperCAmelCase_											=  self.search(__snake_case       )
									if node.right and node.left:
													UpperCAmelCase_											=  self._get_lowest_node(node.right       )
													UpperCAmelCase_											=  node.left
													UpperCAmelCase_											=  node.right
													UpperCAmelCase_											=  lowest_node
													if node.right:
																	UpperCAmelCase_											=  lowest_node
													self._reassign_nodes(__snake_case      ,					__snake_case       )
									elif not node.right and node.left:
													self._reassign_nodes(__snake_case      ,					node.left       )
									elif node.right and not node.left:
													self._reassign_nodes(__snake_case      ,					node.right       )
									else:
													self._reassign_nodes(__snake_case      ,					__snake_case       )
					def 						lowerCamelCase_     (			self     :    Tuple      ,					__snake_case     :    Node      ,					__snake_case     :    Node | None       ):







									if new_children:
													UpperCAmelCase_											=  node.parent

									if node.parent:
													if node.parent.right == node:
																	UpperCAmelCase_											=  new_children
													else:
																	UpperCAmelCase_											=  new_children
									else:
													UpperCAmelCase_											=  new_children
					def 						lowerCamelCase_     (			self     :    int      ,					__snake_case     :    Node       ):







									if node.left:
													UpperCAmelCase_											=  self._get_lowest_node(node.left       )
									else:
													UpperCAmelCase_											=  node
													self._reassign_nodes(__snake_case      ,					node.right       )

									return lowest_node
					def 						lowerCamelCase_     (			self     :    int      ,					__snake_case     :    int       ):







									try:
													self.search(__snake_case       )
													return True
									except Exception:
													return False
					def 						lowerCamelCase_     (			self     :    Union[str, Any]       ):







									if self.root is None:
													raise Exception('''Binary search tree is empty'''       )

									UpperCAmelCase_											=  self.root
									while node.right is not None:
													UpperCAmelCase_											=  node.right

									return node.label
					def 						lowerCamelCase_     (			self     :    Union[str, Any]       ):







									if self.root is None:
													raise Exception('''Binary search tree is empty'''       )

									UpperCAmelCase_											=  self.root
									while node.left is not None:
													UpperCAmelCase_											=  node.left

									return node.label
					def 						lowerCamelCase_     (			self     :    List[Any]       ):
									return self._inorder_traversal(self.root       )
					def 						lowerCamelCase_     (			self     :    str      ,					__snake_case     :    Node | None       ):







									if node is not None:
													yield from self._inorder_traversal(node.left       )
													yield node
													yield from self._inorder_traversal(node.right       )
					def 						lowerCamelCase_     (			self     :    Optional[Any]       ):
									return self._preorder_traversal(self.root       )




					def 						lowerCamelCase_     (			self     :    Any      ,					__snake_case     :    Node | None       ):







									if node is not None:
													yield node
													yield from self._preorder_traversal(node.left       )
													yield from self._preorder_traversal(node.right       )



class     a  (     unittest.TestCase    ):

					'''simple docstring'''





					@staticmethod
					def 						lowerCamelCase_     (			):
									UpperCAmelCase_											=  BinarySearchTree()
									t.put(8       )
									t.put(3       )
									t.put(6       )
									t.put(1       )
									t.put(10       )
									t.put(14       )
									t.put(13       )
									t.put(4       )
									t.put(7       )
									t.put(5       )

									return t
					def 						lowerCamelCase_     (			self     :    Dict       ):
									UpperCAmelCase_											=  BinarySearchTree()
									assert t.is_empty()

									t.put(8       )
									assert t.root is not None
									assert t.root.parent is None
									assert t.root.label == 8

									t.put(10       )
									assert t.root.right is not None
									assert t.root.right.parent == t.root
									assert t.root.right.label == 10

									t.put(3       )
									assert t.root.left is not None
									assert t.root.left.parent == t.root
									assert t.root.left.label == 3

									t.put(6       )
									assert t.root.left.right is not None
									assert t.root.left.right.parent == t.root.left
									assert t.root.left.right.label == 6

									t.put(1       )
									assert t.root.left.left is not None
									assert t.root.left.left.parent == t.root.left
									assert t.root.left.left.label == 1

									with self.assertRaises(__snake_case       ):  # noqa: B017
													t.put(1       )
					def 						lowerCamelCase_     (			self     :    Tuple       ):
									UpperCAmelCase_											=  self._get_binary_search_tree()

									UpperCAmelCase_											=  t.search(6       )
									assert node.label == 6

									UpperCAmelCase_											=  t.search(13       )
									assert node.label == 13

									with self.assertRaises(__snake_case       ):  # noqa: B017
													t.search(2       )
					def 						lowerCamelCase_     (			self     :    Any       ):
									UpperCAmelCase_											=  self._get_binary_search_tree()

									t.remove(13       )
									assert t.root is not None
									assert t.root.right is not None
									assert t.root.right.right is not None
									assert t.root.right.right.right is None
									assert t.root.right.right.left is None

									t.remove(7       )
									assert t.root.left is not None
									assert t.root.left.right is not None
									assert t.root.left.right.left is not None
									assert t.root.left.right.right is None
									assert t.root.left.right.left.label == 4

									t.remove(6       )
									assert t.root.left.left is not None
									assert t.root.left.right.right is not None
									assert t.root.left.left.label == 1
									assert t.root.left.right.label == 4
									assert t.root.left.right.right.label == 5
									assert t.root.left.right.left is None
									assert t.root.left.left.parent == t.root.left
									assert t.root.left.right.parent == t.root.left

									t.remove(3       )
									assert t.root is not None
									assert t.root.left.label == 4
									assert t.root.left.right.label == 5
									assert t.root.left.left.label == 1
									assert t.root.left.parent == t.root
									assert t.root.left.left.parent == t.root.left
									assert t.root.left.right.parent == t.root.left

									t.remove(4       )
									assert t.root.left is not None
									assert t.root.left.left is not None
									assert t.root.left.label == 5
									assert t.root.left.right is None
									assert t.root.left.left.label == 1
									assert t.root.left.parent == t.root
									assert t.root.left.left.parent == t.root.left
					def 						lowerCamelCase_     (			self     :    int       ):
									UpperCAmelCase_											=  self._get_binary_search_tree()

									t.remove(3       )
									assert t.root is not None
									assert t.root.left is not None
									assert t.root.left.left is not None
									assert t.root.left.right is not None
									assert t.root.left.right.left is not None
									assert t.root.left.right.right is not None
									assert t.root.left.label == 4
									assert t.root.left.right.label == 6
									assert t.root.left.left.label == 1
									assert t.root.left.right.right.label == 7
									assert t.root.left.right.left.label == 5
									assert t.root.left.parent == t.root
									assert t.root.left.right.parent == t.root.left
									assert t.root.left.left.parent == t.root.left
									assert t.root.left.right.left.parent == t.root.left.right
					def 						lowerCamelCase_     (			self     :    int       ):
									UpperCAmelCase_											=  self._get_binary_search_tree()
									t.empty()
									assert t.root is None
					def 						lowerCamelCase_     (			self     :    str       ):
									UpperCAmelCase_											=  self._get_binary_search_tree()
									assert not t.is_empty()

									t.empty()
									assert t.is_empty()
					def 						lowerCamelCase_     (			self     :    Any       ):
									UpperCAmelCase_											=  self._get_binary_search_tree()

									assert t.exists(6       )
									assert not t.exists(-1       )
					def 						lowerCamelCase_     (			self     :    List[str]       ):
									UpperCAmelCase_											=  self._get_binary_search_tree()

									assert t.get_max_label() == 14

									t.empty()
									with self.assertRaises(__snake_case       ):  # noqa: B017
													t.get_max_label()
					def 						lowerCamelCase_     (			self     :    Optional[int]       ):
									UpperCAmelCase_											=  self._get_binary_search_tree()

									assert t.get_min_label() == 1

									t.empty()
									with self.assertRaises(__snake_case       ):  # noqa: B017
													t.get_min_label()
					def 						lowerCamelCase_     (			self     :    Optional[int]       ):
									UpperCAmelCase_											=  self._get_binary_search_tree()

									UpperCAmelCase_											=  [i.label for i in t.inorder_traversal()]
									assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]




					def 						lowerCamelCase_     (			self     :    List[Any]       ):
									UpperCAmelCase_											=  self._get_binary_search_tree()

									UpperCAmelCase_											=  [i.label for i in t.preorder_traversal()]
									assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]




def       SCREAMING_SNAKE_CASE			( )						->							None:
				UpperCAmelCase_											=  BinarySearchTree()
				t.put(8   )
				t.put(3   )
				t.put(6   )
				t.put(1   )
				t.put(10   )
				t.put(14   )
				t.put(13   )
				t.put(4   )
				t.put(7   )
				t.put(5   )

				print(
				    '''
            8
           / \\
          3   10
         / \\    \\
        1   6    14
           / \\   /
          4   7 13
           \\
            5
        '''   )

				print('''Label 6 exists:''' ,  t.exists(6   )   )
				print('''Label 13 exists:''' ,  t.exists(13   )   )
				print('''Label -1 exists:''' ,  t.exists(-1   )   )
				print('''Label 12 exists:''' ,  t.exists(12   )   )

				# Prints all the elements of the list in inorder traversal
				UpperCAmelCase_											=  [i.label for i in t.inorder_traversal()]
				print('''Inorder traversal:''' ,  __UpperCamelCase   )

				# Prints all the elements of the list in preorder traversal
				UpperCAmelCase_											=  [i.label for i in t.preorder_traversal()]
				print('''Preorder traversal:''' ,  __UpperCamelCase   )

				print('''Max. label:''' ,  t.get_max_label()   )
				print('''Min. label:''' ,  t.get_min_label()   )

				# Delete elements
				print('''\nDeleting elements 13, 10, 8, 3, 6, 14'''   )
				print(
				    '''
          4
         / \\
        1   7
             \\
              5
        '''   )
				t.remove(13   )
				t.remove(10   )
				t.remove(8   )
				t.remove(3   )
				t.remove(6   )
				t.remove(14   )

				# Prints all the elements of the list in inorder traversal after delete
				UpperCAmelCase_											=  [i.label for i in t.inorder_traversal()]
				print('''Inorder traversal after delete:''' ,  __UpperCamelCase   )

				# Prints all the elements of the list in preorder traversal after delete
				UpperCAmelCase_											=  [i.label for i in t.preorder_traversal()]
				print('''Preorder traversal after delete:''' ,  __UpperCamelCase   )

				print('''Max. label:''' ,  t.get_max_label()   )
				print('''Min. label:''' ,  t.get_min_label()   )


if __name__ == "__main__":
	binary_search_tree_example()











_lowerCamelCase    				=		[
    [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
    [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
    [0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
]




def       SCREAMING_SNAKE_CASE			( __UpperCamelCase    :		int ,  __UpperCamelCase    :		int ,  __UpperCamelCase    :		int ,  __UpperCamelCase    :		int   )						->							bool:
    return 0 <= row < rows and 0 <= col < cols




def       SCREAMING_SNAKE_CASE			( __UpperCamelCase    :		int ,  __UpperCamelCase    :		int ,  __UpperCamelCase    :		set ,  __UpperCamelCase    :		list[list[int]]   )						->							int:
    UpperCAmelCase_											=  len(__UpperCamelCase   )
    UpperCAmelCase_											=  len(mat[0]   )
    if is_safe(__UpperCamelCase ,  __UpperCamelCase ,  __UpperCamelCase ,  __UpperCamelCase   ) and (row, col) not in seen and mat[row][col] == 1:
        seen.add((row, col)   )
        return (
            1
            + depth_first_search(row + 1 ,  __UpperCamelCase ,  __UpperCamelCase ,  __UpperCamelCase   )
            + depth_first_search(row - 1 ,  __UpperCamelCase ,  __UpperCamelCase ,  __UpperCamelCase   )
            + depth_first_search(__UpperCamelCase ,  col + 1 ,  __UpperCamelCase ,  __UpperCamelCase   )
            + depth_first_search(__UpperCamelCase ,  col - 1 ,  __UpperCamelCase ,  __UpperCamelCase   )
        )
    else:
        return 0




def       SCREAMING_SNAKE_CASE			( __UpperCamelCase    :		list[list[int]]   )						->							int:
    UpperCAmelCase_											=  set()

    UpperCAmelCase_											=  0
    for row, line in enumerate(__UpperCamelCase   ):
        for col, item in enumerate(__UpperCamelCase   ):
            if item == 1 and (row, col) not in seen:
                # Maximizing the area
                UpperCAmelCase_											=  max(__UpperCamelCase ,  depth_first_search(__UpperCamelCase ,  __UpperCamelCase ,  __UpperCamelCase ,  __UpperCamelCase   )   )
    return max_area


if __name__ == "__main__":
 import doctest

 print(find_max_area(matrix))  # Output -> 6
 doctest.testmod()





