


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

class     UpperCAmelCase__ :



     '''simple docstring'''




     def __init__(			self							:							List[Any]						,   UpperCamelCase							:							Optional[Any]		):





            """simple docstring"""



            _lowercase       :					Tuple     							=      str(id_		)
            _lowercase       :					Any     							=      None
            _lowercase       :					Optional[int]     							=      None
            _lowercase       :					Optional[int]     							=      []
            _lowercase       :					List[str]     							=      {}  # {vertex:distance}




     def __lt__(			self							:							Union[str, Any]						,   UpperCamelCase							:							Any		):





            """simple docstring"""



            return self.key < other.key




     def __repr__(			self							:							Tuple		):





            """simple docstring"""



            return self.id




     def 	lowerCAmelCase_ (			self							:							str						,   UpperCamelCase							:							Optional[int]		):





            """simple docstring"""



            self.neighbors.append(__snake_case		)




     def 	lowerCAmelCase_ (			self							:							List[str]						,   UpperCamelCase							:							Tuple						,   UpperCamelCase							:							str		):





            """simple docstring"""



            _lowercase       :					List[Any]     							=      weight




def 	UpperCamelCase__ (     UpperCAmelCase_     ,  UpperCAmelCase_     ,  UpperCAmelCase_     ,  UpperCAmelCase_      )    ->				Optional[Any]:




       '''simple docstring'''






       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]     ,  _UpperCAmelCase      )
       graph[b - 1].add_edge(graph[a - 1]     ,  _UpperCAmelCase      )

def 	UpperCamelCase__ (     UpperCAmelCase_     ,  UpperCAmelCase_      )    ->				list:




       '''simple docstring'''






       _lowercase       :					Union[str, Any]     							=      []
       for u in graph:
              _lowercase       :					Union[str, Any]     							=      math.inf
              _lowercase       :					Any     							=      None
       _lowercase       :					Dict     							=      0
       _lowercase       :					Any     							=      graph[:]
       while q:
              _lowercase       :					Tuple     							=      min(_UpperCAmelCase      )
              q.remove(_UpperCAmelCase      )
              for v in u.neighbors:
                     if (v in q) and (u.edges[v.id] < v.key):
                            _lowercase       :					int     							=      u
                            _lowercase       :					List[Any]     							=      u.edges[v.id]
       for i in range(1     ,  len(_UpperCAmelCase      )      ):
              a.append((int(graph[i].id      ) + 1, int(graph[i].pi.id      ) + 1)      )
       return a

def 	UpperCamelCase__ (     UpperCAmelCase_     ,  UpperCAmelCase_      )    ->				Iterator[tuple]:




       '''simple docstring'''






       for u in graph:
              _lowercase       :					Dict     							=      math.inf
              _lowercase       :					str     							=      None
       _lowercase       :					Tuple     							=      0

       _lowercase       :					Optional[Any]     							=      list(_UpperCAmelCase      )
       hq.heapify(_UpperCAmelCase      )

       while h:
              _lowercase       :					Dict     							=      hq.heappop(_UpperCAmelCase      )
              for v in u.neighbors:
                     if (v in h) and (u.edges[v.id] < v.key):
                            _lowercase       :					List[str]     							=      u
                            _lowercase       :					int     							=      u.edges[v.id]
                            hq.heapify(_UpperCAmelCase      )

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

def 	UpperCamelCase__ (     )    ->				None:




       '''simple docstring'''










if __name__ == "__main__":
   import doctest

   doctest.testmod()






def      UpperCAmelCase_    (    _UpperCAmelCase							:Any  ,						_UpperCAmelCase							:Dict				)	->				Union[str, Any]:
     '''simple docstring'''


     A_          =       [1]
     for i in range(2  ,						_UpperCAmelCase				):
          factorials.append(factorials[-1] * i				)
     assert 0 <= k < factorials[-1] * n, "k out of bounds"

     A_          =       []
     A_          =       list(range(_UpperCAmelCase				)				)

     # Find permutation
     while factorials:
          A_          =       factorials.pop()
          A_   ,    A_          =       divmod(_UpperCAmelCase  ,						_UpperCAmelCase				)
          permutation.append(elements[number]				)
          elements.remove(elements[number]				)
     permutation.append(elements[0]				)

     return permutation


if __name__ == "__main__":
      import doctest

      doctest.testmod()



