




import functools
from math import sqrt
from time import time







def       _a (		SCREAMING_SNAKE_CASE_				:							List[Any] , *SCREAMING_SNAKE_CASE_				:							List[Any] , **SCREAMING_SNAKE_CASE_				:							int	):
					__lowerCAmelCase							  =			time()
					__lowerCAmelCase							  =			func(*lowerCamelCase__ , **lowerCamelCase__	)
					__lowerCAmelCase							  =			time()
					if int(end - start	) > 0:
										print(F"""{func.__name__} runtime: {(end - start):0.4f} s"""	)
					else:
										print(F"""{func.__name__} runtime: {(end - start) * 10_00:0.4f} ms"""	)
					return output







def       _a (		SCREAMING_SNAKE_CASE_				:							Union[str, Any]	):
					if n < 0:
										raise Exception("n is negative"	)
					if n == 0:
										return [0]
					__lowerCAmelCase							  =			[0, 1]
					for _ in range(n - 1	):
										fib.append(fib[-1] + fib[-2]	)
					return fib







def       _a (		SCREAMING_SNAKE_CASE_				:							Any	):

					def fib_recursive_term(SCREAMING_SNAKE_CASE_				:							Tuple	) -> int:
										if i < 0:
															raise Exception("n is negative"	)
										if i < 2:
															return i
										return fib_recursive_term(i - 1	) + fib_recursive_term(i - 2	)

					if n < 0:
										raise Exception("n is negative"	)
					return [fib_recursive_term(lowerCamelCase__	) for i in range(n + 1	)]







def       _a (		SCREAMING_SNAKE_CASE_				:							Tuple	):

					@functools.cache
					def fib_recursive_term(SCREAMING_SNAKE_CASE_				:							Union[str, Any]	) -> int:
										if i < 0:
															raise Exception("n is negative"	)
										if i < 2:
															return i
										return fib_recursive_term(i - 1	) + fib_recursive_term(i - 2	)

					if n < 0:
										raise Exception("n is negative"	)
					return [fib_recursive_term(lowerCamelCase__	) for i in range(n + 1	)]







def       _a (		SCREAMING_SNAKE_CASE_				:							Tuple	):
					if n < 0:
										raise Exception("n is negative"	)
					# Cache must be outside recursuive function
					# other it will reset every time it calls itself.
					__lowerCAmelCase							  =			{0: 0, 1: 1, 2: 1}  # Prefilled cache

					def rec_fn_memoized(SCREAMING_SNAKE_CASE_				:							Optional[Any]	) -> int:
										if num in cache:
															return cache[num]

										__lowerCAmelCase							  =			rec_fn_memoized(num - 1	) + rec_fn_memoized(num - 2	)
										__lowerCAmelCase							  =			value
										return value

					return [rec_fn_memoized(lowerCamelCase__	) for i in range(n + 1	)]







def       _a (		SCREAMING_SNAKE_CASE_				:							Optional[int]	):
					if n < 0:
										raise Exception("n is negative"	)
					if n >= 14_75:
										raise Exception("n is too large"	)
					__lowerCAmelCase							  =			sqrt(5	)
					__lowerCAmelCase							  =			(1 + sqrt_a) / 2
					return [round(phi**i / sqrt_a	) for i in range(n + 1	)]


if __name__ == "__main__":
					UpperCamelCase__            =     30
					time_func(fib_iterative, num)
					time_func(fib_recursive, num)  # Around 3s runtime
					time_func(fib_recursive_cached, num)  # Around 0ms runtime
					time_func(fib_memoization, num)
					time_func(fib_binet, num)












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()
