


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







class     _lowercase				:


							"""simple docstring"""




							def __init__(     self							:    List[str]      ,   __lowerCamelCase							:    List[Any] ):


													'''simple docstring'''



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





							def __lt__(     self							:    List[Any]      ,   __lowerCamelCase							:    Dict ):


													'''simple docstring'''



													return self.key < other.key





							def __repr__(     self							:    Optional[Any] ):


													'''simple docstring'''



													return self.id





							def 		lowerCAmelCase  (     self							:    Optional[int]      ,   __lowerCamelCase							:    Any ):


													'''simple docstring'''



													self.neighbors.append(__lowerCamelCase )





							def 		lowerCAmelCase  (     self							:    Tuple      ,   __lowerCamelCase							:    Any      ,   __lowerCamelCase							:    int ):


													'''simple docstring'''



													lowerCamelCase__	:       List[Any]					=						weight



def    lowercase_	(	_A    :					str					,      _A    :					int					,      _A    :					Optional[int]					,      _A    :					List[str]		):

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

def    lowercase_	(	_A    :					list					,      _A    :					Vertex		):

						"""simple docstring"""




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

def    lowercase_	(	_A    :					list					,      _A    :					Vertex		):

						"""simple docstring"""




						for u in graph:
												lowerCamelCase__	:       Any					=						math.inf
												lowerCamelCase__	:       str					=						None
						lowerCamelCase__	:       Tuple					=						0

						lowerCamelCase__	:       Tuple					=						list(_A		)
						hq.heapify(_A		)

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

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

def    lowercase_	(	):

						"""simple docstring"""










if __name__ == "__main__":
				import doctest

				doctest.testmod()






def    lowercase_	(	_A    :					int					,      _A    :					int		):

      """simple docstring"""




      if a < 0 or b < 0:
            raise ValueError("the value of both inputs must be positive"		)

      lowerCamelCase__	:       List[str]					=						str(bin(_A		)		)[2:]  # remove the leading "0b"
      lowerCamelCase__	:       List[Any]					=						str(bin(_A		)		)[2:]  # remove the leading "0b"

      lowerCamelCase__	:       List[Any]					=						max(len(_A		)					,      len(_A		)		)

      return "0b" + "".join(
          str(int(char_a != char_b		)		)
          for char_a, char_b in zip(a_binary.zfill(_A		)					,      b_binary.zfill(_A		)		)		)


if __name__ == "__main__":
    import doctest

    doctest.testmod()


