


'''simple docstring'''
from collections import deque
from math import floor
from random import random
from time import time




class      lowerCamelCase_  :






      def __init__(   self							:       Tuple					):


          '''simple docstring'''


          UpperCAmelCase__     :						Dict						=							{}






      def lowercase_				(   self							:       Optional[int]		,		_A							:       Optional[int]		,		_A							:       str		,		_A							:       List[str]=1					):


          '''simple docstring'''


          if self.graph.get(_A					):
              if self.graph[u].count([w, v]					) == 0:
                  self.graph[u].append([w, v]					)
          else:
              UpperCAmelCase__     :						Tuple						=							[[w, v]]
          if not self.graph.get(_A					):
              UpperCAmelCase__     :						List[Any]						=							[]






      def lowercase_				(   self							:       Dict					):


          '''simple docstring'''


          return list(self.graph					)






      def lowercase_				(   self							:       int		,		_A							:       List[str]		,		_A							:       str					):


          '''simple docstring'''


          if self.graph.get(_A					):
              for _ in self.graph[u]:
                  if _[1] == v:
                      self.graph[u].remove(_A					)






      def lowercase_				(   self							:       Dict		,		_A							:       List[Any]=-2		,		_A							:       Optional[int]=-1					):


          '''simple docstring'''


          if s == d:
              return []
          UpperCAmelCase__     :						Union[str, Any]						=							[]
          UpperCAmelCase__     :						int						=							[]
          if s == -2:
              UpperCAmelCase__     :						Tuple						=							list(self.graph					)[0]
          stack.append(_A					)
          visited.append(_A					)
          UpperCAmelCase__     :						List[Any]						=							s

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

            # check if all the children are visited
              if s == ss:
                  stack.pop()
                  if len(_A					) != 0:
                      UpperCAmelCase__     :						Dict						=							stack[len(_A					) - 1]
              else:
                  UpperCAmelCase__     :						str						=							ss

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






      def lowercase_				(   self							:       Tuple		,		_A							:       int=-1					):


          '''simple docstring'''


          if c == -1:
              UpperCAmelCase__     :						Tuple						=							floor(random() * 10_000					) + 10
          for i in range(_A					):
              # every vertex has max 100 edges
              for _ in range(floor(random() * 102					) + 1					):
                  UpperCAmelCase__     :						Union[str, Any]						=							floor(random() * c					) + 1
                  if n != i:
                      self.add_pair(_A		,		_A		,		1					)






      def lowercase_				(   self							:       Tuple		,		_A							:       List[str]=-2					):


          '''simple docstring'''


          UpperCAmelCase__     :						int						=							deque()
          UpperCAmelCase__     :						Optional[int]						=							[]
          if s == -2:
              UpperCAmelCase__     :						Union[str, Any]						=							list(self.graph					)[0]
          d.append(_A					)
          visited.append(_A					)
          while d:
              UpperCAmelCase__     :						Dict						=							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 lowercase_				(   self							:       int		,		_A							:       Union[str, Any]					):


          '''simple docstring'''


          UpperCAmelCase__     :						List[str]						=							0
          for x in self.graph:
              for y in self.graph[x]:
                  if y[1] == u:
                      count += 1
          return count






      def lowercase_				(   self							:       Dict		,		_A							:       Union[str, Any]					):


          '''simple docstring'''


          return len(self.graph[u]					)






      def lowercase_				(   self							:       Dict		,		_A							:       Optional[Any]=-2					):


          '''simple docstring'''


          UpperCAmelCase__     :						Optional[Any]						=							[]
          UpperCAmelCase__     :						List[Any]						=							[]
          if s == -2:
              UpperCAmelCase__     :						List[str]						=							list(self.graph					)[0]
          stack.append(_A					)
          visited.append(_A					)
          UpperCAmelCase__     :						Any						=							s
          UpperCAmelCase__     :						Any						=							[]

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

            # check if all the children are visited
              if s == ss:
                  sorted_nodes.append(stack.pop()					)
                  if len(_A					) != 0:
                      UpperCAmelCase__     :						Union[str, Any]						=							stack[len(_A					) - 1]
              else:
                  UpperCAmelCase__     :						Union[str, Any]						=							ss

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






      def lowercase_				(   self							:       Optional[Any]					):


          '''simple docstring'''


          UpperCAmelCase__     :						Any						=							[]
          UpperCAmelCase__     :						List[str]						=							[]
          UpperCAmelCase__     :						Union[str, Any]						=							list(self.graph					)[0]
          stack.append(_A					)
          visited.append(_A					)
          UpperCAmelCase__     :						int						=							-2
          UpperCAmelCase__     :						List[str]						=							[]
          UpperCAmelCase__     :						Optional[int]						=							s
          UpperCAmelCase__     :						Any						=							False
          UpperCAmelCase__     :						int						=							set()

          while True:
              # check if there is any non isolated nodes
              if len(self.graph[s]					) != 0:
                  UpperCAmelCase__     :						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
                      ):
                          UpperCAmelCase__     :						Dict						=							len(_A					) - 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]					)
                          UpperCAmelCase__     :						Optional[int]						=							node[1]
                          break

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

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






      def lowercase_				(   self							:       Union[str, Any]					):


          '''simple docstring'''


          UpperCAmelCase__     :						Optional[Any]						=							[]
          UpperCAmelCase__     :						Tuple						=							[]
          UpperCAmelCase__     :						Dict						=							list(self.graph					)[0]
          stack.append(_A					)
          visited.append(_A					)
          UpperCAmelCase__     :						Union[str, Any]						=							-2
          UpperCAmelCase__     :						Optional[Any]						=							[]
          UpperCAmelCase__     :						List[Any]						=							s
          UpperCAmelCase__     :						str						=							False
          UpperCAmelCase__     :						str						=							set()

          while True:
              # check if there is any non isolated nodes
              if len(self.graph[s]					) != 0:
                  UpperCAmelCase__     :						str						=							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
                      ):
                          UpperCAmelCase__     :						List[str]						=							len(_A					) - 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]					)
                          UpperCAmelCase__     :						Optional[int]						=							node[1]
                          break

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

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






      def lowercase_				(   self							:       Dict		,		_A							:       Any=-2		,		_A							:       List[str]=-1					):


          '''simple docstring'''


          UpperCAmelCase__     :						Any						=							time()
          self.dfs(_A		,		_A					)
          UpperCAmelCase__     :						Union[str, Any]						=							time()
          return end - begin






      def lowercase_				(   self							:       Union[str, Any]		,		_A							:       Optional[int]=-2					):


          '''simple docstring'''


          UpperCAmelCase__     :						Dict						=							time()
          self.bfs(_A					)
          UpperCAmelCase__     :						Any						=							time()
          return end - begin




class      lowerCamelCase_  :






      def __init__(   self							:       List[str]					):


          '''simple docstring'''


          UpperCAmelCase__     :						Optional[int]						=							{}






      def lowercase_				(   self							:       List[Any]		,		_A							:       List[str]		,		_A							:       Optional[int]		,		_A							:       Any=1					):


          '''simple docstring'''


          if self.graph.get(_A					):
              # 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
              UpperCAmelCase__     :						Any						=							[[w, v]]
          # add the other way
          if self.graph.get(_A					):
              # 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
              UpperCAmelCase__     :						List[str]						=							[[w, u]]






      def lowercase_				(   self							:       Optional[Any]		,		_A							:       Optional[int]		,		_A							:       Dict					):


          '''simple docstring'''


          if self.graph.get(_A					):
              for _ in self.graph[u]:
                  if _[1] == v:
                      self.graph[u].remove(_A					)
        # the other way round
          if self.graph.get(_A					):
              for _ in self.graph[v]:
                  if _[1] == u:
                      self.graph[v].remove(_A					)






      def lowercase_				(   self							:       Optional[Any]		,		_A							:       int=-2		,		_A							:       Optional[int]=-1					):


          '''simple docstring'''


          if s == d:
              return []
          UpperCAmelCase__     :						int						=							[]
          UpperCAmelCase__     :						Dict						=							[]
          if s == -2:
              UpperCAmelCase__     :						Optional[Any]						=							list(self.graph					)[0]
          stack.append(_A					)
          visited.append(_A					)
          UpperCAmelCase__     :						Optional[Any]						=							s

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

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

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






      def lowercase_				(   self							:       str		,		_A							:       Tuple=-1					):


          '''simple docstring'''


          if c == -1:
              UpperCAmelCase__     :						str						=							floor(random() * 10_000					) + 10
          for i in range(_A					):
              # every vertex has max 100 edges
              for _ in range(floor(random() * 102					) + 1					):
                  UpperCAmelCase__     :						List[str]						=							floor(random() * c					) + 1
                  if n != i:
                      self.add_pair(_A		,		_A		,		1					)






      def lowercase_				(   self							:       Tuple		,		_A							:       List[str]=-2					):


          '''simple docstring'''


          UpperCAmelCase__     :						Optional[Any]						=							deque()
          UpperCAmelCase__     :						Optional[int]						=							[]
          if s == -2:
              UpperCAmelCase__     :						int						=							list(self.graph					)[0]
          d.append(_A					)
          visited.append(_A					)
          while d:
              UpperCAmelCase__     :						Dict						=							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 lowercase_				(   self							:       Tuple		,		_A							:       int					):


          '''simple docstring'''


          return len(self.graph[u]					)






      def lowercase_				(   self							:       str					):


          '''simple docstring'''


          UpperCAmelCase__     :						Dict						=							[]
          UpperCAmelCase__     :						str						=							[]
          UpperCAmelCase__     :						Any						=							list(self.graph					)[0]
          stack.append(_A					)
          visited.append(_A					)
          UpperCAmelCase__     :						Union[str, Any]						=							-2
          UpperCAmelCase__     :						Union[str, Any]						=							[]
          UpperCAmelCase__     :						List[Any]						=							s
          UpperCAmelCase__     :						Any						=							False
          UpperCAmelCase__     :						Any						=							set()

          while True:
              # check if there is any non isolated nodes
              if len(self.graph[s]					) != 0:
                  UpperCAmelCase__     :						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
                      ):
                          UpperCAmelCase__     :						Tuple						=							len(_A					) - 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]					)
                          UpperCAmelCase__     :						Any						=							node[1]
                          break

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

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






      def lowercase_				(   self							:       str					):


          '''simple docstring'''


          UpperCAmelCase__     :						List[Any]						=							[]
          UpperCAmelCase__     :						str						=							[]
          UpperCAmelCase__     :						Any						=							list(self.graph					)[0]
          stack.append(_A					)
          visited.append(_A					)
          UpperCAmelCase__     :						Dict						=							-2
          UpperCAmelCase__     :						Optional[int]						=							[]
          UpperCAmelCase__     :						Optional[Any]						=							s
          UpperCAmelCase__     :						Optional[Any]						=							False
          UpperCAmelCase__     :						Union[str, Any]						=							set()

          while True:
              # check if there is any non isolated nodes
              if len(self.graph[s]					) != 0:
                  UpperCAmelCase__     :						List[str]						=							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
                      ):
                          UpperCAmelCase__     :						Union[str, Any]						=							len(_A					) - 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]					)
                          UpperCAmelCase__     :						Any						=							node[1]
                          break

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

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






      def lowercase_				(   self							:       int					):


          '''simple docstring'''


          return list(self.graph					)






      def lowercase_				(   self							:       List[Any]		,		_A							:       Any=-2		,		_A							:       List[str]=-1					):


          '''simple docstring'''


          UpperCAmelCase__     :						Union[str, Any]						=							time()
          self.dfs(_A		,		_A					)
          UpperCAmelCase__     :						Tuple						=							time()
          return end - begin






      def lowercase_				(   self							:       int		,		_A							:       str=-2					):


          '''simple docstring'''


          UpperCAmelCase__     :						Tuple						=							time()
          self.bfs(_A					)
          UpperCAmelCase__     :						int						=							time()
          return end - begin




'''simple docstring'''





class 				UpperCAmelCase			:


 def __init__(      self							:	Union[str, Any] ):
    UpperCAmelCase__	:dict[str, TrieNode]      =      {}  # Mapping from char to TrieNode
    UpperCAmelCase__	:Union[str, Any]      =      False


 def        __SCREAMING_SNAKE_CASE					(      self							:	Optional[int]			,       __lowerCamelCase							:	list[str] ):
    for word in words:
       self.insert(__lowerCamelCase )


 def        __SCREAMING_SNAKE_CASE					(      self							:	Dict			,       __lowerCamelCase							:	str ):
    UpperCAmelCase__	:Tuple      =      self
    for char in word:
       if char not in curr.nodes:
          UpperCAmelCase__	:Optional[int]      =      TrieNode()
       UpperCAmelCase__	:Dict      =      curr.nodes[char]
    UpperCAmelCase__	:Optional[int]      =      True


 def        __SCREAMING_SNAKE_CASE					(      self							:	Any			,       __lowerCamelCase							:	str ):
    UpperCAmelCase__	:str      =      self
    for char in word:
       if char not in curr.nodes:
          return False
       UpperCAmelCase__	:Dict      =      curr.nodes[char]
    return curr.is_leaf





 def        __SCREAMING_SNAKE_CASE					(      self							:	Optional[Any]			,       __lowerCamelCase							:	str ):

    def _delete(__lowerCamelCase							:	TrieNode			,       __lowerCamelCase							:	str			,       __lowerCamelCase							:	int ) -> bool:
       if index == len(__lowerCamelCase ):
          # If word does not exist
          if not curr.is_leaf:
             return False
          UpperCAmelCase__	:int      =      False
          return len(curr.nodes ) == 0
       UpperCAmelCase__	:str      =      word[index]
       UpperCAmelCase__	:Optional[Any]      =      curr.nodes.get(__lowerCamelCase )
       # If char not in current trie node
       if not char_node:
          return False
       # Flag to check if node can be deleted
       UpperCAmelCase__	:Any      =      _delete(__lowerCamelCase			,       __lowerCamelCase			,       index + 1 )
       if delete_curr:
          del curr.nodes[char]
          return len(curr.nodes ) == 0
       return delete_curr

    _delete(self			,       __lowerCamelCase			,       0 )


def        a__     (					UpperCamelCase_						:      TrieNode,   UpperCamelCase_						:      str						):
   if node.is_leaf:
      print(UpperCamelCase_,   end=''' '''						)

   for key, value in node.nodes.items():
      print_words(UpperCamelCase_,   word + key						)


def        a__     (					):
   UpperCAmelCase__	:Union[str, Any]      =      '''banana bananas bandana band apple all beast'''.split()
   UpperCAmelCase__	:Union[str, Any]      =      TrieNode()
   root.insert_many(UpperCamelCase_						)
   # print_words(root, "")
   assert all(root.find(UpperCamelCase_						) for word in words						)
   assert root.find('''banana'''						)
   assert not root.find('''bandanas'''						)
   assert not root.find('''apps'''						)
   assert root.find('''apple'''						)
   assert root.find('''all'''						)
   root.delete('''all'''						)
   assert not root.find('''all'''						)
   root.delete('''banana'''						)
   assert not root.find('''banana'''						)
   assert root.find('''bananas'''						)
   return True


def        a__     (					UpperCamelCase_						:      str,   UpperCamelCase_						:      bool						):
   print(str(UpperCamelCase_						),   '''works!''' if passes else '''doesn\'t work :('''						)


def        a__     (					):
   assert test_trie()


def        a__     (					):
   print_results('''Testing trie functionality''',   test_trie()						)


if __name__ == "__main__":
    main()



