




from typing import Any





class        lowerCamelCase_							:


 '''simple docstring'''







 def __init__(							self  :		List[Any]				,				_lowerCAmelCase  :		Any						):
       SCREAMING_SNAKE_CASE_							=			data
       SCREAMING_SNAKE_CASE_							=			None




 def __repr__(							self  :		Optional[Any]						):
       return F"Node({self.data})"





class        lowerCamelCase_							:


 '''simple docstring'''







 def __init__(							self  :		List[Any]						):
       SCREAMING_SNAKE_CASE_							=			None



 def __iter__(							self  :		str						):
       SCREAMING_SNAKE_CASE_							=			self.head
       while node:
             yield node.data
             SCREAMING_SNAKE_CASE_							=			node.next



 def __len__(							self  :		List[str]						):
       return sum(1 for _ in self						)



 def __repr__(							self  :		Tuple						):
       return "->".join([str(_lowerCAmelCase						) for item in self]						)



 def __getitem__(							self  :		Union[str, Any]				,				_lowerCAmelCase  :		int						):
       if not 0 <= index < len(self						):
             raise ValueError('list index out of range.'						)
       for i, node in enumerate(self						):
             if i == index:
                   return node
       return None



 def __setitem__(							self  :		Optional[int]				,				_lowerCAmelCase  :		int				,				_lowerCAmelCase  :		Any						):
       if not 0 <= index < len(self						):
             raise ValueError('list index out of range.'						)
       SCREAMING_SNAKE_CASE_							=			self.head
       for _ in range(_lowerCAmelCase						):
             SCREAMING_SNAKE_CASE_							=			current.next
       SCREAMING_SNAKE_CASE_							=			data



 def       lowerCAmelCase_  (							self  :		List[str]				,				_lowerCAmelCase  :		Any						):
       self.insert_nth(len(self						)				,				_lowerCAmelCase						)



 def       lowerCAmelCase_  (							self  :		str				,				_lowerCAmelCase  :		Any						):
       self.insert_nth(0				,				_lowerCAmelCase						)



 def       lowerCAmelCase_  (							self  :		Union[str, Any]				,				_lowerCAmelCase  :		int				,				_lowerCAmelCase  :		Any						):
       if not 0 <= index <= len(self						):
             raise IndexError('list index out of range'						)
       SCREAMING_SNAKE_CASE_							=			Node(_lowerCAmelCase						)
       if self.head is None:
             SCREAMING_SNAKE_CASE_							=			new_node
       elif index == 0:
             SCREAMING_SNAKE_CASE_							=			self.head  # link new_node to head
             SCREAMING_SNAKE_CASE_							=			new_node
       else:
             SCREAMING_SNAKE_CASE_							=			self.head
             for _ in range(index - 1						):
                   SCREAMING_SNAKE_CASE_							=			temp.next
             SCREAMING_SNAKE_CASE_							=			temp.next
             SCREAMING_SNAKE_CASE_							=			new_node



 def       lowerCAmelCase_  (							self  :		Union[str, Any]						):  # print every node data
       print(self						)



 def       lowerCAmelCase_  (							self  :		Dict						):
       return self.delete_nth(0						)



 def       lowerCAmelCase_  (							self  :		Union[str, Any]						):  # delete from tail
       return self.delete_nth(len(self						) - 1						)



 def       lowerCAmelCase_  (							self  :		Any				,				_lowerCAmelCase  :		int = 0						):
       if not 0 <= index <= len(self						) - 1:  # test if index is valid
             raise IndexError('List index out of range.'						)
       SCREAMING_SNAKE_CASE_							=			self.head  # default first node
       if index == 0:
             SCREAMING_SNAKE_CASE_							=			self.head.next
       else:
             SCREAMING_SNAKE_CASE_							=			self.head
             for _ in range(index - 1						):
                   SCREAMING_SNAKE_CASE_							=			temp.next
             SCREAMING_SNAKE_CASE_							=			temp.next
             SCREAMING_SNAKE_CASE_							=			temp.next.next
       return delete_node.data



 def       lowerCAmelCase_  (							self  :		List[str]						):
       return self.head is None




 def       lowerCAmelCase_  (							self  :		int						):
       SCREAMING_SNAKE_CASE_							=			None
       SCREAMING_SNAKE_CASE_							=			self.head

       while current:
             # Store the current node's next node.
             SCREAMING_SNAKE_CASE_							=			current.next
             # Make the current node's next point backwards
             SCREAMING_SNAKE_CASE_							=			prev
             # Make the previous node be the current node
             SCREAMING_SNAKE_CASE_							=			current
             # Make the current node the next node (to progress iteration)
             SCREAMING_SNAKE_CASE_							=			next_node
       # Return prev in order to put the head at the end
       SCREAMING_SNAKE_CASE_							=			prev


def 					UpperCAmelCase_							(      )					-> None:
      SCREAMING_SNAKE_CASE_							=			LinkedList()
      assert linked_list.is_empty() is True
      assert str(__UpperCAmelCase							) == ""

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

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

      for i in range(10							):
            assert len(__UpperCAmelCase							) == i
            linked_list.insert_nth(__UpperCAmelCase			,			i + 1							)
      assert str(__UpperCAmelCase							) == "->".join(str(__UpperCAmelCase							) for i in range(1			,			11							)							)

      linked_list.insert_head(0							)
      linked_list.insert_tail(11							)
      assert str(__UpperCAmelCase							) == "->".join(str(__UpperCAmelCase							) for i in range(0			,			12							)							)

      assert linked_list.delete_head() == 0
      assert linked_list.delete_nth(9							) == 10
      assert linked_list.delete_tail() == 11
      assert len(__UpperCAmelCase							) == 9
      assert str(__UpperCAmelCase							) == "->".join(str(__UpperCAmelCase							) for i in range(1			,			10							)							)

      assert all(linked_list[i] == i + 1 for i in range(0			,			9							)							) is True

      for i in range(0			,			9							):
            SCREAMING_SNAKE_CASE_							=			-i
      assert all(linked_list[i] == -i for i in range(0			,			9							)							) is True

      linked_list.reverse()
      assert str(__UpperCAmelCase							) == "->".join(str(__UpperCAmelCase							) for i in range(-8			,			1							)							)

def 					UpperCAmelCase_							(      )					-> None:
      SCREAMING_SNAKE_CASE_							=			[
          -9,
          1_00,
          Node(77_34_51_12							),
          'dlrow olleH',
          7,
          55_55,
          0,
          -1_9_2.5_5_5_5_5,
          'Hello, world!',
          7_7.9,
          Node(10							),
          None,
          None,
          1_2.2_0,
      ]
      SCREAMING_SNAKE_CASE_							=			LinkedList()

      for i in test_input:
            linked_list.insert_tail(__UpperCAmelCase							)

      # Check if it's empty or not
      assert linked_list.is_empty() is False
      assert (
          str(__UpperCAmelCase							) == "-9->100->Node(77345112)->dlrow olleH->7->5555->0->"
          "-192.55555->Hello, world!->77.9->Node(10)->None->None->12.2"
      )

      # Delete the head
      SCREAMING_SNAKE_CASE_							=			linked_list.delete_head()
      assert result == -9
      assert (
          str(__UpperCAmelCase							) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
          "Hello, world!->77.9->Node(10)->None->None->12.2"
      )

      # Delete the tail
      SCREAMING_SNAKE_CASE_							=			linked_list.delete_tail()
      assert result == 1_2.2
      assert (
          str(__UpperCAmelCase							) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
          "Hello, world!->77.9->Node(10)->None->None"
      )

      # Delete a node in specific location in linked list
      SCREAMING_SNAKE_CASE_							=			linked_list.delete_nth(10							)
      assert result is None
      assert (
          str(__UpperCAmelCase							) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
          "Hello, world!->77.9->Node(10)->None"
      )

      # Add a Node instance to its head
      linked_list.insert_head(Node('Hello again, world!'							)							)
      assert (
          str(__UpperCAmelCase							)
          == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
          "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None"
      )

      # Add None to its tail
      linked_list.insert_tail(__UpperCAmelCase							)
      assert (
          str(__UpperCAmelCase							)
          == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
          "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None->None"
      )

      # Reverse the linked list
      linked_list.reverse()
      assert (
          str(__UpperCAmelCase							)
          == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
          "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
      )

def 					UpperCAmelCase_							(      )					-> Optional[Any]:
      from doctest import testmod

      testmod()

      SCREAMING_SNAKE_CASE_							=			LinkedList()
      linked_list.insert_head(input('Inserting 1st at head '							).strip()							)
      linked_list.insert_head(input('Inserting 2nd at head '							).strip()							)
      print('\nPrint list:'							)
      linked_list.print_list()
      linked_list.insert_tail(input('\nInserting 1st at tail '							).strip()							)
      linked_list.insert_tail(input('Inserting 2nd at tail '							).strip()							)
      print('\nPrint list:'							)
      linked_list.print_list()
      print('\nDelete head'							)
      linked_list.delete_head()
      print('Delete tail'							)
      linked_list.delete_tail()
      print('\nPrint list:'							)
      linked_list.print_list()
      print('\nReverse linked list'							)
      linked_list.reverse()
      print('\nPrint list:'							)
      linked_list.print_list()
      print('\nString representation of linked list:'							)
      print(__UpperCAmelCase							)
      print('\nReading/changing Node data using indexing:'							)
      print(f"Element at Position 1: {linked_list[1]}"							)
      SCREAMING_SNAKE_CASE_							=			input('Enter New Value: '							).strip()
      print('New list:'							)
      print(__UpperCAmelCase							)
      print(f"length of linked_list is : {len(__UpperCAmelCase							)}"							)


if __name__ == "__main__":
   main()





class        lowerCamelCase_							:


 '''simple docstring'''







 def __init__(							self  :		List[Any]						):
       SCREAMING_SNAKE_CASE_							=			{}



 def       lowerCAmelCase_  (							self  :		List[str]						):
       print(self.vertex						)
       for i in self.vertex:
             print(_lowerCAmelCase				,				' -> '				,				' -> '.join([str(_lowerCAmelCase						) for j in self.vertex[i]]						)						)



 def       lowerCAmelCase_  (							self  :		List[Any]				,				_lowerCAmelCase  :		int				,				_lowerCAmelCase  :		int						):
       # check if vertex is already present,
       if from_vertex in self.vertex:
             self.vertex[from_vertex].append(_lowerCAmelCase						)
       else:
             # else make a new vertex
             SCREAMING_SNAKE_CASE_							=			[to_vertex]



 def       lowerCAmelCase_  (							self  :		Dict						):
       # visited array for storing already visited nodes
       SCREAMING_SNAKE_CASE_							=			[False] * len(self.vertex						)

       # call the recursive helper function
       for i in range(len(self.vertex						)						):
             if not visited[i]:
                   self.dfs_recursive(_lowerCAmelCase				,				_lowerCAmelCase						)




 def       lowerCAmelCase_  (							self  :		Union[str, Any]				,				_lowerCAmelCase  :		int				,				_lowerCAmelCase  :		list						):
       # mark start vertex as visited
       SCREAMING_SNAKE_CASE_							=			True

       print(_lowerCAmelCase				,				end=' '						)

       # Recur for all the vertices that are adjacent to this node
       for i in self.vertex:
             if not visited[i]:
                   self.dfs_recursive(_lowerCAmelCase				,				_lowerCAmelCase						)


if __name__ == "__main__":
   lowerCamelCase__ :   List[Any]					=							Graph()
   g.add_edge(0, 1)
   g.add_edge(0, 2)
   g.add_edge(1, 2)
   g.add_edge(2, 0)
   g.add_edge(2, 3)
   g.add_edge(3, 3)

   g.print_graph()
   print('DFS:')
   g.dfs()

   # OUTPUT:
   # 0  ->  1 -> 2
   # 1  ->  2
   # 2  ->  0 -> 3
   # 3  ->  3
   # DFS:
   #  0 1 2 3