



"""simple docstring"""







def       _lowerCamelCase				(							UpperCAmelCase_ :       list[int],	UpperCAmelCase_ :       list[int],	UpperCAmelCase_ :       int     )	-> bool:






	"""simple docstring"""





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

def       _lowerCamelCase				(							UpperCAmelCase_ :       list[list[int]],	UpperCAmelCase_ :       int,	UpperCAmelCase_ :       list[int],	UpperCAmelCase_ :       int     )	-> bool:






	"""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
			A__											=					i
			# Validate coloring
			if util_color(UpperCAmelCase_,	UpperCAmelCase_,	UpperCAmelCase_,	index + 1     ):
				return True
			# Backtrack
			A__											=					-1
	return False




def       _lowerCamelCase				(							UpperCAmelCase_ :       list[list[int]],	UpperCAmelCase_ :       int     )	-> list[int]:






	"""simple docstring"""





	A__											=					[-1] * len(UpperCAmelCase_     )

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

	return []








class     A__   :







    """simple docstring"""

    def __init__(			self     ,   __snake_case       ):
         snake_case											=							n
         snake_case											=							[None] * self.n
         snake_case											=							0  # index of the first element
         snake_case											=							0
         snake_case											=							0
    def __len__(			self       ):
         return self.size
    def 						a_     (			self       ):
         return self.size == 0
    def 						a_     (			self       ):
         return False if self.is_empty() else self.array[self.front]
    def 						a_     (			self     ,   __snake_case       ):
         if self.size >= self.n:
              raise Exception('''QUEUE IS FULL'''       )

         snake_case											=							data
         snake_case											=							(self.rear + 1) % self.n
         self.size += 1
         return self




    def 						a_     (			self       ):
         if self.size == 0:
              raise Exception('''UNDERFLOW'''       )

         snake_case											=							self.array[self.front]
         snake_case											=							None
         snake_case											=							(self.front + 1) % self.n
         self.size -= 1
         return temp




