

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






class 	__magic_name__    :





			def __init__(		self					)   -> str:




						'''simple docstring'''
						__a        ={}





			def 		__magic_name__    (		self					,  __snake_case					,  __snake_case					,  __snake_case=1					)   -> str:




						'''simple docstring'''
						if self.graph.get(lowerCamelCase__					):
									if self.graph[u].count([w, v]					) == 0:
												self.graph[u].append([w, v]					)
						else:
									__a        =[[w, v]]
						if not self.graph.get(lowerCamelCase__					):
									__a        =[]





			def 		__magic_name__    (		self					)   -> Any:




						'''simple docstring'''
						return list(self.graph					)





			def 		__magic_name__    (		self					,  __snake_case					,  __snake_case					)   -> Any:




						'''simple docstring'''
						if self.graph.get(lowerCamelCase__					):
									for _ in self.graph[u]:
												if _[1] == v:
															self.graph[u].remove(lowerCamelCase__					)





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




						'''simple docstring'''
						if s == d:
									return []
						__a        =[]
						__a        =[]
						if s == -2:
									__a        =list(self.graph					)[0]
						stack.append(lowerCamelCase__					)
						visited.append(lowerCamelCase__					)
						__a        =s

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

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

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





			def 		__magic_name__    (		self					,  __snake_case=-1					)   -> Tuple:




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





			def 		__magic_name__    (		self					,  __snake_case=-2					)   -> Optional[Any]:




						'''simple docstring'''
						__a        =deque()
						__a        =[]
						if s == -2:
									__a        =list(self.graph					)[0]
						d.append(lowerCamelCase__					)
						visited.append(lowerCamelCase__					)
						while d:
									__a        =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 		__magic_name__    (		self					,  __snake_case					)   -> str:




						'''simple docstring'''
						__a        =0
						for x in self.graph:
									for y in self.graph[x]:
												if y[1] == u:
															count += 1
						return count





			def 		__magic_name__    (		self					,  __snake_case					)   -> Tuple:




						'''simple docstring'''
						return len(self.graph[u]					)





			def 		__magic_name__    (		self					,  __snake_case=-2					)   -> List[str]:




						'''simple docstring'''
						__a        =[]
						__a        =[]
						if s == -2:
									__a        =list(self.graph					)[0]
						stack.append(lowerCamelCase__					)
						visited.append(lowerCamelCase__					)
						__a        =s
						__a        =[]

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

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

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





			def 		__magic_name__    (		self					)   -> List[str]:




						'''simple docstring'''
						__a        =[]
						__a        =[]
						__a        =list(self.graph					)[0]
						stack.append(lowerCamelCase__					)
						visited.append(lowerCamelCase__					)
						__a        =-2
						__a        =[]
						__a        =s
						__a        =False
						__a        =set()

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

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

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





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




						'''simple docstring'''
						__a        =[]
						__a        =[]
						__a        =list(self.graph					)[0]
						stack.append(lowerCamelCase__					)
						visited.append(lowerCamelCase__					)
						__a        =-2
						__a        =[]
						__a        =s
						__a        =False
						__a        =set()

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

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

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





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




						'''simple docstring'''
						__a        =time()
						self.dfs(lowerCamelCase__					,  lowerCamelCase__					)
						__a        =time()
						return end - begin





			def 		__magic_name__    (		self					,  __snake_case=-2					)   -> List[Any]:




						'''simple docstring'''
						__a        =time()
						self.bfs(lowerCamelCase__					)
						__a        =time()
						return end - begin






class 	__magic_name__    :





			def __init__(		self					)   -> List[str]:




						'''simple docstring'''
						__a        ={}





			def 		__magic_name__    (		self					,  __snake_case					,  __snake_case					,  __snake_case=1					)   -> Tuple:




						'''simple docstring'''
						# check if the u exists
						if self.graph.get(lowerCamelCase__					):
									# 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
									__a        =[[w, v]]
						# add the other way
						if self.graph.get(lowerCamelCase__					):
									# 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
									__a        =[[w, u]]





			def 		__magic_name__    (		self					,  __snake_case					,  __snake_case					)   -> List[Any]:




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





			def 		__magic_name__    (		self					,  __snake_case=-2					,  __snake_case=-1					)   -> List[Any]:




						'''simple docstring'''
						if s == d:
									return []
						__a        =[]
						__a        =[]
						if s == -2:
									__a        =list(self.graph					)[0]
						stack.append(lowerCamelCase__					)
						visited.append(lowerCamelCase__					)
						__a        =s

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

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

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





			def 		__magic_name__    (		self					,  __snake_case=-1					)   -> str:




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





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




						'''simple docstring'''
						__a        =deque()
						__a        =[]
						if s == -2:
									__a        =list(self.graph					)[0]
						d.append(lowerCamelCase__					)
						visited.append(lowerCamelCase__					)
						while d:
									__a        =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 		__magic_name__    (		self					,  __snake_case					)   -> Optional[int]:




						'''simple docstring'''
						return len(self.graph[u]					)





			def 		__magic_name__    (		self					)   -> str:




						'''simple docstring'''
						__a        =[]
						__a        =[]
						__a        =list(self.graph					)[0]
						stack.append(lowerCamelCase__					)
						visited.append(lowerCamelCase__					)
						__a        =-2
						__a        =[]
						__a        =s
						__a        =False
						__a        =set()

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

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

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





			def 		__magic_name__    (		self					)   -> Any:




						'''simple docstring'''
						__a        =[]
						__a        =[]
						__a        =list(self.graph					)[0]
						stack.append(lowerCamelCase__					)
						visited.append(lowerCamelCase__					)
						__a        =-2
						__a        =[]
						__a        =s
						__a        =False
						__a        =set()

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

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

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





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




						'''simple docstring'''
						return list(self.graph					)





			def 		__magic_name__    (		self					,  __snake_case=-2					,  __snake_case=-1					)   -> List[Any]:




						'''simple docstring'''
						__a        =time()
						self.dfs(lowerCamelCase__					,  lowerCamelCase__					)
						__a        =time()
						return end - begin





			def 		__magic_name__    (		self					,  __snake_case=-2					)   -> List[Any]:




						'''simple docstring'''
						__a        =time()
						self.bfs(lowerCamelCase__					)
						__a        =time()
						return end - begin












from math import sqrt







def 			lowerCamelCase_		(       UpperCamelCase__				:      int      )     ->       bool:





				"""simple docstring"""


				if 1 < number < 4:
								# 2 and 3 are primes
								return True
				elif number < 2 or number % 2 == 0 or number % 3 == 0:
								# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
								return False

				# All primes number are in format of 6k +/- 1
				for i in range(5 ,     int(sqrt(UpperCamelCase__      ) + 1      ) ,     6      ):
								if number % i == 0 or number % (i + 2) == 0:
												return False
				return True







def 			lowerCamelCase_		(       UpperCamelCase__				:      int = 1_0001      )     ->       int:





				"""simple docstring"""


				__lowerCamelCase		       =    0
				__lowerCamelCase		       =    1
				while count != nth and number < 3:
								number += 1
								if is_prime(UpperCamelCase__      ):
												count += 1
				while count != nth:
								number += 2
								if is_prime(UpperCamelCase__      ):
												count += 1
				return number


if __name__ == "__main__":
					print(f'''{solution() = }''')


