

"""simple docstring"""

_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 			SCREAMING_SNAKE_CASE       (   lowercase__				,				lowercase__				,				lowercase__				,				lowercase__      ) ->	bool:
 return 0 <= row < rows and 0 <= col < cols



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



def 			SCREAMING_SNAKE_CASE       (   lowercase__      ) ->	int:
 lowerCAmelCase__      :							set    =							set()

 lowerCAmelCase__      :							List[str]    =							0
 for row, line in enumerate(lowercase__      ):
  for col, item in enumerate(lowercase__      ):
   if item == 1 and (row, col) not in seen:
    # Maximizing the area
    lowerCAmelCase__      :							str    =							max(lowercase__				,				depth_first_search(lowercase__				,				lowercase__				,				lowercase__				,				lowercase__      )      )
 return max_area


if __name__ == "__main__":
    import doctest

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









"""simple docstring"""

# A Bipartite Graph is a graph whose vertices can be divided into two independent sets,
# U and V such that every edge (u, v) either connects a vertex from U to V or a vertex
# from V to U. In other words, for every edge (u, v), either u belongs to U and v to V,
# or u belongs to V and v to U. We can also say that there is no edge that connects
# vertices of same set.
from queue import Queue



def 			SCREAMING_SNAKE_CASE       (   lowercase__      ) ->	List[str]:
 lowerCAmelCase__      :							Tuple    =							Queue()
 lowerCAmelCase__      :							Optional[int]    =							[False] * len(lowercase__      )
 lowerCAmelCase__      :							Dict    =							[-1] * len(lowercase__      )

 def bfs():
  while not queue.empty():
   lowerCAmelCase__      :							Optional[Any]    =							queue.get()
   lowerCAmelCase__      :							Union[str, Any]    =							True

   for neighbour in graph[u]:
    if neighbour == u:
     return False

    if color[neighbour] == -1:
     lowerCAmelCase__      :							Any    =							1 - color[u]
     queue.put(lowercase__      )

    elif color[neighbour] == color[u]:
     return False

  return True

 for i in range(len(lowercase__      )      ):
  if not visited[i]:
   queue.put(lowercase__      )
   lowerCAmelCase__      :							int    =							0
   if bfs() is False:
    return False

 return True


if __name__ == "__main__":
    # Adjacency List of graph
    print(check_bipartite({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}))






