
"""simple docstring"""







_SCREAMING_SNAKE_CASE	       =      [0, 2, 4, 6, 8]
_SCREAMING_SNAKE_CASE	       =      [1, 3, 5, 7, 9]
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE )  ->     int:







							"""simple docstring"""


							if remaining_length == 0:
														if digits[0] == 0 or digits[-1] == 0:
																					return 0

														for i in range(length // 2 - 1							,    -1							,    -1 ):
																					remainder += digits[i] + digits[length - i - 1]

																					if remainder % 2 == 0:
																												return 0

																					remainder //= 10

														return 1

							if remaining_length == 1:
														if remainder % 2 == 0:
																					return 0

														__snake_case     			=       0
														for digit in range(10 ):
																					__snake_case     			=       digit
																					result += reversible_numbers(
																					    0							,    (remainder + 2 * digit) // 10							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE )
														return result

							__snake_case     			=       0
							for digita in range(10 ):
														__snake_case     			=       digita

														if (remainder + digita) % 2 == 0:
																					__snake_case     			=       ODD_DIGITS
														else:
																					__snake_case     			=       EVEN_DIGITS

														for digita in other_parity_digits:
																					__snake_case     			=       digita
																					result += reversible_numbers(
																					    remaining_length - 2							,    (remainder + digita + digita) // 10							,    SCREAMING_SNAKE_CASE							,    SCREAMING_SNAKE_CASE							,    )
							return result
def   __UpperCamelCase   (					SCREAMING_SNAKE_CASE = 9 )  ->     int:







							"""simple docstring"""


							__snake_case     			=       0
							for length in range(1							,    max_power + 1 ):
														result += reversible_numbers(SCREAMING_SNAKE_CASE							,    0							,    [0] * length							,    SCREAMING_SNAKE_CASE )
							return result


if __name__ == "__main__":
		print(F"""{solution() = }""")


"""simple docstring"""







from __future__ import annotations

_SCREAMING_SNAKE_CASE	       =      {
    """A""": ["""B""", """C""", """E"""],
    """B""": ["""A""", """D""", """E"""],
    """C""": ["""A""", """F""", """G"""],
    """D""": ["""B"""],
    """E""": ["""A""", """B""", """D"""],
    """F""": ["""C"""],
    """G""": ["""C"""],
}







class 							__magic_name__     :





					def __init__(				self   :							Any							,						snake_case_   :							dict[str, list[str]]							,						snake_case_   :							str    ):
												__snake_case     			=       graph
												# mapping node to its parent in resulting breadth first tree
												__snake_case     			=       {}
												__snake_case     			=       source_vertex





					def 							lowerCAmelCase      (				self   :							Union[str, Any]    ):
												__snake_case     			=       {self.source_vertex}
												__snake_case     			=       None
												__snake_case     			=       [self.source_vertex]  # first in first out queue

												while queue:
																			__snake_case     			=       queue.pop(0    )
																			for adjacent_vertex in self.graph[vertex]:
																										if adjacent_vertex not in visited:
																																	visited.add(snake_case_    )
																																	__snake_case     			=       vertex
																																	queue.append(snake_case_    )





					def 							lowerCAmelCase      (				self   :							Dict							,						snake_case_   :							str    ):
												if target_vertex == self.source_vertex:
																			return self.source_vertex

												__snake_case     			=       self.parent.get(snake_case_    )
												if target_vertex_parent is None:
																			__snake_case     			=       (
																			    F'''No path from vertex: {self.source_vertex} to vertex: {target_vertex}'''
																			)
																			raise ValueError(snake_case_    )

												return self.shortest_path(snake_case_    ) + F'''->{target_vertex}'''


if __name__ == "__main__":
		_SCREAMING_SNAKE_CASE	       =      Graph(graph, """G""")
		g.breath_first_search()
		print(g.shortest_path("""D"""))
		print(g.shortest_path("""G"""))
		print(g.shortest_path("""Foo"""))
