






from collections import Counter
from timeit import timeit

def   snake_case (UpperCAmelCase__ = ""     ,   )	->    List[str]:
  return sum(c % 2 for c in Counter(input_str.replace(' '     ,   ''  ).lower()  ).values()  ) < 2

def   snake_case (UpperCAmelCase__ = ""  )	->    Union[str, Any]:






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

  for character in lower_case_input_str:
    UpperCamelCase_: Dict   				=    character_freq_dict.get(_a     ,   0  ) + 1
  UpperCamelCase_: 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   snake_case (UpperCAmelCase__ = ""  )	->    Any:
  print('\nFor string = '     ,   _a     ,   ':'  )
  print(
      '> can_string_be_rearranged_as_palindrome_counter()'     ,   '\tans ='     ,   can_string_be_rearranged_as_palindrome_counter(_a  )     ,   '\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(_a  )     ,   '\ttime ='     ,   timeit(
          'z.can_string_be_rearranged_as_palindrome(z.check_str)'     ,   setup='import __main__ as z'     ,   )     ,   'seconds'     ,   )


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







# A Bipartite Graph is a graph whose vertices can be divided into two independent sets,
# U and V such that every edge (u, v) either connects a vertex from U to V or a vertex
# from V to U. In other words, for every edge (u, v), either u belongs to U and v to V,
# or u belongs to V and v to U. We can also say that there is no edge that connects
# vertices of same set.

def   snake_case (UpperCAmelCase__  )	->    List[str]:
  UpperCamelCase_: int   				=    [False] * len(UpperCAmelCase__  )
  UpperCamelCase_: Any   				=    [-1] * len(UpperCAmelCase__  )

  def dfs(UpperCAmelCase__     ,   UpperCAmelCase__  ):
    UpperCamelCase_: Tuple   				=    True
    UpperCamelCase_: Optional[int]   				=    c
    for u in graph[v]:
      if not visited[u]:
        dfs(UpperCAmelCase__     ,   1 - c  )

  for i in range(len(UpperCAmelCase__  )  ):
    if not visited[i]:
      dfs(UpperCAmelCase__     ,   0  )

  for i in range(len(UpperCAmelCase__  )  ):
    for j in graph[i]:
      if color[i] == color[j]:
        return False

  return True


# Adjacency list of graph
A_		:		Dict		     =			{0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: []}
print(check_bipartite_dfs(graph))