
"""simple docstring"""

from __future__ import annotations

from collections.abc import Iterator
from typing import Any

class __lowerCAmelCase		:





     def __init__(     self     ,					__UpperCAmelCase				):

      '''simple docstring'''




      __UpperCamelCase      =	data
      __UpperCamelCase      =	None


class __lowerCAmelCase		:





     def __init__(     self				):

      '''simple docstring'''




      __UpperCamelCase      =	None
      __UpperCamelCase      =	None





     def __iter__(     self				):

      '''simple docstring'''




      __UpperCamelCase      =	self.head
      while self.head:
       yield node.data
       __UpperCamelCase      =	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(__UpperCAmelCase				) for item in iter(self				)				)





     def 						UpperCAmelCase (     self     ,					__UpperCAmelCase				):

      '''simple docstring'''




      self.insert_nth(len(self				)     ,					__UpperCAmelCase				)





     def 						UpperCAmelCase (     self     ,					__UpperCAmelCase				):

      '''simple docstring'''




      self.insert_nth(0     ,					__UpperCAmelCase				)





     def 						UpperCAmelCase (     self     ,					__UpperCAmelCase     ,					__UpperCAmelCase				):

      '''simple docstring'''




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





     def 						UpperCAmelCase (     self				):

      '''simple docstring'''




      return self.delete_nth(0				)





     def 						UpperCAmelCase (     self				):

      '''simple docstring'''




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





     def 						UpperCAmelCase (     self     ,					__UpperCAmelCase = 0				):

      '''simple docstring'''




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







     def 						UpperCAmelCase (     self				):

      '''simple docstring'''




      return len(self				) == 0






def 							A						(    )				->     None:
 __UpperCamelCase      =	CircularLinkedList()
 assert len(snake_case		) == 0
 assert circular_linked_list.is_empty() is True
 assert str(snake_case		) == ""

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

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

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

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

 assert circular_linked_list.is_empty() is False


if __name__ == "__main__":
      import doctest

      doctest.testmod()





"""simple docstring"""

import heapq as hq
import math
from collections.abc import Iterator

class __lowerCAmelCase		:





     def __init__(     self     ,					__UpperCAmelCase				):

      '''simple docstring'''




      __UpperCamelCase      =	str(id_				)
      __UpperCamelCase      =	None
      __UpperCamelCase      =	None
      __UpperCamelCase      =	[]
      __UpperCamelCase      =	{}  # {vertex:distance}





     def __lt__(     self     ,					__UpperCAmelCase				):

      '''simple docstring'''




      return self.key < other.key





     def __repr__(     self				):

      '''simple docstring'''




      return self.id





     def 						UpperCAmelCase (     self     ,					__UpperCAmelCase				):

      '''simple docstring'''




      self.neighbors.append(__UpperCAmelCase				)







     def 						UpperCAmelCase (     self     ,					__UpperCAmelCase     ,					__UpperCAmelCase				):

      '''simple docstring'''




      __UpperCamelCase      =	weight






def 							A						(    snake_case				:List[Any]    , snake_case				:Dict    , snake_case				:Any    , snake_case				:str		)				->     List[str]:
 # add the neighbors:
 graph[a - 1].add_neighbor(graph[b - 1]		)
 graph[b - 1].add_neighbor(graph[a - 1]		)
 # add the edges:
 graph[a - 1].add_edge(graph[b - 1]    , snake_case		)
 graph[b - 1].add_edge(graph[a - 1]    , snake_case		)






def 							A						(    snake_case				:list    , snake_case				:Vertex		)				->     list:
 __UpperCamelCase      =	[]
 for u in graph:
  __UpperCamelCase      =	math.inf
  __UpperCamelCase      =	None
 __UpperCamelCase      =	0
 __UpperCamelCase      =	graph[:]
 while q:
  __UpperCamelCase      =	min(snake_case		)
  q.remove(snake_case		)
  for v in u.neighbors:
   if (v in q) and (u.edges[v.id] < v.key):
    __UpperCamelCase      =	u
    __UpperCamelCase      =	u.edges[v.id]
 for i in range(1    , len(snake_case		)		):
  a.append((int(graph[i].id		) + 1, int(graph[i].pi.id		) + 1)		)
 return a






def 							A						(    snake_case				:list    , snake_case				:Vertex		)				->     Iterator[tuple]:
 for u in graph:
  __UpperCamelCase      =	math.inf
  __UpperCamelCase      =	None
 __UpperCamelCase      =	0

 __UpperCamelCase      =	list(snake_case		)
 hq.heapify(snake_case		)

 while h:
  __UpperCamelCase      =	hq.heappop(snake_case		)
  for v in u.neighbors:
   if (v in h) and (u.edges[v.id] < v.key):
    __UpperCamelCase      =	u
    __UpperCamelCase      =	u.edges[v.id]
    hq.heapify(snake_case		)

 for i in range(1    , len(snake_case		)		):
  yield (int(graph[i].id		) + 1, int(graph[i].pi.id		) + 1)






def 							A						(    )				->     None:
 pass


if __name__ == "__main__":
      import doctest

      doctest.testmod()



