




from collections import deque
from math import floor
from random import random
from time import time
class 		UpperCAmelCase   :







						'''simple docstring'''





						def __init__(						self							:     str						):






							"""simple docstring"""






							snake_case_		    =     {}






						def        snake_case__						(						self							:     List[str]       ,	__lowercase							:     List[Any]       ,	__lowercase							:     Tuple       ,	__lowercase							:     Optional[int]=1						):






							"""simple docstring"""






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






						def        snake_case__						(						self							:     List[Any]						):






							"""simple docstring"""






							return list(self.graph						)






						def        snake_case__						(						self							:     List[Any]       ,	__lowercase							:     Tuple       ,	__lowercase							:     Union[str, Any]						):






							"""simple docstring"""






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






						def        snake_case__						(						self							:     Union[str, Any]       ,	__lowercase							:     str=-2       ,	__lowercase							:     Optional[int]=-1						):






							"""simple docstring"""






							if s == d:
								return []
							snake_case_		    =     []
							snake_case_		    =     []
							if s == -2:
								snake_case_		    =     list(self.graph						)[0]
							stack.append(__lowercase						)
							visited.append(__lowercase						)
							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(__lowercase						)
												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(__lowercase						) != 0:
										snake_case_		    =     stack[len(__lowercase						) - 1]
								else:
									snake_case_		    =     ss

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






						def        snake_case__						(						self							:     List[str]       ,	__lowercase							:     Any=-1						):






							"""simple docstring"""






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






						def        snake_case__						(						self							:     Dict       ,	__lowercase							:     Union[str, Any]=-2						):






							"""simple docstring"""






							snake_case_		    =     deque()
							snake_case_		    =     []
							if s == -2:
								snake_case_		    =     list(self.graph						)[0]
							d.append(__lowercase						)
							visited.append(__lowercase						)
							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        snake_case__						(						self							:     List[str]       ,	__lowercase							:     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        snake_case__						(						self							:     Union[str, Any]       ,	__lowercase							:     str						):






							"""simple docstring"""






							return len(self.graph[u]						)






						def        snake_case__						(						self							:     List[str]       ,	__lowercase							:     List[str]=-2						):






							"""simple docstring"""






							snake_case_		    =     []
							snake_case_		    =     []
							if s == -2:
								snake_case_		    =     list(self.graph						)[0]
							stack.append(__lowercase						)
							visited.append(__lowercase						)
							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(__lowercase						) != 0:
										snake_case_		    =     stack[len(__lowercase						) - 1]
								else:
									snake_case_		    =     ss

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






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






							"""simple docstring"""






							snake_case_		    =     []
							snake_case_		    =     []
							snake_case_		    =     list(self.graph						)[0]
							stack.append(__lowercase						)
							visited.append(__lowercase						)
							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(__lowercase						) - 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(__lowercase						) != 0:
										snake_case_		    =     stack[len(__lowercase						) - 1]
								else:
									snake_case_		    =     False
									indirect_parents.append(__lowercase						)
									snake_case_		    =     s
									snake_case_		    =     ss

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






						def        snake_case__						(						self							:     int						):






							"""simple docstring"""






							snake_case_		    =     []
							snake_case_		    =     []
							snake_case_		    =     list(self.graph						)[0]
							stack.append(__lowercase						)
							visited.append(__lowercase						)
							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(__lowercase						) - 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(__lowercase						) != 0:
										snake_case_		    =     stack[len(__lowercase						) - 1]
								else:
									snake_case_		    =     False
									indirect_parents.append(__lowercase						)
									snake_case_		    =     s
									snake_case_		    =     ss

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






						def        snake_case__						(						self							:     Tuple       ,	__lowercase							:     Tuple=-2       ,	__lowercase							:     Union[str, Any]=-1						):






							"""simple docstring"""






							snake_case_		    =     time()
							self.dfs(__lowercase       ,	__lowercase						)
							snake_case_		    =     time()
							return end - begin






						def        snake_case__						(						self							:     Optional[Any]       ,	__lowercase							:     List[Any]=-2						):






							"""simple docstring"""






							snake_case_		    =     time()
							self.bfs(__lowercase						)
							snake_case_		    =     time()
							return end - begin







class 		UpperCAmelCase   :







						'''simple docstring'''





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






							"""simple docstring"""






							snake_case_		    =     {}






						def        snake_case__						(						self							:     List[Any]       ,	__lowercase							:     int       ,	__lowercase							:     str       ,	__lowercase							:     Optional[Any]=1						):






							"""simple docstring"""






							if self.graph.get(__lowercase						):
								# 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(__lowercase						):
								# 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        snake_case__						(						self							:     Union[str, Any]       ,	__lowercase							:     List[str]       ,	__lowercase							:     List[Any]						):






							"""simple docstring"""






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






						def        snake_case__						(						self							:     List[Any]       ,	__lowercase							:     List[str]=-2       ,	__lowercase							:     Tuple=-1						):






							"""simple docstring"""






							if s == d:
								return []
							snake_case_		    =     []
							snake_case_		    =     []
							if s == -2:
								snake_case_		    =     list(self.graph						)[0]
							stack.append(__lowercase						)
							visited.append(__lowercase						)
							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(__lowercase						)
												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(__lowercase						) != 0:
										snake_case_		    =     stack[len(__lowercase						) - 1]
								else:
									snake_case_		    =     ss

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






						def        snake_case__						(						self							:     str       ,	__lowercase							:     Dict=-1						):






							"""simple docstring"""






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






						def        snake_case__						(						self							:     Union[str, Any]       ,	__lowercase							:     Any=-2						):






							"""simple docstring"""






							snake_case_		    =     deque()
							snake_case_		    =     []
							if s == -2:
								snake_case_		    =     list(self.graph						)[0]
							d.append(__lowercase						)
							visited.append(__lowercase						)
							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        snake_case__						(						self							:     str       ,	__lowercase							:     List[str]						):






							"""simple docstring"""






							return len(self.graph[u]						)






						def        snake_case__						(						self							:     Tuple						):






							"""simple docstring"""






							snake_case_		    =     []
							snake_case_		    =     []
							snake_case_		    =     list(self.graph						)[0]
							stack.append(__lowercase						)
							visited.append(__lowercase						)
							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(__lowercase						) - 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(__lowercase						) != 0:
										snake_case_		    =     stack[len(__lowercase						) - 1]
								else:
									snake_case_		    =     False
									indirect_parents.append(__lowercase						)
									snake_case_		    =     s
									snake_case_		    =     ss

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






						def        snake_case__						(						self							:     Any						):






							"""simple docstring"""






							snake_case_		    =     []
							snake_case_		    =     []
							snake_case_		    =     list(self.graph						)[0]
							stack.append(__lowercase						)
							visited.append(__lowercase						)
							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(__lowercase						) - 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(__lowercase						) != 0:
										snake_case_		    =     stack[len(__lowercase						) - 1]
								else:
									snake_case_		    =     False
									indirect_parents.append(__lowercase						)
									snake_case_		    =     s
									snake_case_		    =     ss

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






						def        snake_case__						(						self							:     Tuple						):






							"""simple docstring"""






							return list(self.graph						)






						def        snake_case__						(						self							:     int       ,	__lowercase							:     Optional[Any]=-2       ,	__lowercase							:     Dict=-1						):






							"""simple docstring"""






							snake_case_		    =     time()
							self.dfs(__lowercase       ,	__lowercase						)
							snake_case_		    =     time()
							return end - begin






						def        snake_case__						(						self							:     Optional[int]       ,	__lowercase							:     List[Any]=-2						):






							"""simple docstring"""






							snake_case_		    =     time()
							self.bfs(__lowercase						)
							snake_case_		    =     time()
							return end - begin






def 						lowerCamelCase__    (		):







	'''simple docstring'''





	snake_case_		    =     []
	snake_case_		    =     1

	while len(_A							) < 1E6:
		constant.append(str(_A							)							)
		i += 1

	snake_case_		    =     "".join(_A							)

	return (
	    int(constant[0]							)
	    * int(constant[9]							)
	    * int(constant[99]							)
	    * int(constant[999]							)
	    * int(constant[9999]							)
	    * int(constant[99999]							)
	    * int(constant[999999]							)
	)


if __name__ == "__main__":
		print(solution())
