





from __future__ import annotations

from collections.abc import Iterator
from typing import Any
class      UpperCamelCase_						:




					def __init__(						self			,  lowerCAmelCase_					)						->							str:
										_snake_case													=			data
										_snake_case													=			None





class      UpperCamelCase_						:




					def __init__(						self					)						->							Tuple:
										_snake_case													=			None
										_snake_case													=			None




					def __iter__(						self					)						->							Iterator[Any]:
										_snake_case													=			self.head
										while self.head:
															yield node.data
															_snake_case													=			node.next
															if node == self.head:
																				break




					def __len__(						self					)						->							int:
										return sum(1 for _ in self					)




					def __repr__(						self					)						->							Optional[int]:
										return "->".join(str(lowerCAmelCase_					) for item in iter(self					)					)




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_					)						->							None:
										self.insert_nth(len(self					)			,  lowerCAmelCase_					)




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_					)						->							None:
										self.insert_nth(0			,  lowerCAmelCase_					)




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_			,  lowerCAmelCase_					)						->							None:
										if index < 0 or index > len(self					):
															raise IndexError('list index out of range.'					)
										_snake_case													=			Node(lowerCAmelCase_					)
										if self.head is None:
															_snake_case													=			new_node  # first node points itself
															_snake_case													=			_snake_case													=			new_node
										elif index == 0:  # insert at head
															_snake_case													=			self.head
															_snake_case													=			_snake_case													=			new_node
										else:
															_snake_case													=			self.head
															for _ in range(index - 1					):
																				_snake_case													=			temp.next
															_snake_case													=			temp.next
															_snake_case													=			new_node
															if index == len(self					) - 1:  # insert at tail
																				_snake_case													=			new_node




					def 		lowerCAmelCase     (						self					)						->							List[Any]:
										return self.delete_nth(0					)




					def 		lowerCAmelCase     (						self					)						->							Any:
										return self.delete_nth(len(self					) - 1					)




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_ = 0					)						->							Any:
										if not 0 <= index < len(self					):
															raise IndexError('list index out of range.'					)
										_snake_case													=			self.head
										if self.head == self.tail:  # just one node
															_snake_case													=			_snake_case													=			None
										elif index == 0:  # delete head node
															_snake_case													=			self.tail.next.next
															_snake_case													=			self.head.next
										else:
															_snake_case													=			self.head
															for _ in range(index - 1					):
																				_snake_case													=			temp.next
															_snake_case													=			temp.next
															_snake_case													=			temp.next.next
															if index == len(self					) - 1:  # delete at tail
																				_snake_case													=			temp
										return delete_node.data






					def 		lowerCAmelCase     (						self					)						->							bool:
										return len(self					) == 0





def   lowerCamelCase__       (       )     ->	None:



					'''simple docstring'''




					_snake_case													=			CircularLinkedList()
					assert len(UpperCamelCase__  ) == 0
					assert circular_linked_list.is_empty() is True
					assert str(UpperCamelCase__  ) == ""

					try:
										circular_linked_list.delete_front()
										raise AssertionError  # This should not happen
					except IndexError:
										assert True  # This should happen

					try:
										circular_linked_list.delete_tail()
										raise AssertionError  # This should not happen
					except IndexError:
										assert True  # This should happen

					try:
										circular_linked_list.delete_nth(-1  )
										raise AssertionError
					except IndexError:
										assert True

					try:
										circular_linked_list.delete_nth(0  )
										raise AssertionError
					except IndexError:
										assert True

					assert circular_linked_list.is_empty() is True
					for i in range(5  ):
										assert len(UpperCamelCase__  ) == i
										circular_linked_list.insert_nth(UpperCamelCase__    ,      i + 1  )
					assert str(UpperCamelCase__  ) == "->".join(str(UpperCamelCase__  ) for i in range(1    ,      6  )  )

					circular_linked_list.insert_tail(6  )
					assert str(UpperCamelCase__  ) == "->".join(str(UpperCamelCase__  ) for i in range(1    ,      7  )  )
					circular_linked_list.insert_head(0  )
					assert str(UpperCamelCase__  ) == "->".join(str(UpperCamelCase__  ) for i in range(0    ,      7  )  )

					assert circular_linked_list.delete_front() == 0
					assert circular_linked_list.delete_tail() == 6
					assert str(UpperCamelCase__  ) == "->".join(str(UpperCamelCase__  ) for i in range(1    ,      6  )  )
					assert circular_linked_list.delete_nth(2  ) == 3

					circular_linked_list.insert_nth(2    ,      3  )
					assert str(UpperCamelCase__  ) == "->".join(str(UpperCamelCase__  ) for i in range(1    ,      6  )  )

					assert circular_linked_list.is_empty() is False


if __name__ == "__main__":
					import doctest

					doctest.testmod()










def   lowerCamelCase__       (       UpperCamelCase__     :    list[list[int]]    ,      UpperCamelCase__     :    int    ,      UpperCamelCase__     :    int    ,      UpperCamelCase__     :    list[int]  )     ->	bool:



					'''simple docstring'''




					if graph[path[curr_ind - 1]][next_ver] == 0:
										return False

					# 2. Validate that next vertex is not already in path
					return not any(vertex == next_ver for vertex in path  )





def   lowerCamelCase__       (       UpperCamelCase__     :    list[list[int]]    ,      UpperCamelCase__     :    list[int]    ,      UpperCamelCase__     :    int  )     ->	bool:



					'''simple docstring'''




					if curr_ind == len(UpperCamelCase__  ):
										# return whether path exists between current and starting vertices
										return graph[path[curr_ind - 1]][path[0]] == 1

					# Recursive Step
					for next_ver in range(0    ,      len(UpperCamelCase__  )  ):
										if valid_connection(UpperCamelCase__    ,      UpperCamelCase__    ,      UpperCamelCase__    ,      UpperCamelCase__  ):
															# Insert current vertex  into path as next transition
															_snake_case													=			next_ver
															# Validate created path
															if util_hamilton_cycle(UpperCamelCase__    ,      UpperCamelCase__    ,      curr_ind + 1  ):
																				return True
															# Backtrack
															_snake_case													=			-1
					return False





def   lowerCamelCase__       (       UpperCamelCase__     :    list[list[int]]    ,      UpperCamelCase__     :    int = 0  )     ->	list[int]:



					'''simple docstring'''




					_snake_case													=			[-1] * (len(UpperCamelCase__  ) + 1)
					# initialize start and end of path with starting index
					_snake_case													=			_snake_case													=			start_index
					# evaluate and if we find answer return path either return empty array
					return path if util_hamilton_cycle(UpperCamelCase__    ,      UpperCamelCase__    ,      1  ) else []



