



from collections import Counter
from timeit import timeit



def 	__a					(   lowerCAmelCase_       : str = ""      ,)				->			bool:






						'''simple docstring'''



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



def 	__a					(   lowerCAmelCase_       : str = ""    )				->			bool:






						'''simple docstring'''



						if len(lowerCAmelCase_    ) == 0:
												return True
						UpperCAmelCase_=       input_str.replace(""" """      ,""""""    ).lower()
						# character_freq_dict: Stores the frequency of every character in the input string
						UpperCAmelCase_=       {}

						for character in lower_case_input_str:
												UpperCAmelCase_=       character_freq_dict.get(lowerCAmelCase_      ,0    ) + 1
						UpperCAmelCase_=       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					(   lowerCAmelCase_       : str = ""    )				->			None:






						'''simple docstring'''



						print("""\nFor string = """      ,lowerCAmelCase_      ,""":"""    )
						print(
						    """> can_string_be_rearranged_as_palindrome_counter()"""      ,"""\tans ="""      ,can_string_be_rearranged_as_palindrome_counter(lowerCAmelCase_    )      ,"""\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(lowerCAmelCase_    )      ,"""\ttime ="""      ,timeit(
						        """z.can_string_be_rearranged_as_palindrome(z.check_str)"""      ,setup="""import __main__ as z"""      ,)      ,"""seconds"""      ,)


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









def 	__a					(   lowerCAmelCase_       : Dict    )				->			Dict:






						'''simple docstring'''



						return [
						    {
						        0: [1, 2],
						        1: [0, 2],
						        2: [0, 1, 3, 5],
						        3: [2, 4],
						        4: [3],
						        5: [2, 6, 8],
						        6: [5, 7],
						        7: [6, 8],
						        8: [5, 7],
						    },
						    {
						        0: [6],
						        1: [9],
						        2: [4, 5],
						        3: [4],
						        4: [2, 3],
						        5: [2],
						        6: [0, 7],
						        7: [6],
						        8: [],
						        9: [1],
						    },
						    {
						        0: [4],
						        1: [6],
						        2: [],
						        3: [5, 6, 7],
						        4: [0, 6],
						        5: [3, 8, 9],
						        6: [1, 3, 4, 7],
						        7: [3, 6, 8, 9],
						        8: [5, 7],
						        9: [5, 7],
						    },
						    {
						        0: [1, 3],
						        1: [0, 2, 4],
						        2: [1, 3, 4],
						        3: [0, 2, 4],
						        4: [1, 2, 3],
						    },
						][index]



def 	__a					(   lowerCAmelCase_       : dict[int, list[int]]    )				->			list[tuple[int, int]]:






						'''simple docstring'''



						UpperCAmelCase_=       0
						UpperCAmelCase_=       len(lowerCAmelCase_    )  # No of vertices in graph
						UpperCAmelCase_=       [0] * n
						UpperCAmelCase_=       [False] * n

						def dfs(lowerCAmelCase_       : Optional[int]      ,lowerCAmelCase_       : Dict      ,lowerCAmelCase_       : Any      ,lowerCAmelCase_       : int    ):
												UpperCAmelCase_=       True
												UpperCAmelCase_=       id_
												id_ += 1
												for to in graph[at]:
																		if to == parent:
																								pass
																		elif not visited[to]:
																								dfs(lowerCAmelCase_      ,lowerCAmelCase_      ,lowerCAmelCase_      ,id_    )
																								UpperCAmelCase_=       min(low[at]      ,low[to]    )
																								if id_ <= low[to]:
																														bridges.append((at, to) if at < to else (to, at)    )
																		else:
																								# This edge is a back edge and cannot be a bridge
																								UpperCAmelCase_=       min(low[at]      ,low[to]    )

						UpperCAmelCase_=       []
						for i in range(lowerCAmelCase_    ):
												if not visited[i]:
																		dfs(lowerCAmelCase_      ,-1      ,lowerCAmelCase_      ,id_    )
						return bridges


if __name__ == "__main__":
	import doctest

	doctest.testmod()




