



from __future__ import annotations

from queue import Queue



class 		_lowercase		:

   def __init__(   self      :							Any				)							->					None:


    """simple docstring"""






    a							=		{}

   def 		A				(   self      :							Dict				)							->					None:


    """simple docstring"""






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

   def 		A				(   self      :							Dict				, __lowerCAmelCase      :							int				, __lowerCAmelCase      :							int				)							->					None:


    """simple docstring"""






    if from_vertex in self.vertices:
     self.vertices[from_vertex].append(__lowerCAmelCase				)
    else:
     a							=		[to_vertex]




   def 		A				(   self      :							List[Any]				, __lowerCAmelCase      :							int				)							->					set[int]:


    """simple docstring"""






    a							=		set()

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

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

    while not queue.empty():
     a							=		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(__lowerCAmelCase				)
       visited.add(__lowerCAmelCase				)
    return visited


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

     testmod(verbose=True)

     A_		:  Tuple										=  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]









UpperCamelCase											=      [
    [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       _a   (							lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__				)  ->      bool:
 return 0 <= row < rows and 0 <= col < cols




def       _a   (							lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__				)  ->      int:
 lowerCamelCase_							:    Tuple							=     len(lowerCamelCase__				)
 lowerCamelCase_							:    Tuple							=     len(mat[0]				)
 if is_safe(lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__				) and (row, col) not in seen and mat[row][col] == 1:
  seen.add((row, col)				)
  return (
      1
      + depth_first_search(row + 1 ,			lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__				)
      + depth_first_search(row - 1 ,			lowerCamelCase__ ,			lowerCamelCase__ ,			lowerCamelCase__				)
      + depth_first_search(lowerCamelCase__ ,			col + 1 ,			lowerCamelCase__ ,			lowerCamelCase__				)
      + depth_first_search(lowerCamelCase__ ,			col - 1 ,			lowerCamelCase__ ,			lowerCamelCase__				)
  )
 else:
  return 0




def       _a   (							lowerCamelCase__				)  ->      int:
 lowerCamelCase_							:    set							=     set()

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


if __name__ == "__main__":
       import doctest

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