





"""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'''



							snake_case_						:   Dict           =  {}






			def       lowerCamelCase  (self ,							__magic_name__ ,							__magic_name__ ,							__magic_name__=1   )					->       int:


							'''simple docstring'''



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






			def       lowerCamelCase  (self   )					->       Optional[int]:


							'''simple docstring'''



							return list(self.graph   )






			def       lowerCamelCase  (self ,							__magic_name__ ,							__magic_name__   )					->       int:


							'''simple docstring'''



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






			def       lowerCamelCase  (self ,							__magic_name__=-2 ,							__magic_name__=-1   )					->       Optional[int]:


							'''simple docstring'''



							if s == d:
											return []
							snake_case_						:   Tuple           =  []
							snake_case_						:   Optional[Any]           =  []
							if s == -2:
											snake_case_						:   Any           =  list(self.graph   )[0]
							stack.append(UpperCamelCase_   )
							visited.append(UpperCamelCase_   )
							snake_case_						:   Dict           =  s

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

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

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






			def       lowerCamelCase  (self ,							__magic_name__=-1   )					->       List[str]:


							'''simple docstring'''



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






			def       lowerCamelCase  (self ,							__magic_name__=-2   )					->       Tuple:


							'''simple docstring'''



							snake_case_						:   Tuple           =  deque()
							snake_case_						:   Optional[Any]           =  []
							if s == -2:
											snake_case_						:   List[Any]           =  list(self.graph   )[0]
							d.append(UpperCamelCase_   )
							visited.append(UpperCamelCase_   )
							while d:
											snake_case_						:   List[str]           =  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       lowerCamelCase  (self ,							__magic_name__   )					->       int:


							'''simple docstring'''



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






			def       lowerCamelCase  (self ,							__magic_name__   )					->       Optional[int]:


							'''simple docstring'''



							return len(self.graph[u]   )






			def       lowerCamelCase  (self ,							__magic_name__=-2   )					->       str:


							'''simple docstring'''



							snake_case_						:   Tuple           =  []
							snake_case_						:   Tuple           =  []
							if s == -2:
											snake_case_						:   Any           =  list(self.graph   )[0]
							stack.append(UpperCamelCase_   )
							visited.append(UpperCamelCase_   )
							snake_case_						:   Tuple           =  s
							snake_case_						:   Optional[Any]           =  []

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

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

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






			def       lowerCamelCase  (self   )					->       str:


							'''simple docstring'''



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

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

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

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






			def       lowerCamelCase  (self   )					->       int:


							'''simple docstring'''



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

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

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

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






			def       lowerCamelCase  (self ,							__magic_name__=-2 ,							__magic_name__=-1   )					->       Dict:


							'''simple docstring'''



							snake_case_						:   Optional[int]           =  time()
							self.dfs(UpperCamelCase_ ,							UpperCamelCase_   )
							snake_case_						:   Union[str, Any]           =  time()
							return end - begin






			def       lowerCamelCase  (self ,							__magic_name__=-2   )					->       Union[str, Any]:


							'''simple docstring'''



							snake_case_						:   Union[str, Any]           =  time()
							self.bfs(UpperCamelCase_   )
							snake_case_						:   str           =  time()
							return end - begin




class  __lowerCAmelCase	:






			def __init__(self   )					->       Union[str, Any]:


							'''simple docstring'''



							snake_case_						:   Optional[int]           =  {}






			def       lowerCamelCase  (self ,							__magic_name__ ,							__magic_name__ ,							__magic_name__=1   )					->       Optional[Any]:


							'''simple docstring'''



							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
											snake_case_						:   int           =  [[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
											snake_case_						:   List[str]           =  [[w, u]]






			def       lowerCamelCase  (self ,							__magic_name__ ,							__magic_name__   )					->       Union[str, Any]:


							'''simple docstring'''



							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       lowerCamelCase  (self ,							__magic_name__=-2 ,							__magic_name__=-1   )					->       Dict:


							'''simple docstring'''



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

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

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

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






			def       lowerCamelCase  (self ,							__magic_name__=-1   )					->       Any:


							'''simple docstring'''



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






			def       lowerCamelCase  (self ,							__magic_name__=-2   )					->       Any:


							'''simple docstring'''



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


							'''simple docstring'''



							return len(self.graph[u]   )






			def       lowerCamelCase  (self   )					->       Dict:


							'''simple docstring'''



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

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

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

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






			def       lowerCamelCase  (self   )					->       Optional[int]:


							'''simple docstring'''



							snake_case_						:   Any           =  []
							snake_case_						:   Any           =  []
							snake_case_						:   Any           =  list(self.graph   )[0]
							stack.append(UpperCamelCase_   )
							visited.append(UpperCamelCase_   )
							snake_case_						:   Tuple           =  -2
							snake_case_						:   Union[str, Any]           =  []
							snake_case_						:   int           =  s
							snake_case_						:   Union[str, Any]           =  False
							snake_case_						:   Any           =  set()

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

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

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






			def       lowerCamelCase  (self   )					->       Tuple:


							'''simple docstring'''



							return list(self.graph   )






			def       lowerCamelCase  (self ,							__magic_name__=-2 ,							__magic_name__=-1   )					->       Any:


							'''simple docstring'''



							snake_case_						:   List[str]           =  time()
							self.dfs(UpperCamelCase_ ,							UpperCamelCase_   )
							snake_case_						:   Tuple           =  time()
							return end - begin






			def       lowerCamelCase  (self ,							__magic_name__=-2   )					->       str:


							'''simple docstring'''



							snake_case_						:   Optional[int]           =  time()
							self.bfs(UpperCamelCase_   )
							snake_case_						:   List[str]           =  time()
							return end - begin







def 					lowerCamelCase_						(    _UpperCamelCase			)		->						int:






				"""simple docstring"""


				if not isinstance(_UpperCamelCase			,    _UpperCamelCase			):
								raise ValueError('''multiplicative_persistence() only accepts integral values'''			)
				if num < 0:
								raise ValueError('''multiplicative_persistence() does not accept negative values'''			)

				snake_case_						:   List[Any]           =  0
				snake_case_						:   Tuple           =  str(_UpperCamelCase			)

				while len(_UpperCamelCase			) != 1:
								snake_case_						:   Tuple           =  [int(_UpperCamelCase			) for i in num_string]

								snake_case_						:   Dict           =  1
								for i in range(0			,    len(_UpperCamelCase			)			):
												total *= numbers[i]

								snake_case_						:   str           =  str(_UpperCamelCase			)

								steps += 1
				return steps






def 					lowerCamelCase_						(    _UpperCamelCase			)		->						int:






				"""simple docstring"""


				if not isinstance(_UpperCamelCase			,    _UpperCamelCase			):
								raise ValueError('''additive_persistence() only accepts integral values'''			)
				if num < 0:
								raise ValueError('''additive_persistence() does not accept negative values'''			)

				snake_case_						:   Any           =  0
				snake_case_						:   Tuple           =  str(_UpperCamelCase			)

				while len(_UpperCamelCase			) != 1:
								snake_case_						:   List[str]           =  [int(_UpperCamelCase			) for i in num_string]

								snake_case_						:   Optional[int]           =  0
								for i in range(0			,    len(_UpperCamelCase			)			):
												total += numbers[i]

								snake_case_						:   Tuple           =  str(_UpperCamelCase			)

								steps += 1
				return steps


if __name__ == "__main__":
	import doctest

	doctest.testmod()
