"""simple docstring"""







def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    Tuple							=							0
	while b > 0:
		if b & 1:
			res += a

		a += a
		b >>= 1

	return res


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    Optional[Any]							=							0
	while b > 0:
		if b & 1:
			_lowercase :    Dict							=							((res % c) + (a % c)) % c

		a += a
		b >>= 1

	return res




"""simple docstring"""







def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





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


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			):






	"""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
			_lowercase :    str							=							i
			# Validate coloring
			if util_color(__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase     ,index + 1			):
				return True
			# Backtrack
			_lowercase :    List[str]							=							-1
	return False







def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    Any							=							[-1] * len(__UpperCAmelCase			)

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

	return []



