



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






class 						__a :



	def __init__(						self							:    List[Any])->							Any:
						__lowerCAmelCase	   ={}



	def 		UpperCamelCase							(						self							:    str				,	snake_case_							:    List[str]				,	snake_case_							:    Optional[int]				,	snake_case_							:    Tuple=1)->							Optional[Any]:
						if self.graph.get(snake_case_):
											if self.graph[u].count([w, v]) == 0:
																self.graph[u].append([w, v])
						else:
											__lowerCAmelCase	   =[[w, v]]
						if not self.graph.get(snake_case_):
											__lowerCAmelCase	   =[]



	def 		UpperCamelCase							(						self							:    List[str])->							Optional[Any]:
						return list(self.graph)



	def 		UpperCamelCase							(						self							:    Union[str, Any]				,	snake_case_							:    Tuple				,	snake_case_							:    List[Any])->							Tuple:
						if self.graph.get(snake_case_):
											for _ in self.graph[u]:
																if _[1] == v:
																					self.graph[u].remove(snake_case_)



	def 		UpperCamelCase							(						self							:    List[Any]				,	snake_case_							:    List[str]=-2				,	snake_case_							:    List[Any]=-1)->							Tuple:
						if s == d:
											return []
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =[]
						if s == -2:
											__lowerCAmelCase	   =list(self.graph)[0]
						stack.append(snake_case_)
						visited.append(snake_case_)
						__lowerCAmelCase	   =s

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

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

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



	def 		UpperCamelCase							(						self							:    int				,	snake_case_							:    int=-1)->							Union[str, Any]:
						if c == -1:
											__lowerCAmelCase	   =floor(random() * 1_00_00) + 10
						for i in range(snake_case_):
											# every vertex has max 100 edges
											for _ in range(floor(random() * 1_02) + 1):
																__lowerCAmelCase	   =floor(random() * c) + 1
																if n != i:
																					self.add_pair(snake_case_				,	snake_case_				,	1)



	def 		UpperCamelCase							(						self							:    int				,	snake_case_							:    Optional[int]=-2)->							Optional[int]:
						__lowerCAmelCase	   =deque()
						__lowerCAmelCase	   =[]
						if s == -2:
											__lowerCAmelCase	   =list(self.graph)[0]
						d.append(snake_case_)
						visited.append(snake_case_)
						while d:
											__lowerCAmelCase	   =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 		UpperCamelCase							(						self							:    Optional[int]				,	snake_case_							:    str)->							Tuple:
						__lowerCAmelCase	   =0
						for x in self.graph:
											for y in self.graph[x]:
																if y[1] == u:
																					count += 1
						return count



	def 		UpperCamelCase							(						self							:    int				,	snake_case_							:    Union[str, Any])->							str:
						return len(self.graph[u])



	def 		UpperCamelCase							(						self							:    Optional[int]				,	snake_case_							:    Union[str, Any]=-2)->							Optional[Any]:
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =[]
						if s == -2:
											__lowerCAmelCase	   =list(self.graph)[0]
						stack.append(snake_case_)
						visited.append(snake_case_)
						__lowerCAmelCase	   =s
						__lowerCAmelCase	   =[]

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

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

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



	def 		UpperCamelCase							(						self							:    str)->							Tuple:
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =list(self.graph)[0]
						stack.append(snake_case_)
						visited.append(snake_case_)
						__lowerCAmelCase	   =-2
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =s
						__lowerCAmelCase	   =False
						__lowerCAmelCase	   =set()

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

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

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



	def 		UpperCamelCase							(						self							:    Optional[int])->							str:
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =list(self.graph)[0]
						stack.append(snake_case_)
						visited.append(snake_case_)
						__lowerCAmelCase	   =-2
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =s
						__lowerCAmelCase	   =False
						__lowerCAmelCase	   =set()

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

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

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



	def 		UpperCamelCase							(						self							:    Optional[int]				,	snake_case_							:    str=-2				,	snake_case_							:    int=-1)->							Optional[int]:
						__lowerCAmelCase	   =time()
						self.dfs(snake_case_				,	snake_case_)
						__lowerCAmelCase	   =time()
						return end - begin



	def 		UpperCamelCase							(						self							:    List[Any]				,	snake_case_							:    Tuple=-2)->							Optional[Any]:
						__lowerCAmelCase	   =time()
						self.bfs(snake_case_)
						__lowerCAmelCase	   =time()
						return end - begin






class 						__a :



	def __init__(						self							:    Tuple)->							Dict:
						__lowerCAmelCase	   ={}



	def 		UpperCamelCase							(						self							:    Optional[Any]				,	snake_case_							:    List[Any]				,	snake_case_							:    Union[str, Any]				,	snake_case_							:    Union[str, Any]=1)->							str:
						# check if the u exists
						if self.graph.get(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
											__lowerCAmelCase	   =[[w, v]]
						# add the other way
						if self.graph.get(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
											__lowerCAmelCase	   =[[w, u]]



	def 		UpperCamelCase							(						self							:    Union[str, Any]				,	snake_case_							:    Dict				,	snake_case_							:    Tuple)->							int:
						if self.graph.get(snake_case_):
											for _ in self.graph[u]:
																if _[1] == v:
																					self.graph[u].remove(snake_case_)
        # the other way round
						if self.graph.get(snake_case_):
											for _ in self.graph[v]:
																if _[1] == u:
																					self.graph[v].remove(snake_case_)



	def 		UpperCamelCase							(						self							:    Union[str, Any]				,	snake_case_							:    Optional[int]=-2				,	snake_case_							:    Union[str, Any]=-1)->							Any:
						if s == d:
											return []
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =[]
						if s == -2:
											__lowerCAmelCase	   =list(self.graph)[0]
						stack.append(snake_case_)
						visited.append(snake_case_)
						__lowerCAmelCase	   =s

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

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

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



	def 		UpperCamelCase							(						self							:    List[str]				,	snake_case_							:    Dict=-1)->							Dict:
						if c == -1:
											__lowerCAmelCase	   =floor(random() * 1_00_00) + 10
						for i in range(snake_case_):
											# every vertex has max 100 edges
											for _ in range(floor(random() * 1_02) + 1):
																__lowerCAmelCase	   =floor(random() * c) + 1
																if n != i:
																					self.add_pair(snake_case_				,	snake_case_				,	1)



	def 		UpperCamelCase							(						self							:    Dict				,	snake_case_							:    List[str]=-2)->							Union[str, Any]:
						__lowerCAmelCase	   =deque()
						__lowerCAmelCase	   =[]
						if s == -2:
											__lowerCAmelCase	   =list(self.graph)[0]
						d.append(snake_case_)
						visited.append(snake_case_)
						while d:
											__lowerCAmelCase	   =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 		UpperCamelCase							(						self							:    List[Any]				,	snake_case_							:    Dict)->							int:
						return len(self.graph[u])



	def 		UpperCamelCase							(						self							:    Union[str, Any])->							Union[str, Any]:
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =list(self.graph)[0]
						stack.append(snake_case_)
						visited.append(snake_case_)
						__lowerCAmelCase	   =-2
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =s
						__lowerCAmelCase	   =False
						__lowerCAmelCase	   =set()

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

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

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



	def 		UpperCamelCase							(						self							:    List[Any])->							Optional[int]:
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =list(self.graph)[0]
						stack.append(snake_case_)
						visited.append(snake_case_)
						__lowerCAmelCase	   =-2
						__lowerCAmelCase	   =[]
						__lowerCAmelCase	   =s
						__lowerCAmelCase	   =False
						__lowerCAmelCase	   =set()

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

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

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



	def 		UpperCamelCase							(						self							:    Tuple)->							Any:
						return list(self.graph)



	def 		UpperCamelCase							(						self							:    Dict				,	snake_case_							:    int=-2				,	snake_case_							:    List[Any]=-1)->							List[str]:
						__lowerCAmelCase	   =time()
						self.dfs(snake_case_				,	snake_case_)
						__lowerCAmelCase	   =time()
						return end - begin



	def 		UpperCamelCase							(						self							:    List[str]				,	snake_case_							:    List[str]=-2)->							Dict:
						__lowerCAmelCase	   =time()
						self.bfs(snake_case_)
						__lowerCAmelCase	   =time()
						return end - begin









def 					__lowerCAmelCase		(  __lowerCamelCase	:    list[int]	)  ->						int:
					if not numbers:
										return 0

					if not isinstance(__lowerCamelCase				,   (list, tuple)	) or not all(
					    isinstance(__lowerCamelCase				,   __lowerCamelCase	) for number in numbers	):
										raise ValueError("""numbers must be an iterable of integers"""	)

					__lowerCAmelCase	   =__lowerCAmelCase	   =__lowerCAmelCase	   =numbers[0]

					for i in range(1				,   len(__lowerCamelCase	)	):
										# update the maximum and minimum subarray products
										__lowerCAmelCase	   =numbers[i]
										if number < 0:
															__lowerCAmelCase   ,	__lowerCAmelCase	   =min_till_now, max_till_now
										__lowerCAmelCase	   =max(__lowerCamelCase				,   max_till_now * number	)
										__lowerCAmelCase	   =min(__lowerCamelCase				,   min_till_now * number	)

										# update the maximum product found till now
										__lowerCAmelCase	   =max(__lowerCamelCase				,   __lowerCamelCase	)

					return max_prod




