






from __future__ import annotations

from collections.abc import Iterator
from typing import Any





class    lowerCamelCase__  :
     """simple docstring"""



     def __init__(self				,			__a    ):






           '''simple docstring'''



           lowerCamelCase								=		data
           lowerCamelCase								=		None





class    lowerCamelCase__  :
     """simple docstring"""



     def __init__(self    ):






           '''simple docstring'''



           lowerCamelCase								=		None
           lowerCamelCase								=		None







     def __iter__(self    ):






           '''simple docstring'''



           lowerCamelCase								=		self.head
           while self.head:
                 yield node.data
                 lowerCamelCase								=		node.next
                 if node == self.head:
                       break







     def __len__(self    ):






           '''simple docstring'''



           return sum(1 for _ in self    )







     def __repr__(self    ):






           '''simple docstring'''



           return "->".join(str(__a    ) for item in iter(self    )    )







     def 						_a      (self				,			__a    ):






           '''simple docstring'''



           self.insert_nth(len(self    )				,			__a    )







     def 						_a      (self				,			__a    ):






           '''simple docstring'''



           self.insert_nth(0				,			__a    )







     def 						_a      (self				,			__a				,			__a    ):






           '''simple docstring'''



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







     def 						_a      (self    ):






           '''simple docstring'''



           return self.delete_nth(0    )







     def 						_a      (self    ):






           '''simple docstring'''



           return self.delete_nth(len(self    ) - 1    )







     def 						_a      (self				,			__a = 0    ):






           '''simple docstring'''



           if not 0 <= index < len(self    ):
                 raise IndexError("list index out of range."    )
           lowerCamelCase								=		self.head
           if self.head == self.tail:  # just one node
                 lowerCamelCase								=		lowerCamelCase								=		None
           elif index == 0:  # delete head node
                 lowerCamelCase								=		self.tail.next.next
                 lowerCamelCase								=		self.head.next
           else:
                 lowerCamelCase								=		self.head
                 for _ in range(index - 1    ):
                       lowerCamelCase								=		temp.next
                 lowerCamelCase								=		temp.next
                 lowerCamelCase								=		temp.next.next
                 if index == len(self    ) - 1:  # delete at tail
                       lowerCamelCase								=		temp
           return delete_node.data







     def 						_a      (self    ):






           '''simple docstring'''



           return len(self    ) == 0



def     __lowercase(	):


      """simple docstring"""



      lowerCamelCase								=		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()




from __future__ import annotations

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





@dataclass
class    lowerCamelCase__  :
     """simple docstring"""



     _A       =			42
     _A       =			42





class    lowerCamelCase__  :
     """simple docstring"""



     def __init__(self				,			__a    ):






           '''simple docstring'''



           lowerCamelCase								=		[[] for _ in range(__a    )]
           lowerCamelCase								=		size







     def __getitem__(self				,			__a    ):






           '''simple docstring'''



           return iter(self._graph[vertex]    )







     @property
     def 						_a      (self    ):






           '''simple docstring'''



           return self._size







     def 						_a      (self				,			__a				,			__a				,			__a    ):






           '''simple docstring'''



           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    ):






           '''simple docstring'''



           lowerCamelCase								=		deque([start_vertex]    )
           lowerCamelCase								=		[None] * self.size
           lowerCamelCase								=		0

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

                 for edge in self[current_vertex]:
                       lowerCamelCase								=		current_distance + edge.weight
                       lowerCamelCase								=		distances[edge.destination_vertex]
                       if (
                           isinstance(__a				,			__a    )
                           and new_distance >= dest_vertex_distance
                       ):
                             continue
                       lowerCamelCase								=		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()