
from __future__ import annotations

from typing import Any





class 			_lowerCAmelCase      :




				def __init__(      self       ,       _UpperCamelCase  )       ->   None:
							lowerCAmelCase_      			=			num_of_nodes
							lowerCAmelCase_      			=			[]
							lowerCAmelCase_      			=			{}




				def   __a		(      self       ,       _UpperCamelCase       ,       _UpperCamelCase       ,       _UpperCamelCase  )       ->   None:
							self.m_edges.append([u_node, v_node, weight]  )




				def   __a		(      self       ,       _UpperCamelCase  )       ->   int:

							if self.m_component[u_node] == u_node:
										return u_node
							return self.find_component(self.m_component[u_node]  )




				def   __a		(      self       ,       _UpperCamelCase  )       ->   None:

							if self.m_component[u_node] != u_node:
										for k in self.m_component:
													lowerCAmelCase_      			=			self.find_component(_UpperCamelCase  )




				def   __a		(      self       ,       _UpperCamelCase       ,       _UpperCamelCase       ,       _UpperCamelCase  )       ->   None:

							if component_size[u_node] <= component_size[v_node]:
										lowerCAmelCase_      			=			v_node
										component_size[v_node] += component_size[u_node]
										self.set_component(_UpperCamelCase  )

							elif component_size[u_node] >= component_size[v_node]:
										lowerCAmelCase_      			=			self.find_component(_UpperCamelCase  )
										component_size[u_node] += component_size[v_node]
										self.set_component(_UpperCamelCase  )




				def   __a		(      self  )       ->   None:
							lowerCAmelCase_      			=			[]
							lowerCAmelCase_      			=			0

							lowerCAmelCase_      			=			[-1] * self.m_num_of_nodes

							# A list of components (initialized to all of the nodes)
							for node in range(self.m_num_of_nodes  ):
										self.m_component.update({node: node}  )
										component_size.append(1  )

							lowerCAmelCase_      			=			self.m_num_of_nodes

							while num_of_components > 1:
										for edge in self.m_edges:
													lowerCAmelCase_			,						lowerCAmelCase_			,						lowerCAmelCase_      			=			edge

													lowerCAmelCase_      			=			self.m_component[u]
													lowerCAmelCase_      			=			self.m_component[v]

													if u_component != v_component:

																for component in (u_component, v_component):
																			if (
																			    minimum_weight_edge[component] == -1
																			    or minimum_weight_edge[component][2] > w
																			):
																						lowerCAmelCase_      			=			[u, v, w]

										for edge in minimum_weight_edge:
													if isinstance(_UpperCamelCase       ,       _UpperCamelCase  ):
																lowerCAmelCase_			,						lowerCAmelCase_			,						lowerCAmelCase_      			=			edge

																lowerCAmelCase_      			=			self.m_component[u]
																lowerCAmelCase_      			=			self.m_component[v]

																if u_component != v_component:
																			mst_weight += w
																			self.union(_UpperCamelCase       ,       _UpperCamelCase       ,       _UpperCamelCase  )
																			print(f"""Added edge [{u} - {v}]\nAdded weight: {w}\n"""  )
																			num_of_components -= 1

										lowerCAmelCase_      			=			[-1] * self.m_num_of_nodes
							print(f"""The total weight of the minimal spanning tree is: {mst_weight}"""  )






def      lowerCamelCase__       (       ):




			"""simple docstring"""




if __name__ == "__main__":
			import doctest

			doctest.testmod()





import itertools
import string
from collections.abc import Generator, Iterable






def      lowerCamelCase__       (       __lowerCAmelCase						:						Iterable[str]					,							__lowerCAmelCase						:						int       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			iter(__lowerCAmelCase       )
			while True:
						lowerCAmelCase_      			=			tuple(itertools.islice(__lowerCAmelCase					,							__lowerCAmelCase       )       )
						if not chunk:
									return
						yield chunk






def      lowerCamelCase__       (       __lowerCAmelCase						:						str       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			"".join([c.upper() for c in dirty if c in string.ascii_letters]       )
			lowerCAmelCase_      			=			""

			if len(__lowerCAmelCase       ) < 2:
						return dirty

			for i in range(len(__lowerCAmelCase       ) - 1       ):
						clean += dirty[i]

						if dirty[i] == dirty[i + 1]:
									clean += "X"

			clean += dirty[-1]

			if len(__lowerCAmelCase       ) & 1:
						clean += "X"

			return clean






def      lowerCamelCase__       (       __lowerCAmelCase						:						str       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			"ABCDEFGHIKLMNOPQRSTUVWXYZ"
			# we're using a list instead of a '2d' array because it makes the math
			# for setting up the table and doing the actual encoding/decoding simpler
			lowerCAmelCase_      			=			[]

			# copy key chars into the table if they are in `alphabet` ignoring duplicates
			for char in key.upper():
						if char not in table and char in alphabet:
									table.append(__lowerCAmelCase       )

    # fill the rest of the table in with the remaining alphabet chars
			for char in alphabet:
						if char not in table:
									table.append(__lowerCAmelCase       )

			return table






def      lowerCamelCase__       (       __lowerCAmelCase						:						str					,							__lowerCAmelCase						:						str       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			generate_table(__lowerCAmelCase       )
			lowerCAmelCase_      			=			prepare_input(__lowerCAmelCase       )
			lowerCAmelCase_      			=			""

			# https://en.wikipedia.org/wiki/Playfair_cipher#Description
			for chara, chara in chunker(__lowerCAmelCase					,							2       ):
						lowerCAmelCase_			,						lowerCAmelCase_      			=			divmod(table.index(__lowerCAmelCase       )					,							5       )
						lowerCAmelCase_			,						lowerCAmelCase_      			=			divmod(table.index(__lowerCAmelCase       )					,							5       )

						if rowa == rowa:
									ciphertext += table[rowa * 5 + (cola + 1) % 5]
									ciphertext += table[rowa * 5 + (cola + 1) % 5]
						elif cola == cola:
									ciphertext += table[((rowa + 1) % 5) * 5 + cola]
									ciphertext += table[((rowa + 1) % 5) * 5 + cola]
						else:  # rectangle
									ciphertext += table[rowa * 5 + cola]
									ciphertext += table[rowa * 5 + cola]

			return ciphertext






def      lowerCamelCase__       (       __lowerCAmelCase						:						str					,							__lowerCAmelCase						:						str       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			generate_table(__lowerCAmelCase       )
			lowerCAmelCase_      			=			""

			# https://en.wikipedia.org/wiki/Playfair_cipher#Description
			for chara, chara in chunker(__lowerCAmelCase					,							2       ):
						lowerCAmelCase_			,						lowerCAmelCase_      			=			divmod(table.index(__lowerCAmelCase       )					,							5       )
						lowerCAmelCase_			,						lowerCAmelCase_      			=			divmod(table.index(__lowerCAmelCase       )					,							5       )

						if rowa == rowa:
									plaintext += table[rowa * 5 + (cola - 1) % 5]
									plaintext += table[rowa * 5 + (cola - 1) % 5]
						elif cola == cola:
									plaintext += table[((rowa - 1) % 5) * 5 + cola]
									plaintext += table[((rowa - 1) % 5) * 5 + cola]
						else:  # rectangle
									plaintext += table[rowa * 5 + cola]
									plaintext += table[rowa * 5 + cola]

			return plaintext



