






"""simple docstring"""
class 		a_      :







      '''simple docstring'''

      def __init__(self,     lowerCamelCase_					):

       '''simple docstring'''



       lowerCamelCase__     :			Any     				=						data
       lowerCamelCase__     :			int
       lowerCamelCase__     :			Node






def        lowerCamelCase_  (						_lowerCamelCase				):
 lowerCamelCase__     :			str     				=						0
 lowerCamelCase__     :			List[Any]     				=						x






def        lowerCamelCase_  (						_lowerCamelCase			,   _lowerCamelCase				):
 lowerCamelCase__				,     lowerCamelCase__     :			str     				=						find_set(_lowerCamelCase				), find_set(_lowerCamelCase				)
 if x == y:
  return

 elif x.rank > y.rank:
  lowerCamelCase__     :			Union[str, Any]     				=						x
 else:
  lowerCamelCase__     :			Tuple     				=						y
  if x.rank == y.rank:
   y.rank += 1






def        lowerCamelCase_  (						_lowerCamelCase				):
 if x != x.parent:
  lowerCamelCase__     :			int     				=						find_set(x.parent				)
 return x.parent






def        lowerCamelCase_  (						_lowerCamelCase				):
 lowerCamelCase__     :			Union[str, Any]     				=						({0, 1, 2}, {3, 4, 5})
 for s in sets:
  if node.data in s:
   return s
 lowerCamelCase__     :			Dict     				=						f'''{node.data} is not in {sets}'''
 raise ValueError(_lowerCamelCase				)






def        lowerCamelCase_  (						):
 lowerCamelCase__     :			List[Any]     				=						[Node(_lowerCamelCase				) for i in range(6				)]
 for v in vertex:
  make_set(_lowerCamelCase				)

 union_set(vertex[0]			,   vertex[1]				)
 union_set(vertex[1]			,   vertex[2]				)
 union_set(vertex[3]			,   vertex[4]				)
 union_set(vertex[3]			,   vertex[5]				)

 for nodea in vertex:
  for nodea in vertex:
   if find_python_set(_lowerCamelCase				).isdisjoint(find_python_set(_lowerCamelCase				)				):
    assert find_set(_lowerCamelCase				) != find_set(_lowerCamelCase				)
   else:
    assert find_set(_lowerCamelCase				) == find_set(_lowerCamelCase				)


if __name__ == "__main__":
      test_disjoint_set()









"""simple docstring"""
class 		a_      :







      '''simple docstring'''

      class 		a_      :







            '''simple docstring'''

            lowerCamelCase__       :				List[Any] =	'_prev', '_data', '_next'




            def __init__(self,     lowerCamelCase_,     lowerCamelCase_,     lowerCamelCase_					):

             '''simple docstring'''



             lowerCamelCase__     :			Optional[int]     				=						link_p
             lowerCamelCase__     :			Optional[Any]     				=						element
             lowerCamelCase__     :			List[Any]     				=						link_n





            def 			a__							(self					):

             '''simple docstring'''



             return (
                 f''' Prev -> {self._prev is not None}, Next -> {self._next is not None}'''
             )




      def __init__(self					):

       '''simple docstring'''



       lowerCamelCase__     :			Any     				=						self._Node(lowerCamelCase_,     lowerCamelCase_,     lowerCamelCase_					)
       lowerCamelCase__     :			Dict     				=						self._Node(lowerCamelCase_,     lowerCamelCase_,     lowerCamelCase_					)
       lowerCamelCase__     :			List[str]     				=						self._trailer
       lowerCamelCase__     :			Union[str, Any]     				=						self._header
       lowerCamelCase__     :			Any     				=						0




      def __len__(self					):

       '''simple docstring'''



       return self._size




      def 			a__							(self					):

       '''simple docstring'''



       return self.__len__() == 0




      def 			a__							(self,     lowerCamelCase_,     lowerCamelCase_,     lowerCamelCase_					):

       '''simple docstring'''



       lowerCamelCase__     :			int     				=						self._Node(lowerCamelCase_,     lowerCamelCase_,     lowerCamelCase_					)
       lowerCamelCase__     :			Optional[int]     				=						new_node
       lowerCamelCase__     :			List[Any]     				=						new_node
       self._size += 1
       return self





      def 			a__							(self,     lowerCamelCase_					):

       '''simple docstring'''



       lowerCamelCase__     :			Optional[Any]     				=						node._prev
       lowerCamelCase__     :			List[str]     				=						node._next

       lowerCamelCase__     :			Tuple     				=						successor
       lowerCamelCase__     :			Tuple     				=						predecessor
       self._size -= 1
       lowerCamelCase__     :			int     				=						node._data
       lowerCamelCase__     :			Dict     				=						None
       del node
       return temp



class 		a_      (	_DoublyLinkedBase ):







      '''simple docstring'''

      def 			a__							(self					):

       '''simple docstring'''



       if self.is_empty():
        raise Exception('List is empty'					)
       return self._header._next._data




      def 			a__							(self					):

       '''simple docstring'''



       if self.is_empty():
        raise Exception('List is empty'					)
       return self._trailer._prev._data




      def 			a__							(self,     lowerCamelCase_					):

       '''simple docstring'''



       return self._insert(self._header,     lowerCamelCase_,     self._header._next					)




      def 			a__							(self,     lowerCamelCase_					):

       '''simple docstring'''



       return self._insert(self._trailer._prev,     lowerCamelCase_,     self._trailer					)




      def 			a__							(self					):

       '''simple docstring'''



       if self.is_empty():
        raise IndexError('remove_first from empty list'					)
       return self._delete(self._header._next					)





      def 			a__							(self					):

       '''simple docstring'''



       if self.is_empty():
        raise IndexError('remove_first from empty list'					)
       return self._delete(self._trailer._prev					)

