





import dataclasses
import re
from dataclasses import dataclass
from functools import total_ordering
from typing import Optional, Union


_UpperCAmelCase       : Optional[Any]			     =       re.compile(R"""^(?P<major>\d+)""" R"""\.(?P<minor>\d+)""" R"""\.(?P<patch>\d+)$""")

@total_ordering
@dataclass
class      lowerCAmelCase							:
 UpperCAmelCase__									=	42
 UpperCAmelCase__									=	None
 UpperCAmelCase__									=	None
 UpperCAmelCase__									=	None
 UpperCAmelCase__									=	None
 def   A_			(   self						:   Dict			)    ->			Tuple:
     lowerCamelCase__				,							lowerCamelCase__				,							lowerCamelCase__					:   Optional[Any]      				=	_str_to_version_tuple(self.version_str			)
 def __repr__(   self						:   Any			)    ->			Optional[int]:
     return F"""{self.tuple[0]}.{self.tuple[1]}.{self.tuple[2]}"""
 @property
 def   A_			(   self						:   Optional[int]			)    ->			Optional[Any]:
     return self.major, self.minor, self.patch
 def   A_			(   self						:   List[str]    ,  UpperCAmelCase						:   int			)    ->			int:
     if isinstance(_a    ,  _a			):
         return Version(_a			)
     elif isinstance(_a    ,  _a			):
         return other
     raise TypeError(F"""{other} (type {type(_a			)}) cannot be compared to version."""			)
 def __eq__(   self						:   int    ,  UpperCAmelCase						:   List[Any]			)    ->			Dict:
     try:
         lowerCamelCase__					:   List[Any]      				=	self._validate_operand(_a			)
     except (TypeError, ValueError):
         return False
     else:
         return self.tuple == other.tuple
 def __lt__(   self						:   Optional[int]    ,  UpperCAmelCase						:   Dict			)    ->			int:
     lowerCamelCase__					:   Dict      				=	self._validate_operand(_a			)
     return self.tuple < other.tuple
 def __hash__(   self						:   str			)    ->			int:
     return hash(_version_tuple_to_str(self.tuple			)			)
 @classmethod
 def   A_			(   cls						:   Union[str, Any]    ,  UpperCAmelCase						:   List[Any]			)    ->			Optional[Any]:
     lowerCamelCase__					:   Dict      				=	{f.name for f in dataclasses.fields(cls			)}
     return cls(**{k: v for k, v in dic.items() if k in field_names}			)







 def   A_			(   self						:   Union[str, Any]			)    ->			List[Any]:
     return self.version_str



def  SCREAMING_SNAKE_CASE   ( _UpperCAmelCase				)    ->  Any:
    lowerCamelCase__					:   Dict      				=	_VERSION_REG.match(lowerCAmelCase__				)
    if not res:
        raise ValueError(F"""Invalid version \'{version_str}\'. Format should be x.y.z with {{x,y,z}} being digits."""				)
    return tuple(int(lowerCAmelCase__				) for v in [res.group('major'				), res.group('minor'				), res.group('patch'				)]				)


def  SCREAMING_SNAKE_CASE   ( _UpperCAmelCase				)    ->  List[str]:
    return ".".join(str(lowerCAmelCase__				) for v in version_tuple				)












class      lowerCAmelCase							:
 def __init__(   self						:   Union[str, Any]    ,  UpperCAmelCase						:   list			)    ->			None:
     lowerCamelCase__					:   int      				=	set_counts
     lowerCamelCase__					:   List[str]      				=	max(UpperCAmelCase			)
     lowerCamelCase__					:   Dict      				=	len(UpperCAmelCase			)
     lowerCamelCase__					:   List[str]      				=	[1] * num_sets
     lowerCamelCase__					:   List[str]      				=	list(range(UpperCAmelCase			)			)
 def   A_			(   self						:   Dict    ,  UpperCAmelCase						:   int    ,  UpperCAmelCase						:   int			)    ->			bool:
     lowerCamelCase__					:   List[str]      				=	self.get_parent(UpperCAmelCase			)
     lowerCamelCase__					:   List[str]      				=	self.get_parent(UpperCAmelCase			)

     if src_parent == dst_parent:
         return False

     if self.ranks[dst_parent] >= self.ranks[src_parent]:
         self.set_counts[dst_parent] += self.set_counts[src_parent]
         lowerCamelCase__					:   Union[str, Any]      				=	0
         lowerCamelCase__					:   str      				=	dst_parent
         if self.ranks[dst_parent] == self.ranks[src_parent]:
             self.ranks[dst_parent] += 1
         lowerCamelCase__					:   int      				=	self.set_counts[dst_parent]
     else:
         self.set_counts[src_parent] += self.set_counts[dst_parent]
         lowerCamelCase__					:   List[str]      				=	0
         lowerCamelCase__					:   Tuple      				=	src_parent
         lowerCamelCase__					:   List[str]      				=	self.set_counts[src_parent]

     lowerCamelCase__					:   Optional[int]      				=	max(self.max_set    ,  UpperCAmelCase			)
     return True







 def   A_			(   self						:   str    ,  UpperCAmelCase						:   int			)    ->			int:
     if self.parents[disj_set] == disj_set:
         return disj_set
     lowerCamelCase__					:   Dict      				=	self.get_parent(self.parents[disj_set]			)
     return self.parents[disj_set]





