


from collections import Counter
from timeit import timeit




def 	a_      (    SCREAMING_SNAKE_CASE__					:      str = ""		,			):
       '''simple docstring'''





       return sum(c % 2 for c in Counter(input_str.replace(' '		,			''     ).lower()     ).values()     ) < 2




def 	a_      (    SCREAMING_SNAKE_CASE__					:      str = ""     ):
       '''simple docstring'''





       if len(SCREAMING_SNAKE_CASE__     ) == 0:
              return True
       _lowerCamelCase       :		str		=input_str.replace(' '		,			''     ).lower()
       # character_freq_dict: Stores the frequency of every character in the input string
       _lowerCamelCase       :		dict[str, int]		={}

       for character in lower_case_input_str:
              _lowerCamelCase       :		Optional[Any]		=character_freq_dict.get(SCREAMING_SNAKE_CASE__		,			0     ) + 1
       _lowerCamelCase       :		Union[str, Any]		=0

       for character_count in character_freq_dict.values():
              if character_count % 2:
                     odd_char += 1
       if odd_char > 1:
              return False
       return True




def 	a_      (    SCREAMING_SNAKE_CASE__					:      str = ""     ):
       '''simple docstring'''





       print('\nFor string = '		,			SCREAMING_SNAKE_CASE__		,			':'     )
       print(
           '> can_string_be_rearranged_as_palindrome_counter()'		,			'\tans ='		,			can_string_be_rearranged_as_palindrome_counter(SCREAMING_SNAKE_CASE__     )		,			'\ttime ='		,			timeit(
               'z.can_string_be_rearranged_as_palindrome_counter(z.check_str)'		,			setup='import __main__ as z'		,			)		,			'seconds'		,			)
       print(
           '> can_string_be_rearranged_as_palindrome()'		,			'\tans ='		,			can_string_be_rearranged_as_palindrome(SCREAMING_SNAKE_CASE__     )		,			'\ttime ='		,			timeit(
               'z.can_string_be_rearranged_as_palindrome(z.check_str)'		,			setup='import __main__ as z'		,			)		,			'seconds'		,			)


if __name__ == "__main__":
 lowerCamelCase											=       input(
     'Enter string to determine if it can be rearranged as a palindrome or not: '
 ).strip()
 benchmark(check_str)
 lowerCamelCase											=       can_string_be_rearranged_as_palindrome_counter(check_str)
 print(F"""{check_str} can {"" if status else "not "}be rearranged as a palindrome""")






# using dfs for finding eulerian path traversal




def 	a_      (    SCREAMING_SNAKE_CASE__					:      Any		,			SCREAMING_SNAKE_CASE__					:      List[str]		,			SCREAMING_SNAKE_CASE__					:      List[str]		,			SCREAMING_SNAKE_CASE__					:      Optional[int]=None     ):
       '''simple docstring'''





       _lowerCamelCase       :		Optional[Any]		=(path or []) + [u]
       for v in graph[u]:
              if visited_edge[u][v] is False:
                     _lowerCamelCase	,     _lowerCamelCase       :		Dict		=True, True
                     _lowerCamelCase       :		Optional[Any]		=dfs(SCREAMING_SNAKE_CASE__		,			SCREAMING_SNAKE_CASE__		,			SCREAMING_SNAKE_CASE__		,			SCREAMING_SNAKE_CASE__     )
       return path




def 	a_      (    SCREAMING_SNAKE_CASE__					:      List[str]		,			SCREAMING_SNAKE_CASE__					:      Optional[Any]     ):
       '''simple docstring'''





       _lowerCamelCase       :		Union[str, Any]		=0
       _lowerCamelCase       :		Union[str, Any]		=-1
       for i in range(SCREAMING_SNAKE_CASE__     ):
              if i not in graph.keys():
                     continue
              if len(graph[i]     ) % 2 == 1:
                     odd_degree_nodes += 1
                     _lowerCamelCase       :		Tuple		=i
       if odd_degree_nodes == 0:
              return 1, odd_node
       if odd_degree_nodes == 2:
              return 2, odd_node
       return 3, odd_node




def 	a_      (    SCREAMING_SNAKE_CASE__					:      Union[str, Any]		,			SCREAMING_SNAKE_CASE__					:      Any     ):
       '''simple docstring'''





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




def 	a_      (    ):
       '''simple docstring'''





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


if __name__ == "__main__":
 main()


