


def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		list[int]       ,  SCREAMING_SNAKE_CASE_   :		list[int]       ,  SCREAMING_SNAKE_CASE_   :		int	):





			"""simple docstring"""




			return not any(
			    neighbour == 1 and colored_vertices[i] == color
			    for i, neighbour in enumerate(UpperCAmelCase__	)	)






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		list[list[int]]       ,  SCREAMING_SNAKE_CASE_   :		int       ,  SCREAMING_SNAKE_CASE_   :		list[int]       ,  SCREAMING_SNAKE_CASE_   :		int	):





			"""simple docstring"""




			if index == len(UpperCAmelCase__	):
						return True

			# Recursive Step
			for i in range(UpperCAmelCase__	):
						if valid_coloring(graph[index]       ,  UpperCAmelCase__       ,  UpperCAmelCase__	):
									# Color current vertex
									UpperCamelCase         =					i
									# Validate coloring
									if util_color(UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  index + 1	):
												return True
									# Backtrack
									UpperCamelCase         =					-1
			return False






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		list[list[int]]       ,  SCREAMING_SNAKE_CASE_   :		int	):





			"""simple docstring"""




			UpperCamelCase         =					[-1] * len(UpperCAmelCase__	)

			if util_color(UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  0	):
						return colored_vertices

			return []








def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		int	):





			"""simple docstring"""




			assert (
			    isinstance(SCREAMING_SNAKE_CASE_       ,  SCREAMING_SNAKE_CASE_	) and number_of_steps > 0
			), f'number_of_steps needs to be positive integer, your input {number_of_steps}'
			if number_of_steps == 1:
						return 1
			UpperCamelCase  ,  UpperCamelCase         =					1, 1
			for _ in range(number_of_steps - 1	):
						UpperCamelCase  ,  UpperCamelCase         =					current + previous, current
			return current


if __name__ == "__main__":
			import doctest

			doctest.testmod()




