






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




class 					UpperCamelCase_ :



	'''simple docstring'''




	def __init__(			self   )			->       int:
								snake_case_           =				{}




	def 				_UpperCamelCase     (			self			,     a			,     a			,     a=1   )			->       Any:
								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 				_UpperCamelCase     (			self   )			->       List[Any]:
								return list(self.graph   )




	def 				_UpperCamelCase     (			self			,     a			,     a   )			->       str:
								if self.graph.get(lowercase_   ):
															for _ in self.graph[u]:
																						if _[1] == v:
																													self.graph[u].remove(lowercase_   )




	def 				_UpperCamelCase     (			self			,     a=-2			,     a=-1   )			->       int:
								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 				_UpperCamelCase     (			self			,     a=-1   )			->       Optional[int]:
								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 				_UpperCamelCase     (			self			,     a=-2   )			->       Optional[Any]:
								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 				_UpperCamelCase     (			self			,     a   )			->       List[str]:
								snake_case_           =				0
								for x in self.graph:
															for y in self.graph[x]:
																						if y[1] == u:
																													count += 1
								return count




	def 				_UpperCamelCase     (			self			,     a   )			->       Optional[int]:
								return len(self.graph[u]   )




	def 				_UpperCamelCase     (			self			,     a=-2   )			->       str:
								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 				_UpperCamelCase     (			self   )			->       int:
								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 				_UpperCamelCase     (			self   )			->       Any:
								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 				_UpperCamelCase     (			self			,     a=-2			,     a=-1   )			->       Optional[int]:
								snake_case_           =				time()
								self.dfs(lowercase_			,     lowercase_   )
								snake_case_           =				time()
								return end - begin






	def 				_UpperCamelCase     (			self			,     a=-2   )			->       Optional[int]:
								snake_case_           =				time()
								self.bfs(lowercase_   )
								snake_case_           =				time()
								return end - begin






class 					UpperCamelCase_ :



	'''simple docstring'''




	def __init__(			self   )			->       List[str]:
								snake_case_           =				{}




	def 				_UpperCamelCase     (			self			,     a			,     a			,     a=1   )			->       str:
								# check if the u exists
								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 				_UpperCamelCase     (			self			,     a			,     a   )			->       List[Any]:
								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 				_UpperCamelCase     (			self			,     a=-2			,     a=-1   )			->       Tuple:
								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 				_UpperCamelCase     (			self			,     a=-1   )			->       int:
								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 				_UpperCamelCase     (			self			,     a=-2   )			->       Optional[int]:
								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 				_UpperCamelCase     (			self			,     a   )			->       List[str]:
								return len(self.graph[u]   )




	def 				_UpperCamelCase     (			self   )			->       Dict:
								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 				_UpperCamelCase     (			self   )			->       List[Any]:
								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 				_UpperCamelCase     (			self   )			->       Optional[int]:
								return list(self.graph   )




	def 				_UpperCamelCase     (			self			,     a=-2			,     a=-1   )			->       Any:
								snake_case_           =				time()
								self.dfs(lowercase_			,     lowercase_   )
								snake_case_           =				time()
								return end - begin






	def 				_UpperCamelCase     (			self			,     a=-2   )			->       List[str]:
								snake_case_           =				time()
								self.bfs(lowercase_   )
								snake_case_           =				time()
								return end - begin








"""simple docstring"""





def     __SCREAMING_SNAKE_CASE    ( A_		,	A_					):
	if number < 0 or shift_amount < 0:
		raise ValueError('''both inputs must be positive integers'''					)

	lowerCAmelCase__      :		int    							=      str(bin(A_					)					)
	binary_number += "0" * shift_amount
	return binary_number

def     __SCREAMING_SNAKE_CASE    ( A_		,	A_					):
	if number < 0 or shift_amount < 0:
		raise ValueError('''both inputs must be positive integers'''					)

	lowerCAmelCase__      :		Any    							=      str(bin(A_					)					)[2:]
	if shift_amount >= len(A_					):
		return "0b0"
	lowerCAmelCase__      :		Tuple    							=      binary_number[: len(A_					) - shift_amount]
	return "0b" + shifted_binary_number

def     __SCREAMING_SNAKE_CASE    ( A_		,	A_					):
	if number >= 0:  # Get binary representation of positive number
		lowerCAmelCase__      :		Union[str, Any]    							=      '''0''' + str(bin(A_					)					).strip('''-'''					)[2:]
	else:  # Get binary (2's complement) representation of negative number
		lowerCAmelCase__      :		Optional[Any]    							=      len(bin(A_					)[3:]					)  # Find 2's complement of number
		lowerCAmelCase__      :		Optional[int]    							=      bin(abs(A_					) - (1 << binary_number_length)					)[3:]
		lowerCAmelCase__      :		int    							=      (
		    '''1''' + '''0''' * (binary_number_length - len(A_					)) + binary_number
		)

	if shift_amount >= len(A_					):
		return "0b" + binary_number[0] * len(A_					)
	return (
	    "0b"
	    + binary_number[0] * shift_amount
	    + binary_number[: len(A_					) - shift_amount]
	)


if __name__ == "__main__":
							import doctest

							doctest.testmod()




