



'''simple docstring'''





from collections import deque
from math import floor
from random import random
from time import time






class        lowerCAmelCase_:
  '''simple docstring'''




  def __init__(    self      )    ->		int:
      lowerCAmelCase__ :  Optional[int]							      =					{}




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase  ,__UpperCAmelCase  ,__UpperCAmelCase=1      )    ->		Dict:
      if self.graph.get(__UpperCAmelCase      ):
          if self.graph[u].count([w, v]      ) == 0:
              self.graph[u].append([w, v]      )
      else:
          lowerCAmelCase__ :  List[str]							      =					[[w, v]]
      if not self.graph.get(__UpperCAmelCase      ):
          lowerCAmelCase__ :  Dict							      =					[]




  def 							UpperCAmelCase_	(    self      )    ->		Tuple:
      return list(self.graph      )




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase  ,__UpperCAmelCase      )    ->		Union[str, Any]:
      if self.graph.get(__UpperCAmelCase      ):
          for _ in self.graph[u]:
              if _[1] == v:
                  self.graph[u].remove(__UpperCAmelCase      )




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-2  ,__UpperCAmelCase=-1      )    ->		Optional[Any]:
      if s == d:
          return []
      lowerCAmelCase__ :  Any							      =					[]
      lowerCAmelCase__ :  Tuple							      =					[]
      if s == -2:
          lowerCAmelCase__ :  Any							      =					list(self.graph      )[0]
      stack.append(__UpperCAmelCase      )
      visited.append(__UpperCAmelCase      )
      lowerCAmelCase__ :  Union[str, Any]							      =					s

      while True:
          # check if there is any non isolated nodes
          if len(self.graph[s]      ) != 0:
              lowerCAmelCase__ :  Any							      =					s
              for node in self.graph[s]:
                  if visited.count(node[1]      ) < 1:
                      if node[1] == d:
                          visited.append(__UpperCAmelCase      )
                          return visited
                      else:
                          stack.append(node[1]      )
                          visited.append(node[1]      )
                          lowerCAmelCase__ :  List[Any]							      =					node[1]
                          break

            # check if all the children are visited
          if s == ss:
              stack.pop()
              if len(__UpperCAmelCase      ) != 0:
                  lowerCAmelCase__ :  Any							      =					stack[len(__UpperCAmelCase      ) - 1]
          else:
              lowerCAmelCase__ :  int							      =					ss

          # check if se have reached the starting point
          if len(__UpperCAmelCase      ) == 0:
              return visited




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-1      )    ->		List[Any]:
      if c == -1:
          lowerCAmelCase__ :  Tuple							      =					floor(random() * 1_0000      ) + 10
      for i in range(__UpperCAmelCase      ):
          # every vertex has max 100 edges
          for _ in range(floor(random() * 102      ) + 1      ):
              lowerCAmelCase__ :  int							      =					floor(random() * c      ) + 1
              if n != i:
                  self.add_pair(__UpperCAmelCase  ,__UpperCAmelCase  ,1      )




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-2      )    ->		int:
      lowerCAmelCase__ :  List[Any]							      =					deque()
      lowerCAmelCase__ :  Tuple							      =					[]
      if s == -2:
          lowerCAmelCase__ :  Optional[int]							      =					list(self.graph      )[0]
      d.append(__UpperCAmelCase      )
      visited.append(__UpperCAmelCase      )
      while d:
          lowerCAmelCase__ :  Optional[int]							      =					d.popleft()
          if len(self.graph[s]      ) != 0:
              for node in self.graph[s]:
                  if visited.count(node[1]      ) < 1:
                      d.append(node[1]      )
                      visited.append(node[1]      )
      return visited




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase      )    ->		str:
      lowerCAmelCase__ :  Optional[Any]							      =					0
      for x in self.graph:
          for y in self.graph[x]:
              if y[1] == u:
                  count += 1
      return count




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase      )    ->		str:
      return len(self.graph[u]      )




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-2      )    ->		Optional[Any]:
      lowerCAmelCase__ :  Tuple							      =					[]
      lowerCAmelCase__ :  Dict							      =					[]
      if s == -2:
          lowerCAmelCase__ :  List[str]							      =					list(self.graph      )[0]
      stack.append(__UpperCAmelCase      )
      visited.append(__UpperCAmelCase      )
      lowerCAmelCase__ :  Optional[Any]							      =					s
      lowerCAmelCase__ :  Dict							      =					[]

      while True:
          # check if there is any non isolated nodes
          if len(self.graph[s]      ) != 0:
              lowerCAmelCase__ :  List[Any]							      =					s
              for node in self.graph[s]:
                  if visited.count(node[1]      ) < 1:
                      stack.append(node[1]      )
                      visited.append(node[1]      )
                      lowerCAmelCase__ :  Tuple							      =					node[1]
                      break

            # check if all the children are visited
          if s == ss:
              sorted_nodes.append(stack.pop()      )
              if len(__UpperCAmelCase      ) != 0:
                  lowerCAmelCase__ :  int							      =					stack[len(__UpperCAmelCase      ) - 1]
          else:
              lowerCAmelCase__ :  List[str]							      =					ss

          # check if se have reached the starting point
          if len(__UpperCAmelCase      ) == 0:
              return sorted_nodes




  def 							UpperCAmelCase_	(    self      )    ->		List[str]:
      lowerCAmelCase__ :  Union[str, Any]							      =					[]
      lowerCAmelCase__ :  List[str]							      =					[]
      lowerCAmelCase__ :  List[Any]							      =					list(self.graph      )[0]
      stack.append(__UpperCAmelCase      )
      visited.append(__UpperCAmelCase      )
      lowerCAmelCase__ :  Union[str, Any]							      =					-2
      lowerCAmelCase__ :  List[str]							      =					[]
      lowerCAmelCase__ :  Optional[int]							      =					s
      lowerCAmelCase__ :  Union[str, Any]							      =					False
      lowerCAmelCase__ :  Dict							      =					set()

      while True:
          # check if there is any non isolated nodes
          if len(self.graph[s]      ) != 0:
              lowerCAmelCase__ :  Union[str, Any]							      =					s
              for node in self.graph[s]:
                  if (
                      visited.count(node[1]      ) > 0
                      and node[1] != parent
                      and indirect_parents.count(node[1]      ) > 0
                      and not on_the_way_back
                  ):
                      lowerCAmelCase__ :  Any							      =					len(__UpperCAmelCase      ) - 1
                      while len_stack >= 0:
                          if stack[len_stack] == node[1]:
                              anticipating_nodes.add(node[1]      )
                              break
                          else:
                              anticipating_nodes.add(stack[len_stack]      )
                              len_stack -= 1
                  if visited.count(node[1]      ) < 1:
                      stack.append(node[1]      )
                      visited.append(node[1]      )
                      lowerCAmelCase__ :  Optional[int]							      =					node[1]
                      break

            # check if all the children are visited
          if s == ss:
              stack.pop()
              lowerCAmelCase__ :  Dict							      =					True
              if len(__UpperCAmelCase      ) != 0:
                  lowerCAmelCase__ :  Optional[int]							      =					stack[len(__UpperCAmelCase      ) - 1]
          else:
              lowerCAmelCase__ :  List[str]							      =					False
              indirect_parents.append(__UpperCAmelCase      )
              lowerCAmelCase__ :  Optional[int]							      =					s
              lowerCAmelCase__ :  Dict							      =					ss

          # check if se have reached the starting point
          if len(__UpperCAmelCase      ) == 0:
              return list(__UpperCAmelCase      )




  def 							UpperCAmelCase_	(    self      )    ->		Tuple:
      lowerCAmelCase__ :  Optional[int]							      =					[]
      lowerCAmelCase__ :  Tuple							      =					[]
      lowerCAmelCase__ :  Dict							      =					list(self.graph      )[0]
      stack.append(__UpperCAmelCase      )
      visited.append(__UpperCAmelCase      )
      lowerCAmelCase__ :  Tuple							      =					-2
      lowerCAmelCase__ :  Tuple							      =					[]
      lowerCAmelCase__ :  List[Any]							      =					s
      lowerCAmelCase__ :  str							      =					False
      lowerCAmelCase__ :  int							      =					set()

      while True:
          # check if there is any non isolated nodes
          if len(self.graph[s]      ) != 0:
              lowerCAmelCase__ :  Tuple							      =					s
              for node in self.graph[s]:
                  if (
                      visited.count(node[1]      ) > 0
                      and node[1] != parent
                      and indirect_parents.count(node[1]      ) > 0
                      and not on_the_way_back
                  ):
                      lowerCAmelCase__ :  List[str]							      =					len(__UpperCAmelCase      ) - 1
                      while len_stack_minus_one >= 0:
                          if stack[len_stack_minus_one] == node[1]:
                              anticipating_nodes.add(node[1]      )
                              break
                          else:
                              return True
                  if visited.count(node[1]      ) < 1:
                      stack.append(node[1]      )
                      visited.append(node[1]      )
                      lowerCAmelCase__ :  Union[str, Any]							      =					node[1]
                      break

            # check if all the children are visited
          if s == ss:
              stack.pop()
              lowerCAmelCase__ :  List[str]							      =					True
              if len(__UpperCAmelCase      ) != 0:
                  lowerCAmelCase__ :  Union[str, Any]							      =					stack[len(__UpperCAmelCase      ) - 1]
          else:
              lowerCAmelCase__ :  Optional[Any]							      =					False
              indirect_parents.append(__UpperCAmelCase      )
              lowerCAmelCase__ :  str							      =					s
              lowerCAmelCase__ :  List[str]							      =					ss

          # check if se have reached the starting point
          if len(__UpperCAmelCase      ) == 0:
              return False




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-2  ,__UpperCAmelCase=-1      )    ->		int:
      lowerCAmelCase__ :  Optional[Any]							      =					time()
      self.dfs(__UpperCAmelCase  ,__UpperCAmelCase      )
      lowerCAmelCase__ :  Dict							      =					time()
      return end - begin






  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-2      )    ->		Dict:
      lowerCAmelCase__ :  str							      =					time()
      self.bfs(__UpperCAmelCase      )
      lowerCAmelCase__ :  List[str]							      =					time()
      return end - begin







class        lowerCAmelCase_:
  '''simple docstring'''




  def __init__(    self      )    ->		Optional[int]:
      lowerCAmelCase__ :  int							      =					{}




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase  ,__UpperCAmelCase  ,__UpperCAmelCase=1      )    ->		Optional[int]:
      # check if the u exists
      if self.graph.get(__UpperCAmelCase      ):
          # if there already is a edge
          if self.graph[u].count([w, v]      ) == 0:
              self.graph[u].append([w, v]      )
      else:
          # if u does not exist
          lowerCAmelCase__ :  Tuple							      =					[[w, v]]
      # add the other way
      if self.graph.get(__UpperCAmelCase      ):
          # if there already is a edge
          if self.graph[v].count([w, u]      ) == 0:
              self.graph[v].append([w, u]      )
      else:
          # if u does not exist
          lowerCAmelCase__ :  List[Any]							      =					[[w, u]]




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase  ,__UpperCAmelCase      )    ->		Tuple:
      if self.graph.get(__UpperCAmelCase      ):
          for _ in self.graph[u]:
              if _[1] == v:
                  self.graph[u].remove(__UpperCAmelCase      )
        # the other way round
      if self.graph.get(__UpperCAmelCase      ):
          for _ in self.graph[v]:
              if _[1] == u:
                  self.graph[v].remove(__UpperCAmelCase      )




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-2  ,__UpperCAmelCase=-1      )    ->		List[str]:
      if s == d:
          return []
      lowerCAmelCase__ :  Union[str, Any]							      =					[]
      lowerCAmelCase__ :  Optional[int]							      =					[]
      if s == -2:
          lowerCAmelCase__ :  str							      =					list(self.graph      )[0]
      stack.append(__UpperCAmelCase      )
      visited.append(__UpperCAmelCase      )
      lowerCAmelCase__ :  Any							      =					s

      while True:
          # check if there is any non isolated nodes
          if len(self.graph[s]      ) != 0:
              lowerCAmelCase__ :  Optional[Any]							      =					s
              for node in self.graph[s]:
                  if visited.count(node[1]      ) < 1:
                      if node[1] == d:
                          visited.append(__UpperCAmelCase      )
                          return visited
                      else:
                          stack.append(node[1]      )
                          visited.append(node[1]      )
                          lowerCAmelCase__ :  List[str]							      =					node[1]
                          break

            # check if all the children are visited
          if s == ss:
              stack.pop()
              if len(__UpperCAmelCase      ) != 0:
                  lowerCAmelCase__ :  Optional[int]							      =					stack[len(__UpperCAmelCase      ) - 1]
          else:
              lowerCAmelCase__ :  Optional[Any]							      =					ss

          # check if se have reached the starting point
          if len(__UpperCAmelCase      ) == 0:
              return visited




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-1      )    ->		Dict:
      if c == -1:
          lowerCAmelCase__ :  Dict							      =					floor(random() * 1_0000      ) + 10
      for i in range(__UpperCAmelCase      ):
          # every vertex has max 100 edges
          for _ in range(floor(random() * 102      ) + 1      ):
              lowerCAmelCase__ :  Any							      =					floor(random() * c      ) + 1
              if n != i:
                  self.add_pair(__UpperCAmelCase  ,__UpperCAmelCase  ,1      )




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-2      )    ->		Tuple:
      lowerCAmelCase__ :  Dict							      =					deque()
      lowerCAmelCase__ :  Optional[int]							      =					[]
      if s == -2:
          lowerCAmelCase__ :  Optional[int]							      =					list(self.graph      )[0]
      d.append(__UpperCAmelCase      )
      visited.append(__UpperCAmelCase      )
      while d:
          lowerCAmelCase__ :  Any							      =					d.popleft()
          if len(self.graph[s]      ) != 0:
              for node in self.graph[s]:
                  if visited.count(node[1]      ) < 1:
                      d.append(node[1]      )
                      visited.append(node[1]      )
      return visited




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase      )    ->		str:
      return len(self.graph[u]      )




  def 							UpperCAmelCase_	(    self      )    ->		Any:
      lowerCAmelCase__ :  Dict							      =					[]
      lowerCAmelCase__ :  List[str]							      =					[]
      lowerCAmelCase__ :  Optional[int]							      =					list(self.graph      )[0]
      stack.append(__UpperCAmelCase      )
      visited.append(__UpperCAmelCase      )
      lowerCAmelCase__ :  int							      =					-2
      lowerCAmelCase__ :  int							      =					[]
      lowerCAmelCase__ :  List[str]							      =					s
      lowerCAmelCase__ :  Tuple							      =					False
      lowerCAmelCase__ :  Dict							      =					set()

      while True:
          # check if there is any non isolated nodes
          if len(self.graph[s]      ) != 0:
              lowerCAmelCase__ :  Union[str, Any]							      =					s
              for node in self.graph[s]:
                  if (
                      visited.count(node[1]      ) > 0
                      and node[1] != parent
                      and indirect_parents.count(node[1]      ) > 0
                      and not on_the_way_back
                  ):
                      lowerCAmelCase__ :  int							      =					len(__UpperCAmelCase      ) - 1
                      while len_stack >= 0:
                          if stack[len_stack] == node[1]:
                              anticipating_nodes.add(node[1]      )
                              break
                          else:
                              anticipating_nodes.add(stack[len_stack]      )
                              len_stack -= 1
                  if visited.count(node[1]      ) < 1:
                      stack.append(node[1]      )
                      visited.append(node[1]      )
                      lowerCAmelCase__ :  str							      =					node[1]
                      break

            # check if all the children are visited
          if s == ss:
              stack.pop()
              lowerCAmelCase__ :  Optional[Any]							      =					True
              if len(__UpperCAmelCase      ) != 0:
                  lowerCAmelCase__ :  Optional[Any]							      =					stack[len(__UpperCAmelCase      ) - 1]
          else:
              lowerCAmelCase__ :  int							      =					False
              indirect_parents.append(__UpperCAmelCase      )
              lowerCAmelCase__ :  List[str]							      =					s
              lowerCAmelCase__ :  List[str]							      =					ss

          # check if se have reached the starting point
          if len(__UpperCAmelCase      ) == 0:
              return list(__UpperCAmelCase      )




  def 							UpperCAmelCase_	(    self      )    ->		Dict:
      lowerCAmelCase__ :  Union[str, Any]							      =					[]
      lowerCAmelCase__ :  str							      =					[]
      lowerCAmelCase__ :  Optional[Any]							      =					list(self.graph      )[0]
      stack.append(__UpperCAmelCase      )
      visited.append(__UpperCAmelCase      )
      lowerCAmelCase__ :  Dict							      =					-2
      lowerCAmelCase__ :  Optional[Any]							      =					[]
      lowerCAmelCase__ :  Any							      =					s
      lowerCAmelCase__ :  Optional[int]							      =					False
      lowerCAmelCase__ :  Dict							      =					set()

      while True:
          # check if there is any non isolated nodes
          if len(self.graph[s]      ) != 0:
              lowerCAmelCase__ :  Optional[int]							      =					s
              for node in self.graph[s]:
                  if (
                      visited.count(node[1]      ) > 0
                      and node[1] != parent
                      and indirect_parents.count(node[1]      ) > 0
                      and not on_the_way_back
                  ):
                      lowerCAmelCase__ :  List[Any]							      =					len(__UpperCAmelCase      ) - 1
                      while len_stack_minus_one >= 0:
                          if stack[len_stack_minus_one] == node[1]:
                              anticipating_nodes.add(node[1]      )
                              break
                          else:
                              return True
                  if visited.count(node[1]      ) < 1:
                      stack.append(node[1]      )
                      visited.append(node[1]      )
                      lowerCAmelCase__ :  Tuple							      =					node[1]
                      break

            # check if all the children are visited
          if s == ss:
              stack.pop()
              lowerCAmelCase__ :  Optional[int]							      =					True
              if len(__UpperCAmelCase      ) != 0:
                  lowerCAmelCase__ :  str							      =					stack[len(__UpperCAmelCase      ) - 1]
          else:
              lowerCAmelCase__ :  Tuple							      =					False
              indirect_parents.append(__UpperCAmelCase      )
              lowerCAmelCase__ :  Union[str, Any]							      =					s
              lowerCAmelCase__ :  int							      =					ss

          # check if se have reached the starting point
          if len(__UpperCAmelCase      ) == 0:
              return False




  def 							UpperCAmelCase_	(    self      )    ->		str:
      return list(self.graph      )




  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-2  ,__UpperCAmelCase=-1      )    ->		List[str]:
      lowerCAmelCase__ :  Tuple							      =					time()
      self.dfs(__UpperCAmelCase  ,__UpperCAmelCase      )
      lowerCAmelCase__ :  int							      =					time()
      return end - begin






  def 							UpperCAmelCase_	(    self  ,__UpperCAmelCase=-2      )    ->		int:
      lowerCAmelCase__ :  Optional[int]							      =					time()
      self.bfs(__UpperCAmelCase      )
      lowerCAmelCase__ :  Any							      =					time()
      return end - begin







'''simple docstring'''





from __future__ import annotations

import math
from collections import Counter
from string import ascii_lowercase
def    _SCREAMING_SNAKE_CASE  (       UpperCamelCase			):



    """simple docstring"""





    lowerCAmelCase__      ,   lowerCAmelCase__ :  List[str]							      =					analyze_text(UpperCamelCase			)
    lowerCAmelCase__ :  Optional[int]							      =					list(""" """ + ascii_lowercase			)
    # what is our total sum of probabilities.
    lowerCAmelCase__ :  List[Any]							      =					sum(single_char_strings.values()			)

    # one length string
    lowerCAmelCase__ :  Optional[int]							      =					0
    # for each alpha we go in our dict and if it is in it we calculate entropy
    for ch in my_alphas:
        if ch in single_char_strings:
            lowerCAmelCase__ :  List[Any]							      =					single_char_strings[ch]
            lowerCAmelCase__ :  List[Any]							      =					my_str / all_sum
            my_fir_sum += prob * math.loga(UpperCamelCase			)  # entropy formula.

    # print entropy
    print(f"""{round(-1 * my_fir_sum			):.1f}"""			)

    # two len string
    lowerCAmelCase__ :  Dict							      =					sum(two_char_strings.values()			)
    lowerCAmelCase__ :  int							      =					0
    # for each alpha (two in size) calculate entropy.
    for cha in my_alphas:
        for cha in my_alphas:
            lowerCAmelCase__ :  Union[str, Any]							      =					cha + cha
            if sequence in two_char_strings:
                lowerCAmelCase__ :  Dict							      =					two_char_strings[sequence]
                lowerCAmelCase__ :  Tuple							      =					int(UpperCamelCase			) / all_sum
                my_sec_sum += prob * math.loga(UpperCamelCase			)

    # print second entropy
    print(f"""{round(-1 * my_sec_sum			):.1f}"""			)

    # print the difference between them
    print(f"""{round((-1 * my_sec_sum) - (-1 * my_fir_sum)			):.1f}"""			)
def    _SCREAMING_SNAKE_CASE  (       UpperCamelCase			):



    """simple docstring"""





    lowerCAmelCase__ :  Optional[Any]							      =					Counter()  # type: ignore
    lowerCAmelCase__ :  Tuple							      =					Counter()  # type: ignore
    single_char_strings[text[-1]] += 1

    # first case when we have space at start.
    two_char_strings[" " + text[0]] += 1
    for i in range(0							,    len(UpperCamelCase			) - 1			):
        single_char_strings[text[i]] += 1
        two_char_strings[text[i : i + 2]] += 1
    return single_char_strings, two_char_strings
def    _SCREAMING_SNAKE_CASE  (       ):



    """simple docstring"""





    import doctest

    doctest.testmod()
    # text = (
    #     "Had repulsive dashwoods suspicion sincerity but advantage now him. Remark "
    #     "easily garret nor nay. Civil those mrs enjoy shy fat merry. You greatest "
    #     "jointure saw horrible. He private he on be imagine suppose. Fertile "
    #     "beloved evident through no service elderly is. Blind there if every no so "
    #     "at. Own neglected you preferred way sincerity delivered his attempted. To "
    #     "of message cottage windows do besides against uncivil.  Delightful "
    #     "unreserved impossible few estimating men favourable see entreaties. She "
    #     "propriety immediate was improving. He or entrance humoured likewise "
    #     "moderate. Much nor game son say feel. Fat make met can must form into "
    #     "gate. Me we offending prevailed discovery. "
    # )

    # calculate_prob(text)


if __name__ == "__main__":
 main()


