





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

class 						SCREAMING_SNAKE_CASE__							:


      def __init__(self			: Optional[int] ):





         """simple docstring"""



         __snake_case							=  {}


      def   a					(self			: Any							,     a__			: Dict							,     a__			: str							,     a__			: Dict=1 ):





         """simple docstring"""



         if self.graph.get(SCREAMING_SNAKE_CASE__ ):
            if self.graph[u].count([w, v] ) == 0:
               self.graph[u].append([w, v] )
         else:
            __snake_case							=  [[w, v]]
         if not self.graph.get(SCREAMING_SNAKE_CASE__ ):
            __snake_case							=  []


      def   a					(self			: str ):





         """simple docstring"""



         return list(self.graph )


      def   a					(self			: Any							,     a__			: Dict							,     a__			: Optional[Any] ):





         """simple docstring"""



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


      def   a					(self			: int							,     a__			: Any=-2							,     a__			: List[str]=-1 ):





         """simple docstring"""



         if s == d:
            return []
         __snake_case							=  []
         __snake_case							=  []
         if s == -2:
            __snake_case							=  list(self.graph )[0]
         stack.append(SCREAMING_SNAKE_CASE__ )
         visited.append(SCREAMING_SNAKE_CASE__ )
         __snake_case							=  s

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

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

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


      def   a					(self			: Dict							,     a__			: Optional[Any]=-1 ):





         """simple docstring"""



         if c == -1:
            __snake_case							=  floor(random() * 1_0000 ) + 10
         for i in range(SCREAMING_SNAKE_CASE__ ):
            # every vertex has max 100 edges
            for _ in range(floor(random() * 102 ) + 1 ):
               __snake_case							=  floor(random() * c ) + 1
               if n != i:
                  self.add_pair(SCREAMING_SNAKE_CASE__							,     SCREAMING_SNAKE_CASE__							,     1 )


      def   a					(self			: Optional[Any]							,     a__			: int=-2 ):





         """simple docstring"""



         __snake_case							=  deque()
         __snake_case							=  []
         if s == -2:
            __snake_case							=  list(self.graph )[0]
         d.append(SCREAMING_SNAKE_CASE__ )
         visited.append(SCREAMING_SNAKE_CASE__ )
         while d:
            __snake_case							=  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   a					(self			: List[str]							,     a__			: List[Any] ):





         """simple docstring"""



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


      def   a					(self			: Tuple							,     a__			: str ):





         """simple docstring"""



         return len(self.graph[u] )


      def   a					(self			: Tuple							,     a__			: int=-2 ):





         """simple docstring"""



         __snake_case							=  []
         __snake_case							=  []
         if s == -2:
            __snake_case							=  list(self.graph )[0]
         stack.append(SCREAMING_SNAKE_CASE__ )
         visited.append(SCREAMING_SNAKE_CASE__ )
         __snake_case							=  s
         __snake_case							=  []

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

            # check if all the children are visited
            if s == ss:
               sorted_nodes.append(stack.pop() )
               if len(SCREAMING_SNAKE_CASE__ ) != 0:
                  __snake_case							=  stack[len(SCREAMING_SNAKE_CASE__ ) - 1]
            else:
               __snake_case							=  ss

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


      def   a					(self			: Dict ):





         """simple docstring"""



         __snake_case							=  []
         __snake_case							=  []
         __snake_case							=  list(self.graph )[0]
         stack.append(SCREAMING_SNAKE_CASE__ )
         visited.append(SCREAMING_SNAKE_CASE__ )
         __snake_case							=  -2
         __snake_case							=  []
         __snake_case							=  s
         __snake_case							=  False
         __snake_case							=  set()

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

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

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


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





         """simple docstring"""



         __snake_case							=  []
         __snake_case							=  []
         __snake_case							=  list(self.graph )[0]
         stack.append(SCREAMING_SNAKE_CASE__ )
         visited.append(SCREAMING_SNAKE_CASE__ )
         __snake_case							=  -2
         __snake_case							=  []
         __snake_case							=  s
         __snake_case							=  False
         __snake_case							=  set()

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

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

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


      def   a					(self			: Union[str, Any]							,     a__			: Any=-2							,     a__			: List[str]=-1 ):





         """simple docstring"""



         __snake_case							=  time()
         self.dfs(SCREAMING_SNAKE_CASE__							,     SCREAMING_SNAKE_CASE__ )
         __snake_case							=  time()
         return end - begin


      def   a					(self			: List[str]							,     a__			: str=-2 ):





         """simple docstring"""



         __snake_case							=  time()
         self.bfs(SCREAMING_SNAKE_CASE__ )
         __snake_case							=  time()
         return end - begin






class 						SCREAMING_SNAKE_CASE__							:


      def __init__(self			: Optional[int] ):





         """simple docstring"""



         __snake_case							=  {}


      def   a					(self			: List[str]							,     a__			: Optional[Any]							,     a__			: Optional[Any]							,     a__			: Any=1 ):





         """simple docstring"""



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


      def   a					(self			: Tuple							,     a__			: List[str]							,     a__			: Any ):





         """simple docstring"""



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


      def   a					(self			: List[Any]							,     a__			: Tuple=-2							,     a__			: Dict=-1 ):





         """simple docstring"""



         if s == d:
            return []
         __snake_case							=  []
         __snake_case							=  []
         if s == -2:
            __snake_case							=  list(self.graph )[0]
         stack.append(SCREAMING_SNAKE_CASE__ )
         visited.append(SCREAMING_SNAKE_CASE__ )
         __snake_case							=  s

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

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

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


      def   a					(self			: Union[str, Any]							,     a__			: Dict=-1 ):





         """simple docstring"""



         if c == -1:
            __snake_case							=  floor(random() * 1_0000 ) + 10
         for i in range(SCREAMING_SNAKE_CASE__ ):
            # every vertex has max 100 edges
            for _ in range(floor(random() * 102 ) + 1 ):
               __snake_case							=  floor(random() * c ) + 1
               if n != i:
                  self.add_pair(SCREAMING_SNAKE_CASE__							,     SCREAMING_SNAKE_CASE__							,     1 )


      def   a					(self			: List[str]							,     a__			: Dict=-2 ):





         """simple docstring"""



         __snake_case							=  deque()
         __snake_case							=  []
         if s == -2:
            __snake_case							=  list(self.graph )[0]
         d.append(SCREAMING_SNAKE_CASE__ )
         visited.append(SCREAMING_SNAKE_CASE__ )
         while d:
            __snake_case							=  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   a					(self			: Optional[Any]							,     a__			: Dict ):





         """simple docstring"""



         return len(self.graph[u] )


      def   a					(self			: Tuple ):





         """simple docstring"""



         __snake_case							=  []
         __snake_case							=  []
         __snake_case							=  list(self.graph )[0]
         stack.append(SCREAMING_SNAKE_CASE__ )
         visited.append(SCREAMING_SNAKE_CASE__ )
         __snake_case							=  -2
         __snake_case							=  []
         __snake_case							=  s
         __snake_case							=  False
         __snake_case							=  set()

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

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

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


      def   a					(self			: int ):





         """simple docstring"""



         __snake_case							=  []
         __snake_case							=  []
         __snake_case							=  list(self.graph )[0]
         stack.append(SCREAMING_SNAKE_CASE__ )
         visited.append(SCREAMING_SNAKE_CASE__ )
         __snake_case							=  -2
         __snake_case							=  []
         __snake_case							=  s
         __snake_case							=  False
         __snake_case							=  set()

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

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

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


      def   a					(self			: Tuple ):





         """simple docstring"""



         return list(self.graph )


      def   a					(self			: List[str]							,     a__			: str=-2							,     a__			: Dict=-1 ):





         """simple docstring"""



         __snake_case							=  time()
         self.dfs(SCREAMING_SNAKE_CASE__							,     SCREAMING_SNAKE_CASE__ )
         __snake_case							=  time()
         return end - begin


      def   a					(self			: str							,     a__			: str=-2 ):





         """simple docstring"""



         __snake_case							=  time()
         self.bfs(SCREAMING_SNAKE_CASE__ )
         __snake_case							=  time()
         return end - begin






"""simple docstring"""







class       UpperCamelCase__			:

			"""simple docstring"""


			def __init__(      self						,	SCREAMING_SNAKE_CASE__ = ""						,	SCREAMING_SNAKE_CASE__ = False		)      ->	None:
				# Mapping from the first character of the prefix of the node
				A__											=					{}

				# A node will be a leaf if the tree contains its word
				A__											=					is_leaf

				A__											=					prefix


			def   snake_case__	(      self						,	SCREAMING_SNAKE_CASE__		)      ->	tuple[str, str, str]:
				A__											=					0
				for q, w in zip(self.prefix						,	SCREAMING_SNAKE_CASE__		):
					if q != w:
						break

					x += 1

				return self.prefix[:x], self.prefix[x:], word[x:]


			def   snake_case__	(      self						,	SCREAMING_SNAKE_CASE__		)      ->	None:
				for word in words:
					self.insert(SCREAMING_SNAKE_CASE__		)


			def   snake_case__	(      self						,	SCREAMING_SNAKE_CASE__		)      ->	None:
				# Case 1: If the word is the prefix of the node
				# Solution: We set the current node as leaf
				if self.prefix == word:
					A__											=					True

				# Case 2: The node has no edges that have a prefix to the word
				# Solution: We create an edge from the current node to a new one
				# containing the word
				elif word[0] not in self.nodes:
					A__											=					RadixNode(prefix=SCREAMING_SNAKE_CASE__						,	is_leaf=SCREAMING_SNAKE_CASE__		)

				else:
					A__											=					self.nodes[word[0]]
					A__							,							A__							,							A__											=					incoming_node.match(
					    SCREAMING_SNAKE_CASE__		)

					# Case 3: The node prefix is equal to the matching
					# Solution: We insert remaining word on the next node
					if remaining_prefix == "":
						self.nodes[matching_string[0]].insert(SCREAMING_SNAKE_CASE__		)

					# Case 4: The word is greater equal to the matching
					# Solution: Create a node in between both nodes, change
					# prefixes and add the new node for the remaining word
					else:
						A__											=					remaining_prefix

						A__											=					self.nodes[matching_string[0]]
						A__											=					RadixNode(SCREAMING_SNAKE_CASE__						,	SCREAMING_SNAKE_CASE__		)
						A__											=					aux_node

						if remaining_word == "":
							A__											=					True
						else:
							self.nodes[matching_string[0]].insert(SCREAMING_SNAKE_CASE__		)


			def   snake_case__	(      self						,	SCREAMING_SNAKE_CASE__		)      ->	bool:
				A__											=					self.nodes.get(word[0]						,	SCREAMING_SNAKE_CASE__		)
				if not incoming_node:
					return False
				else:
					A__							,							A__							,							A__											=					incoming_node.match(
					    SCREAMING_SNAKE_CASE__		)
					# If there is remaining prefix, the word can't be on the tree
					if remaining_prefix != "":
						return False
					# This applies when the word and the prefix are equal
					elif remaining_word == "":
						return incoming_node.is_leaf
					# We have word remaining so we check the next node
					else:
						return incoming_node.find(SCREAMING_SNAKE_CASE__		)


			def   snake_case__	(      self						,	SCREAMING_SNAKE_CASE__		)      ->	bool:
				A__											=					self.nodes.get(word[0]						,	SCREAMING_SNAKE_CASE__		)
				if not incoming_node:
					return False
				else:
					A__							,							A__							,							A__											=					incoming_node.match(
					    SCREAMING_SNAKE_CASE__		)
					# If there is remaining prefix, the word can't be on the tree
					if remaining_prefix != "":
						return False
					# We have word remaining so we check the next node
					elif remaining_word != "":
						return incoming_node.delete(SCREAMING_SNAKE_CASE__		)
					else:
						# If it is not a leaf, we don't have to delete
						if not incoming_node.is_leaf:
							return False
						else:
							# We delete the nodes if no edges go from it
							if len(incoming_node.nodes		) == 0:
								del self.nodes[word[0]]
								# We merge the current node with its only child
								if len(self.nodes		) == 1 and not self.is_leaf:
									A__											=					list(self.nodes.values()		)[0]
									A__											=					merging_node.is_leaf
									self.prefix += merging_node.prefix
									A__											=					merging_node.nodes
                    # If there is more than 1 edge, we just mark it as non-leaf
							elif len(incoming_node.nodes		) > 1:
								A__											=					False
							# If there is 1 edge, we merge it with its child
							else:
								A__											=					list(incoming_node.nodes.values()		)[0]
								A__											=					merging_node.is_leaf
								incoming_node.prefix += merging_node.prefix
								A__											=					merging_node.nodes

							return True







			def   snake_case__	(      self						,	SCREAMING_SNAKE_CASE__ = 0		)      ->	None:
				if self.prefix != "":
					print("-" * height						,	self.prefix						,	"  (leaf)" if self.is_leaf else ""		)

				for value in self.nodes.values():
					value.print_tree(height + 1		)



def       _lowerCamelCase				(							)	-> bool:






	"""simple docstring"""





	A__											=					"banana bananas bandana band apple all beast".split()
	A__											=					RadixNode()
	root.insert_many(UpperCAmelCase_     )

	assert all(root.find(UpperCAmelCase_     ) for word in words     )
	assert not root.find("bandanas"     )
	assert not root.find("apps"     )
	root.delete("all"     )
	assert not root.find("all"     )
	root.delete("banana"     )
	assert not root.find("banana"     )
	assert root.find("bananas"     )

	return True

def       _lowerCamelCase				(							)	-> None:






	"""simple docstring"""





	assert test_trie()

def       _lowerCamelCase				(							)	-> None:






	"""simple docstring"""





	A__											=					RadixNode()
	A__											=					"banana bananas bandanas bandana band apple all beast".split()
	root.insert_many(UpperCAmelCase_     )

	print("Words:",	UpperCAmelCase_     )
	print("Tree:"     )
	root.print_tree()


if __name__ == "__main__":
			main()




