




'''simple docstring'''


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





class    __lowercase						:







			def __init__(	self      )				->    Optional[Any]:
					__a			=					{}







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase      ,							UpperCamelCase      ,							UpperCamelCase=1      )				->    List[str]:
					if self.graph.get(UpperCamelCase      ):
							if self.graph[u].count([w, v]      ) == 0:
									self.graph[u].append([w, v]      )
					else:
							__a			=					[[w, v]]
					if not self.graph.get(UpperCamelCase      ):
							__a			=					[]







			def 		UpperCamelCase__			(	self      )				->    Dict:
					return list(self.graph      )







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







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase=-2      ,							UpperCamelCase=-1      )				->    Any:
					if s == d:
							return []
					__a			=					[]
					__a			=					[]
					if s == -2:
							__a			=					list(self.graph      )[0]
					stack.append(UpperCamelCase      )
					visited.append(UpperCamelCase      )
					__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(UpperCamelCase      )
															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(UpperCamelCase      ) != 0:
											__a			=					stack[len(UpperCamelCase      ) - 1]
							else:
									__a			=					ss

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







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







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







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase      )				->    int:
					return len(self.graph[u]      )







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase=-2      )				->    Tuple:
					__a			=					[]
					__a			=					[]
					if s == -2:
							__a			=					list(self.graph      )[0]
					stack.append(UpperCamelCase      )
					visited.append(UpperCamelCase      )
					__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(UpperCamelCase      ) != 0:
											__a			=					stack[len(UpperCamelCase      ) - 1]
							else:
									__a			=					ss

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







			def 		UpperCamelCase__			(	self      )				->    List[str]:
					__a			=					[]
					__a			=					[]
					__a			=					list(self.graph      )[0]
					stack.append(UpperCamelCase      )
					visited.append(UpperCamelCase      )
					__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(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]      )
													__a			=					node[1]
													break

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

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







			def 		UpperCamelCase__			(	self      )				->    int:
					__a			=					[]
					__a			=					[]
					__a			=					list(self.graph      )[0]
					stack.append(UpperCamelCase      )
					visited.append(UpperCamelCase      )
					__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(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]      )
													__a			=					node[1]
													break

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

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







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase=-2      ,							UpperCamelCase=-1      )				->    Tuple:
					__a			=					time()
					self.dfs(UpperCamelCase      ,							UpperCamelCase      )
					__a			=					time()
					return end - begin







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase=-2      )				->    str:
					__a			=					time()
					self.bfs(UpperCamelCase      )
					__a			=					time()
					return end - begin





class    __lowercase						:







			def __init__(	self      )				->    str:
					__a			=					{}







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase      ,							UpperCamelCase      ,							UpperCamelCase=1      )				->    Tuple:
					# check if the u exists
					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
							__a			=					[[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
							__a			=					[[w, u]]







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase      ,							UpperCamelCase      )				->    Optional[Any]:
					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 		UpperCamelCase__			(	self      ,							UpperCamelCase=-2      ,							UpperCamelCase=-1      )				->    List[str]:
					if s == d:
							return []
					__a			=					[]
					__a			=					[]
					if s == -2:
							__a			=					list(self.graph      )[0]
					stack.append(UpperCamelCase      )
					visited.append(UpperCamelCase      )
					__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(UpperCamelCase      )
															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(UpperCamelCase      ) != 0:
											__a			=					stack[len(UpperCamelCase      ) - 1]
							else:
									__a			=					ss

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







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase=-1      )				->    Optional[int]:
					if c == -1:
							__a			=					floor(random() * 1_0000      ) + 10
					for i in range(UpperCamelCase      ):
							# every vertex has max 100 edges
							for _ in range(floor(random() * 102      ) + 1      ):
									__a			=					floor(random() * c      ) + 1
									if n != i:
											self.add_pair(UpperCamelCase      ,							UpperCamelCase      ,							1      )







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase=-2      )				->    Tuple:
					__a			=					deque()
					__a			=					[]
					if s == -2:
							__a			=					list(self.graph      )[0]
					d.append(UpperCamelCase      )
					visited.append(UpperCamelCase      )
					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 		UpperCamelCase__			(	self      ,							UpperCamelCase      )				->    List[str]:
					return len(self.graph[u]      )







			def 		UpperCamelCase__			(	self      )				->    Tuple:
					__a			=					[]
					__a			=					[]
					__a			=					list(self.graph      )[0]
					stack.append(UpperCamelCase      )
					visited.append(UpperCamelCase      )
					__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(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]      )
													__a			=					node[1]
													break

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

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







			def 		UpperCamelCase__			(	self      )				->    int:
					__a			=					[]
					__a			=					[]
					__a			=					list(self.graph      )[0]
					stack.append(UpperCamelCase      )
					visited.append(UpperCamelCase      )
					__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(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]      )
													__a			=					node[1]
													break

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

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







			def 		UpperCamelCase__			(	self      )				->    Optional[Any]:
					return list(self.graph      )







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase=-2      ,							UpperCamelCase=-1      )				->    List[str]:
					__a			=					time()
					self.dfs(UpperCamelCase      ,							UpperCamelCase      )
					__a			=					time()
					return end - begin







			def 		UpperCamelCase__			(	self      ,							UpperCamelCase=-2      )				->    str:
					__a			=					time()
					self.bfs(UpperCamelCase      )
					__a			=					time()
					return end - begin









'''simple docstring'''


from ..utils import DummyObject, requires_backends





class    __lowercase						(  metaclass=__magic_name__ ):
   _a							=      ["""onnx"""]







   def __init__(	self      ,							*UpperCamelCase      ,							**UpperCamelCase      )				->    str:
     requires_backends(self      ,							['onnx']      )







   @classmethod
   def 		UpperCamelCase__			(	cls      ,							*UpperCamelCase      ,							**UpperCamelCase      )				->    Tuple:
     requires_backends(cls      ,							['onnx']      )







   @classmethod
   def 		UpperCamelCase__			(	cls      ,							*UpperCamelCase      ,							**UpperCamelCase      )				->    Tuple:
     requires_backends(cls      ,							['onnx']      )



