



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







def snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							Generator[tuple[str, ...], None, None]:
		UpperCAmelCase_						=				iter(__SCREAMING_SNAKE_CASE )
		while True:
				UpperCAmelCase_						=				tuple(itertools.islice(__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE ) )
				if not chunk:
						return
				yield chunk







def snake_case__  (			__SCREAMING_SNAKE_CASE )		->							str:
		UpperCAmelCase_						=				"".join([c.upper() for c in dirty if c in string.ascii_letters] )
		UpperCAmelCase_						=				""

		if len(__SCREAMING_SNAKE_CASE ) < 2:
				return dirty

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

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

		clean += dirty[-1]

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

		return clean







def snake_case__  (			__SCREAMING_SNAKE_CASE )		->							list[str]:
		# I and J are used interchangeably to allow
		# us to use a 5x5 table (25 letters)
		UpperCAmelCase_						=				"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
		UpperCAmelCase_						=				[]

		# 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(__SCREAMING_SNAKE_CASE )

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

		return table







def snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							str:
		UpperCAmelCase_						=				generate_table(__SCREAMING_SNAKE_CASE )
		UpperCAmelCase_						=				prepare_input(__SCREAMING_SNAKE_CASE )
		UpperCAmelCase_						=				""

		# https://en.wikipedia.org/wiki/Playfair_cipher#Description
		for chara, chara in chunker(__SCREAMING_SNAKE_CASE			,     2 ):
				UpperCAmelCase_					,						UpperCAmelCase_						=				divmod(table.index(__SCREAMING_SNAKE_CASE )			,     5 )
				UpperCAmelCase_					,						UpperCAmelCase_						=				divmod(table.index(__SCREAMING_SNAKE_CASE )			,     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 snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							str:
		UpperCAmelCase_						=				generate_table(__SCREAMING_SNAKE_CASE )
		UpperCAmelCase_						=				""

		# https://en.wikipedia.org/wiki/Playfair_cipher#Description
		for chara, chara in chunker(__SCREAMING_SNAKE_CASE			,     2 ):
				UpperCAmelCase_					,						UpperCAmelCase_						=				divmod(table.index(__SCREAMING_SNAKE_CASE )			,     5 )
				UpperCAmelCase_					,						UpperCAmelCase_						=				divmod(table.index(__SCREAMING_SNAKE_CASE )			,     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






import heapq as hq
import math
from collections.abc import Iterator



class 	lowerCamelCase      :







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				str(id_     )
							UpperCAmelCase_						=				None
							UpperCAmelCase_						=				None
							UpperCAmelCase_						=				[]
							UpperCAmelCase_						=				{}  # {vertex:distance}



					def __lt__(			self    ,	lowerCAmelCase     ):
							return self.key < other.key



					def __repr__(			self     ):
							return self.id



					def    A__		(			self    ,	lowerCAmelCase     ):
							self.neighbors.append(lowerCAmelCase     )



					def    A__		(			self    ,	lowerCAmelCase    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				weight







def snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							Optional[int]:
		# add the neighbors:
		graph[a - 1].add_neighbor(graph[b - 1] )
		graph[b - 1].add_neighbor(graph[a - 1] )
		# add the edges:
		graph[a - 1].add_edge(graph[b - 1]			,     __SCREAMING_SNAKE_CASE )
		graph[b - 1].add_edge(graph[a - 1]			,     __SCREAMING_SNAKE_CASE )







def snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							list:
		UpperCAmelCase_						=				[]
		for u in graph:
				UpperCAmelCase_						=				math.inf
				UpperCAmelCase_						=				None
		UpperCAmelCase_						=				0
		UpperCAmelCase_						=				graph[:]
		while q:
				UpperCAmelCase_						=				min(__SCREAMING_SNAKE_CASE )
				q.remove(__SCREAMING_SNAKE_CASE )
				for v in u.neighbors:
						if (v in q) and (u.edges[v.id] < v.key):
								UpperCAmelCase_						=				u
								UpperCAmelCase_						=				u.edges[v.id]
		for i in range(1			,     len(__SCREAMING_SNAKE_CASE ) ):
				a.append((int(graph[i].id ) + 1, int(graph[i].pi.id ) + 1) )
		return a







def snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							Iterator[tuple]:
		for u in graph:
				UpperCAmelCase_						=				math.inf
				UpperCAmelCase_						=				None
		UpperCAmelCase_						=				0

		UpperCAmelCase_						=				list(__SCREAMING_SNAKE_CASE )
		hq.heapify(__SCREAMING_SNAKE_CASE )

		while h:
				UpperCAmelCase_						=				hq.heappop(__SCREAMING_SNAKE_CASE )
				for v in u.neighbors:
						if (v in h) and (u.edges[v.id] < v.key):
								UpperCAmelCase_						=				u
								UpperCAmelCase_						=				u.edges[v.id]
								hq.heapify(__SCREAMING_SNAKE_CASE )

		for i in range(1			,     len(__SCREAMING_SNAKE_CASE ) ):
				yield (int(graph[i].id ) + 1, int(graph[i].pi.id ) + 1)







def snake_case__  (			)		->							None:
		pass


if __name__ == "__main__":
			import doctest

			doctest.testmod()

