




"""simple docstring"""


# using dfs for finding eulerian path traversal


def 					UpperCAmelCase__       (snake_case__							:					List[str]		,   snake_case__							:					Tuple		,   snake_case__							:					int		,   snake_case__							:					List[str]=None    ):
  """simple docstring"""

  _snake_case							:		List[Any]								=  (path or []) + [u]
  for v in graph[u]:
    if visited_edge[u][v] is False:
      _snake_case		,					_snake_case							:		Dict								=  True, True
      _snake_case							:		str								=  dfs(snake_case__		,   snake_case__		,   snake_case__		,   snake_case__    )
  return path


def 					UpperCAmelCase__       (snake_case__							:					Union[str, Any]		,   snake_case__							:					Optional[int]    ):
  """simple docstring"""

  _snake_case							:		List[str]								=  0
  _snake_case							:		List[str]								=  -1
  for i in range(snake_case__    ):
    if i not in graph.keys():
      continue
    if len(graph[i]    ) % 2 == 1:
      odd_degree_nodes += 1
      _snake_case							:		int								=  i
  if odd_degree_nodes == 0:
    return 1, odd_node
  if odd_degree_nodes == 2:
    return 2, odd_node
  return 3, odd_node


def 					UpperCAmelCase__       (snake_case__							:					Optional[int]		,   snake_case__							:					List[Any]    ):
  """simple docstring"""

  _snake_case							:		Tuple								=  [[False for _ in range(max_node + 1    )] for _ in range(max_node + 1    )]
  _snake_case		,					_snake_case							:		Dict								=  check_circuit_or_path(snake_case__		,   snake_case__    )
  if check == 3:
    print("""graph is not Eulerian"""    )
    print("""no path"""    )
    return
  _snake_case							:		int								=  1
  if check == 2:
    _snake_case							:		Optional[int]								=  odd_node
    print("""graph has a Euler path"""    )
  if check == 1:
    print("""graph has a Euler cycle"""    )
  _snake_case							:		Optional[int]								=  dfs(snake_case__		,   snake_case__		,   snake_case__    )
  print(snake_case__    )


def 					UpperCAmelCase__       ():
  """simple docstring"""

  _snake_case							:		List[str]								=  {1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [4]}
  _snake_case							:		Dict								=  {1: [2, 3, 4, 5], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [1, 4]}
  _snake_case							:		Optional[Any]								=  {1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2], 4: [1, 2, 5], 5: [4]}
  _snake_case							:		List[str]								=  {1: [2, 3], 2: [1, 3], 3: [1, 2]}
  _snake_case							:		List[str]								=  {
      1: [],
      2: []
      # all degree is zero
  }
  _snake_case							:		List[Any]								=  10
  check_euler(snake_case__		,   snake_case__    )
  check_euler(snake_case__		,   snake_case__    )
  check_euler(snake_case__		,   snake_case__    )
  check_euler(snake_case__		,   snake_case__    )
  check_euler(snake_case__		,   snake_case__    )


if __name__ == "__main__":
     main()








"""simple docstring"""


from math import factorial

A_						=				{str(d): factorial(d) for d in range(10)}


def 					UpperCAmelCase__       (snake_case__							:					int    ):
  """simple docstring"""

  return sum(DIGIT_FACTORIAL[d] for d in str(snake_case__    )    )


def 					UpperCAmelCase__       ():
  """simple docstring"""

  _snake_case							:		List[str]								=  7 * factorial(9    ) + 1
  return sum(i for i in range(3		,   snake_case__    ) if sum_of_digit_factorial(snake_case__    ) == i    )


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


