

"""simple docstring"""




class  lowerCamelCase    :

			def __init__(       self					:    Tuple							) ->     Any:
						SCREAMING_SNAKE_CASE__										=   0
						SCREAMING_SNAKE_CASE__										=   0
						SCREAMING_SNAKE_CASE__										=   {}

			def        SCREAMING_SNAKE_CASE					(       self					:    Union[str, Any]     ,					__UpperCAmelCase					:    str							) ->     int:
						if vertex not in self.adjacency:
									SCREAMING_SNAKE_CASE__										=   {}
									self.num_vertices += 1

			def        SCREAMING_SNAKE_CASE					(       self					:    Union[str, Any]     ,					__UpperCAmelCase					:    Any     ,					__UpperCAmelCase					:    int     ,					__UpperCAmelCase					:    List[str]							) ->     Dict:
						self.add_vertex(__UpperCAmelCase							)
						self.add_vertex(__UpperCAmelCase							)

						if head == tail:
									return

						SCREAMING_SNAKE_CASE__										=   weight
						SCREAMING_SNAKE_CASE__										=   weight

			def        SCREAMING_SNAKE_CASE					(       self					:    List[str]							) ->     Optional[int]:
						SCREAMING_SNAKE_CASE__										=   self.get_edges()
						for edge in edges:
									SCREAMING_SNAKE_CASE__				,		SCREAMING_SNAKE_CASE__				,		SCREAMING_SNAKE_CASE__										=   edge
									edges.remove((tail, head, weight)							)
						for i in range(len(__UpperCAmelCase							)							):
									SCREAMING_SNAKE_CASE__										=   list(edges[i]							)

						edges.sort(key=lambda __UpperCAmelCase							: e[2]							)
						for i in range(len(__UpperCAmelCase							) - 1							):
									if edges[i][2] >= edges[i + 1][2]:
												SCREAMING_SNAKE_CASE__										=   edges[i][2] + 1
						for edge in edges:
									SCREAMING_SNAKE_CASE__				,		SCREAMING_SNAKE_CASE__				,		SCREAMING_SNAKE_CASE__										=   edge
									SCREAMING_SNAKE_CASE__										=   weight
									SCREAMING_SNAKE_CASE__										=   weight

			def __str__(       self					:    Optional[Any]							) ->     Dict:
						SCREAMING_SNAKE_CASE__										=   """"""
						for tail in self.adjacency:
									for head in self.adjacency[tail]:
												SCREAMING_SNAKE_CASE__										=   self.adjacency[head][tail]
												string += F"""{head} -> {tail} == {weight}\n"""
						return string.rstrip("""\n"""							)

			def        SCREAMING_SNAKE_CASE					(       self					:    int							) ->     Dict:
						SCREAMING_SNAKE_CASE__										=   []
						for tail in self.adjacency:
									for head in self.adjacency[tail]:
												output.append((tail, head, self.adjacency[head][tail])							)
						return output

			def        SCREAMING_SNAKE_CASE					(       self					:    Optional[Any]							) ->     str:
						return self.adjacency.keys()

			@staticmethod
			def        SCREAMING_SNAKE_CASE					(       __UpperCAmelCase					:    Union[str, Any]=None     ,					__UpperCAmelCase					:    List[Any]=None							) ->     Optional[int]:
						SCREAMING_SNAKE_CASE__										=   Graph()
						if vertices is None:
									SCREAMING_SNAKE_CASE__										=   []
						if edges is None:
									SCREAMING_SNAKE_CASE__										=   []
						for vertex in vertices:
									g.add_vertex(__UpperCAmelCase							)
						for edge in edges:
									g.add_edge(*__UpperCAmelCase							)
						return g





			class  lowerCamelCase    :

						def __init__(       self					:    Optional[Any]							) ->     str:
									SCREAMING_SNAKE_CASE__										=   {}
									SCREAMING_SNAKE_CASE__										=   {}

						def __len__(       self					:    Any							) ->     List[str]:
									return len(self.parent							)

						def        SCREAMING_SNAKE_CASE					(       self					:    List[Any]     ,					__UpperCAmelCase					:    Tuple							) ->     Optional[Any]:
									if item in self.parent:
												return self.find(__UpperCAmelCase							)

									SCREAMING_SNAKE_CASE__										=   item
									SCREAMING_SNAKE_CASE__										=   0
									return item

						def        SCREAMING_SNAKE_CASE					(       self					:    List[Any]     ,					__UpperCAmelCase					:    Tuple							) ->     Any:
									if item not in self.parent:
												return self.make_set(__UpperCAmelCase							)
									if item != self.parent[item]:
												SCREAMING_SNAKE_CASE__										=   self.find(self.parent[item]							)
									return self.parent[item]





						def        SCREAMING_SNAKE_CASE					(       self					:    int     ,					__UpperCAmelCase					:    Optional[int]     ,					__UpperCAmelCase					:    Tuple							) ->     int:
									SCREAMING_SNAKE_CASE__										=   self.find(__UpperCAmelCase							)
									SCREAMING_SNAKE_CASE__										=   self.find(__UpperCAmelCase							)

									if roota == roota:
												return roota

									if self.rank[roota] > self.rank[roota]:
												SCREAMING_SNAKE_CASE__										=   roota
												return roota

									if self.rank[roota] < self.rank[roota]:
												SCREAMING_SNAKE_CASE__										=   roota
												return roota

									if self.rank[roota] == self.rank[roota]:
												self.rank[roota] += 1
												SCREAMING_SNAKE_CASE__										=   roota
												return roota
									return None

			@staticmethod
			def        SCREAMING_SNAKE_CASE					(       __UpperCAmelCase					:    List[Any]							) ->     Optional[Any]:
						SCREAMING_SNAKE_CASE__										=   graph.num_vertices

						SCREAMING_SNAKE_CASE__										=   Graph.UnionFind()
						SCREAMING_SNAKE_CASE__										=   []
						while num_components > 1:
									SCREAMING_SNAKE_CASE__										=   {}
									for vertex in graph.get_vertices():
												SCREAMING_SNAKE_CASE__										=   -1

									SCREAMING_SNAKE_CASE__										=   graph.get_edges()
									for edge in edges:
												SCREAMING_SNAKE_CASE__				,		SCREAMING_SNAKE_CASE__				,		SCREAMING_SNAKE_CASE__										=   edge
												edges.remove((tail, head, weight)							)
									for edge in edges:
												SCREAMING_SNAKE_CASE__				,		SCREAMING_SNAKE_CASE__				,		SCREAMING_SNAKE_CASE__										=   edge
												SCREAMING_SNAKE_CASE__										=   union_find.find(__UpperCAmelCase							)
												SCREAMING_SNAKE_CASE__										=   union_find.find(__UpperCAmelCase							)
												if seta != seta:
															if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																		SCREAMING_SNAKE_CASE__										=   [head, tail, weight]

															if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																		SCREAMING_SNAKE_CASE__										=   [head, tail, weight]
									for vertex in cheap_edge:
												if cheap_edge[vertex] != -1:
															SCREAMING_SNAKE_CASE__				,		SCREAMING_SNAKE_CASE__				,		SCREAMING_SNAKE_CASE__										=   cheap_edge[vertex]
															if union_find.find(__UpperCAmelCase							) != union_find.find(__UpperCAmelCase							):
																		union_find.union(__UpperCAmelCase     ,					__UpperCAmelCase							)
																		mst_edges.append(cheap_edge[vertex]							)
																		SCREAMING_SNAKE_CASE__										=   num_components - 1
						SCREAMING_SNAKE_CASE__										=   Graph.build(edges=__UpperCAmelCase							)
						return mst





"""simple docstring"""




A_				:      Any           =			"0.21.0"

from .accelerator import Accelerator
from .big_modeling import (
    cpu_offload,
    cpu_offload_with_hook,
    disk_offload,
    dispatch_model,
    init_empty_weights,
    init_on_device,
    load_checkpoint_and_dispatch,
)
from .data_loader import skip_first_batches
from .launchers import debug_launcher, notebook_launcher
from .state import PartialState
from .utils import (
    DeepSpeedPlugin,
    DistributedDataParallelKwargs,
    DistributedType,
    FullyShardedDataParallelPlugin,
    GradScalerKwargs,
    InitProcessGroupKwargs,
    find_executable_batch_size,
    infer_auto_device_map,
    is_rich_available,
    load_checkpoint_in_model,
    synchronize_rng_states,
)


if is_rich_available():
						from .utils import rich


