


from __future__ import annotations

from collections import deque
from collections.abc import Iterator
from dataclasses import dataclass






@dataclass
class     UpperCAmelCase__       :



    """simple docstring"""






    UpperCAmelCase__						:		Optional[int]      =  4_2
    UpperCAmelCase__						:		List[Any]      =  4_2






class     UpperCAmelCase__       :



    """simple docstring"""






    def __init__(			self					,   A_    )  ->       Optional[Any]:
         __UpperCamelCase    							=[[] for _ in range(A_    )]
         __UpperCamelCase    							=size






    def __getitem__(			self					,   A_    )  ->       Any:
         return iter(self._graph[vertex]    )






    @property
    def _a					(			self    )  ->       Optional[Any]:
         return self._size






    def _a					(			self					,   A_					,   A_					,   A_    )  ->       str:
         if weight not in (0, 1):
              raise ValueError('Edge weight must be either 0 or 1.'    )

         if to_vertex < 0 or to_vertex >= self.size:
              raise ValueError('Vertex indexes must be in [0; size).'    )

         self._graph[from_vertex].append(Edge(A_					,   A_    )    )






    def _a					(			self					,   A_					,   A_    )  ->       Union[str, Any]:
         __UpperCamelCase    							=deque([start_vertex]    )
         __UpperCamelCase    							=[None] * self.size
         __UpperCamelCase    							=0

         while queue:
              __UpperCamelCase    							=queue.popleft()
              __UpperCamelCase    							=distances[current_vertex]
              if current_distance is None:
                   continue

              for edge in self[current_vertex]:
                   __UpperCamelCase    							=current_distance + edge.weight
                   __UpperCamelCase    							=distances[edge.destination_vertex]
                   if (
                       isinstance(A_					,   A_    )
                       and new_distance >= dest_vertex_distance
                   ):
                        continue
                   __UpperCamelCase    							=new_distance
                   if edge.weight == 0:
                        queue.appendleft(edge.destination_vertex    )
                   else:
                        queue.append(edge.destination_vertex    )

         if distances[finish_vertex] is None:
              raise ValueError('No path from start_vertex to finish_vertex.'    )

         return distances[finish_vertex]


if __name__ == "__main__":
   import doctest

   doctest.testmod()











"""simple docstring"""






from __future__ import annotations

from collections.abc import Iterator
from typing import Any






class lowerCAmelCase__	:






			'''simple docstring'''



			def __init__(  self  ,      lowercase  ):
							_lowerCamelCase     :			Any    =    data
							_lowerCamelCase     :			Node | None    =    None






class lowerCAmelCase__	:






			'''simple docstring'''



			def __init__(  self  ):
							_lowerCamelCase     :			str    =    None
							_lowerCamelCase     :			str    =    None
			def __iter__(  self  ):
							_lowerCamelCase     :			List[str]    =    self.head
							while self.head:
											yield node.data
											_lowerCamelCase     :			Optional[int]    =    node.next
											if node == self.head:
															break
			def __len__(  self  ):
							return sum(1 for _ in self  )
			def __repr__(  self  ):
							return "->".join(str(lowercase  ) for item in iter(self  )  )
			def 					A_    (  self  ,      lowercase  ):
							self.insert_nth(len(self  )  ,      lowercase  )
			def 					A_    (  self  ,      lowercase  ):
							self.insert_nth(0  ,      lowercase  )
			def 					A_    (  self  ,      lowercase  ,      lowercase  ):
							if index < 0 or index > len(self  ):
											raise IndexError('list index out of range.'  )
							_lowerCamelCase     :			List[Any]    =    Node(lowercase  )
							if self.head is None:
											_lowerCamelCase     :			str    =    new_node  # first node points itself
											_lowerCamelCase     :			Union[str, Any]    =    new_node
							elif index == 0:  # insert at head
											_lowerCamelCase     :			List[str]    =    self.head
											_lowerCamelCase     :			str    =    new_node
							else:
											_lowerCamelCase     :			Union[str, Any]    =    self.head
											for _ in range(index - 1  ):
															_lowerCamelCase     :			List[Any]    =    temp.next
											_lowerCamelCase     :			Union[str, Any]    =    temp.next
											_lowerCamelCase     :			List[str]    =    new_node
											if index == len(self  ) - 1:  # insert at tail
															_lowerCamelCase     :			Any    =    new_node
			def 					A_    (  self  ):
							return self.delete_nth(0  )
			def 					A_    (  self  ):
							return self.delete_nth(len(self  ) - 1  )
			def 					A_    (  self  ,      lowercase = 0  ):
							if not 0 <= index < len(self  ):
											raise IndexError('list index out of range.'  )
							_lowerCamelCase     :			Any    =    self.head
							if self.head == self.tail:  # just one node
											_lowerCamelCase     :			List[str]    =    None
							elif index == 0:  # delete head node
											_lowerCamelCase     :			List[str]    =    self.tail.next.next
											_lowerCamelCase     :			Optional[int]    =    self.head.next
							else:
											_lowerCamelCase     :			Dict    =    self.head
											for _ in range(index - 1  ):
															_lowerCamelCase     :			List[Any]    =    temp.next
											_lowerCamelCase     :			int    =    temp.next
											_lowerCamelCase     :			Optional[int]    =    temp.next.next
											if index == len(self  ) - 1:  # delete at tail
															_lowerCamelCase     :			List[Any]    =    temp
							return delete_node.data






			def 					A_    (  self  ):
							return len(self  ) == 0







def      _snake_case			(				):
				_lowerCamelCase     :			Union[str, Any]    =    CircularLinkedList()
				assert len(lowercase__		) == 0
				assert circular_linked_list.is_empty() is True
				assert str(lowercase__		) == ""

				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(lowercase__		) == i
								circular_linked_list.insert_nth(lowercase__							,    i + 1		)
				assert str(lowercase__		) == "->".join(str(lowercase__		) for i in range(1							,    6		)		)

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

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

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

				assert circular_linked_list.is_empty() is False


if __name__ == "__main__":
			import doctest

			doctest.testmod()