
from __future__ import annotations

from typing import Generic, TypeVar

_UpperCAmelCase      :				Union[str, Any]          = TypeVar("T")


class        lowercase      (	Generic[T]     ):



		def __init__(				self       ,   A_ )						->      None:
				"""simple docstring"""
				UpperCamelCase						=  data
				UpperCamelCase						=  self
				UpperCamelCase						=  0






class        lowercase      (	Generic[T]     ):



		def __init__(				self )						->      None:
				"""simple docstring"""
				# map from node name to the node object
				UpperCamelCase						=  {}



		def __UpperCamelCase				(				self       ,   A_ )						->      None:
				"""simple docstring"""
				# create a new set with x as its member
				UpperCamelCase						=  DisjointSetTreeNode(A_ )



		def __UpperCamelCase				(				self       ,   A_ )						->      DisjointSetTreeNode[T]:
				"""simple docstring"""
				# find the set x belongs to (with path-compression)
				UpperCamelCase						=  self.map[data]
				if elem_ref != elem_ref.parent:
						UpperCamelCase						=  self.find_set(elem_ref.parent.data )
				return elem_ref.parent



		def __UpperCamelCase				(				self       ,   A_       ,   A_ )						->      None:
				"""simple docstring"""
				# helper function for union operation
				if nodea.rank > nodea.rank:
						UpperCamelCase						=  nodea
				else:
						UpperCamelCase						=  nodea
						if nodea.rank == nodea.rank:
								nodea.rank += 1



		def __UpperCamelCase				(				self       ,   A_       ,   A_ )						->      None:
				"""simple docstring"""
				# merge 2 disjoint sets
				self.link(self.find_set(A_ )       ,   self.find_set(A_ ) )






class        lowercase      (	Generic[T]     ):



		def __init__(				self )						->      None:
				"""simple docstring"""
				# connections: map from the node to the neighbouring nodes (with weights)
				UpperCamelCase						=  {}



		def __UpperCamelCase				(				self       ,   A_ )						->      None:
				"""simple docstring"""
				# add a node ONLY if its not present in the graph
				if node not in self.connections:
						UpperCamelCase						=  {}



		def __UpperCamelCase				(				self       ,   A_       ,   A_       ,   A_ )						->      None:
				"""simple docstring"""
				# add an edge with the given weight
				self.add_node(A_ )
				self.add_node(A_ )
				UpperCamelCase						=  weight
				UpperCamelCase						=  weight



		def __UpperCamelCase				(				self )						->      GraphUndirectedWeighted[T]:
				"""simple docstring"""
				UpperCamelCase						=  []
				UpperCamelCase						=  set()
				for start in self.connections:
						for end in self.connections[start]:
								if (start, end) not in seen:
										seen.add((end, start) )
										edges.append((start, end, self.connections[start][end]) )
				edges.sort(key=lambda A_ : x[2] )

				# creating the disjoint set
				UpperCamelCase						=  DisjointSetTree[T]()
				for node in self.connections:
						disjoint_set.make_set(A_ )

				# MST generation
				UpperCamelCase						=  0
				UpperCamelCase						=  0
				UpperCamelCase						=  GraphUndirectedWeighted[T]()
				while num_edges < len(self.connections ) - 1:
						UpperCamelCase			,						UpperCamelCase			,						UpperCamelCase						=  edges[index]
						index += 1
						UpperCamelCase						=  disjoint_set.find_set(A_ )
						UpperCamelCase						=  disjoint_set.find_set(A_ )
						if parent_u != parent_v:
								num_edges += 1
								graph.add_edge(A_       ,   A_       ,   A_ )
								disjoint_set.union(A_       ,   A_ )
				return graph


def    A (      lowercase					, lowercase				)     ->						str:
		'''simple docstring'''

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

		UpperCamelCase						=  str(bin(lowercase				)				)[2:]  # remove the leading "0b"
		UpperCamelCase						=  str(bin(lowercase				)				)[2:]  # remove the leading "0b"

		UpperCamelCase						=  max(len(lowercase				)					, len(lowercase				)				)

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


if __name__ == "__main__":
					import doctest

					doctest.testmod()
