





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


class 						lowerCamelCase       :







       """simple docstring"""




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





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						{}






       def  A_     ( self     :					List[Any],			_UpperCAmelCase     :					Tuple,			_UpperCAmelCase     :					int,			_UpperCAmelCase     :					Any=1						)				->			Any:





              """simple docstring"""
              if self.graph.get(_UpperCAmelCase						):
                     if self.graph[u].count([w, v]						) == 0:
                            self.graph[u].append([w, v]						)
              else:
                     SCREAMING_SNAKE_CASE__       :      Dict     =						[[w, v]]
              if not self.graph.get(_UpperCAmelCase						):
                     SCREAMING_SNAKE_CASE__       :      List[str]     =						[]






       def  A_     ( self     :					List[str]						)				->			List[Any]:





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






       def  A_     ( self     :					int,			_UpperCAmelCase     :					Tuple,			_UpperCAmelCase     :					Optional[int]						)				->			Any:





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






       def  A_     ( self     :					List[str],			_UpperCAmelCase     :					List[Any]=-2,			_UpperCAmelCase     :					Optional[int]=-1						)				->			Tuple:





              """simple docstring"""
              if s == d:
                     return []
              SCREAMING_SNAKE_CASE__       :      int     =						[]
              SCREAMING_SNAKE_CASE__       :      Any     =						[]
              if s == -2:
                     SCREAMING_SNAKE_CASE__       :      Tuple     =						list(self.graph						)[0]
              stack.append(_UpperCAmelCase						)
              visited.append(_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      int     =						s

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

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            if len(_UpperCAmelCase						) != 0:
                                   SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						stack[len(_UpperCAmelCase						) - 1]
                     else:
                            SCREAMING_SNAKE_CASE__       :      str     =						ss

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






       def  A_     ( self     :					Dict,			_UpperCAmelCase     :					Optional[Any]=-1						)				->			int:





              """simple docstring"""
              if c == -1:
                     SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						floor(random() * 1_0_0_0_0						) + 1_0
              for i in range(_UpperCAmelCase						):
                     # every vertex has max 100 edges
                     for _ in range(floor(random() * 1_0_2						) + 1						):
                            SCREAMING_SNAKE_CASE__       :      Optional[int]     =						floor(random() * c						) + 1
                            if n != i:
                                   self.add_pair(_UpperCAmelCase,			_UpperCAmelCase,			1						)






       def  A_     ( self     :					List[str],			_UpperCAmelCase     :					Optional[int]=-2						)				->			Tuple:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						deque()
              SCREAMING_SNAKE_CASE__       :      str     =						[]
              if s == -2:
                     SCREAMING_SNAKE_CASE__       :      Tuple     =						list(self.graph						)[0]
              d.append(_UpperCAmelCase						)
              visited.append(_UpperCAmelCase						)
              while d:
                     SCREAMING_SNAKE_CASE__       :      Optional[int]     =						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  A_     ( self     :					List[Any],			_UpperCAmelCase     :					str						)				->			List[str]:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      List[str]     =						0
              for x in self.graph:
                     for y in self.graph[x]:
                            if y[1] == u:
                                   count += 1
              return count






       def  A_     ( self     :					Tuple,			_UpperCAmelCase     :					Tuple						)				->			Union[str, Any]:





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






       def  A_     ( self     :					List[str],			_UpperCAmelCase     :					int=-2						)				->			str:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      Any     =						[]
              SCREAMING_SNAKE_CASE__       :      int     =						[]
              if s == -2:
                     SCREAMING_SNAKE_CASE__       :      Dict     =						list(self.graph						)[0]
              stack.append(_UpperCAmelCase						)
              visited.append(_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      Tuple     =						s
              SCREAMING_SNAKE_CASE__       :      Tuple     =						[]

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

            # check if all the children are visited
                     if s == ss:
                            sorted_nodes.append(stack.pop()						)
                            if len(_UpperCAmelCase						) != 0:
                                   SCREAMING_SNAKE_CASE__       :      int     =						stack[len(_UpperCAmelCase						) - 1]
                     else:
                            SCREAMING_SNAKE_CASE__       :      List[str]     =						ss

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






       def  A_     ( self     :					Tuple						)				->			int:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      int     =						[]
              SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						[]
              SCREAMING_SNAKE_CASE__       :      int     =						list(self.graph						)[0]
              stack.append(_UpperCAmelCase						)
              visited.append(_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      str     =						-2
              SCREAMING_SNAKE_CASE__       :      List[Any]     =						[]
              SCREAMING_SNAKE_CASE__       :      Any     =						s
              SCREAMING_SNAKE_CASE__       :      Dict     =						False
              SCREAMING_SNAKE_CASE__       :      Dict     =						set()

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

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            SCREAMING_SNAKE_CASE__       :      List[str]     =						True
                            if len(_UpperCAmelCase						) != 0:
                                   SCREAMING_SNAKE_CASE__       :      List[str]     =						stack[len(_UpperCAmelCase						) - 1]
                     else:
                            SCREAMING_SNAKE_CASE__       :      str     =						False
                            indirect_parents.append(_UpperCAmelCase						)
                            SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						s
                            SCREAMING_SNAKE_CASE__       :      List[Any]     =						ss

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






       def  A_     ( self     :					Dict						)				->			Dict:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      Tuple     =						[]
              SCREAMING_SNAKE_CASE__       :      List[Any]     =						[]
              SCREAMING_SNAKE_CASE__       :      int     =						list(self.graph						)[0]
              stack.append(_UpperCAmelCase						)
              visited.append(_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      List[str]     =						-2
              SCREAMING_SNAKE_CASE__       :      Optional[int]     =						[]
              SCREAMING_SNAKE_CASE__       :      Dict     =						s
              SCREAMING_SNAKE_CASE__       :      List[str]     =						False
              SCREAMING_SNAKE_CASE__       :      List[Any]     =						set()

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

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						True
                            if len(_UpperCAmelCase						) != 0:
                                   SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						stack[len(_UpperCAmelCase						) - 1]
                     else:
                            SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						False
                            indirect_parents.append(_UpperCAmelCase						)
                            SCREAMING_SNAKE_CASE__       :      int     =						s
                            SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						ss

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






       def  A_     ( self     :					str,			_UpperCAmelCase     :					Any=-2,			_UpperCAmelCase     :					List[Any]=-1						)				->			Union[str, Any]:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      int     =						time()
              self.dfs(_UpperCAmelCase,			_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      Optional[int]     =						time()
              return end - begin






       def  A_     ( self     :					Tuple,			_UpperCAmelCase     :					Optional[int]=-2						)				->			str:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      Tuple     =						time()
              self.bfs(_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      List[str]     =						time()
              return end - begin


class 						lowerCamelCase       :







       """simple docstring"""




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





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      List[str]     =						{}






       def  A_     ( self     :					Dict,			_UpperCAmelCase     :					Optional[int],			_UpperCAmelCase     :					Optional[int],			_UpperCAmelCase     :					str=1						)				->			Optional[Any]:





              """simple docstring"""
              # 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
                     SCREAMING_SNAKE_CASE__       :      List[str]     =						[[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
                     SCREAMING_SNAKE_CASE__       :      str     =						[[w, u]]






       def  A_     ( self     :					Tuple,			_UpperCAmelCase     :					List[Any],			_UpperCAmelCase     :					Dict						)				->			str:





              """simple docstring"""
              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  A_     ( self     :					Any,			_UpperCAmelCase     :					Any=-2,			_UpperCAmelCase     :					List[str]=-1						)				->			List[str]:





              """simple docstring"""
              if s == d:
                     return []
              SCREAMING_SNAKE_CASE__       :      Optional[int]     =						[]
              SCREAMING_SNAKE_CASE__       :      int     =						[]
              if s == -2:
                     SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						list(self.graph						)[0]
              stack.append(_UpperCAmelCase						)
              visited.append(_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						s

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

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            if len(_UpperCAmelCase						) != 0:
                                   SCREAMING_SNAKE_CASE__       :      Optional[int]     =						stack[len(_UpperCAmelCase						) - 1]
                     else:
                            SCREAMING_SNAKE_CASE__       :      Dict     =						ss

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






       def  A_     ( self     :					Dict,			_UpperCAmelCase     :					Tuple=-1						)				->			List[str]:





              """simple docstring"""
              if c == -1:
                     SCREAMING_SNAKE_CASE__       :      Optional[int]     =						floor(random() * 1_0_0_0_0						) + 1_0
              for i in range(_UpperCAmelCase						):
                     # every vertex has max 100 edges
                     for _ in range(floor(random() * 1_0_2						) + 1						):
                            SCREAMING_SNAKE_CASE__       :      str     =						floor(random() * c						) + 1
                            if n != i:
                                   self.add_pair(_UpperCAmelCase,			_UpperCAmelCase,			1						)






       def  A_     ( self     :					Any,			_UpperCAmelCase     :					str=-2						)				->			Union[str, Any]:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      str     =						deque()
              SCREAMING_SNAKE_CASE__       :      Any     =						[]
              if s == -2:
                     SCREAMING_SNAKE_CASE__       :      List[str]     =						list(self.graph						)[0]
              d.append(_UpperCAmelCase						)
              visited.append(_UpperCAmelCase						)
              while d:
                     SCREAMING_SNAKE_CASE__       :      List[Any]     =						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  A_     ( self     :					Union[str, Any],			_UpperCAmelCase     :					Any						)				->			Tuple:





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






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





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      Dict     =						[]
              SCREAMING_SNAKE_CASE__       :      List[Any]     =						[]
              SCREAMING_SNAKE_CASE__       :      List[str]     =						list(self.graph						)[0]
              stack.append(_UpperCAmelCase						)
              visited.append(_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      Optional[int]     =						-2
              SCREAMING_SNAKE_CASE__       :      str     =						[]
              SCREAMING_SNAKE_CASE__       :      Dict     =						s
              SCREAMING_SNAKE_CASE__       :      int     =						False
              SCREAMING_SNAKE_CASE__       :      Any     =						set()

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

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            SCREAMING_SNAKE_CASE__       :      str     =						True
                            if len(_UpperCAmelCase						) != 0:
                                   SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						stack[len(_UpperCAmelCase						) - 1]
                     else:
                            SCREAMING_SNAKE_CASE__       :      List[Any]     =						False
                            indirect_parents.append(_UpperCAmelCase						)
                            SCREAMING_SNAKE_CASE__       :      Optional[int]     =						s
                            SCREAMING_SNAKE_CASE__       :      Tuple     =						ss

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






       def  A_     ( self     :					Optional[int]						)				->			Union[str, Any]:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      Optional[int]     =						[]
              SCREAMING_SNAKE_CASE__       :      Any     =						[]
              SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						list(self.graph						)[0]
              stack.append(_UpperCAmelCase						)
              visited.append(_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      int     =						-2
              SCREAMING_SNAKE_CASE__       :      Tuple     =						[]
              SCREAMING_SNAKE_CASE__       :      List[Any]     =						s
              SCREAMING_SNAKE_CASE__       :      Any     =						False
              SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						set()

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

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            SCREAMING_SNAKE_CASE__       :      Tuple     =						True
                            if len(_UpperCAmelCase						) != 0:
                                   SCREAMING_SNAKE_CASE__       :      Optional[int]     =						stack[len(_UpperCAmelCase						) - 1]
                     else:
                            SCREAMING_SNAKE_CASE__       :      List[Any]     =						False
                            indirect_parents.append(_UpperCAmelCase						)
                            SCREAMING_SNAKE_CASE__       :      str     =						s
                            SCREAMING_SNAKE_CASE__       :      str     =						ss

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






       def  A_     ( self     :					str						)				->			Optional[Any]:





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






       def  A_     ( self     :					List[Any],			_UpperCAmelCase     :					Optional[Any]=-2,			_UpperCAmelCase     :					List[str]=-1						)				->			List[str]:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      Optional[int]     =						time()
              self.dfs(_UpperCAmelCase,			_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						time()
              return end - begin






       def  A_     ( self     :					List[str],			_UpperCAmelCase     :					str=-2						)				->			int:





              """simple docstring"""
              SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						time()
              self.bfs(_UpperCAmelCase						)
              SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						time()
              return end - begin













def _a (  SCREAMING_SNAKE_CASE__      :  str       )	->    str:

							'''simple docstring'''






							if not all(char in "01" for char in bin_string       ):
														raise ValueError("Non-binary value was passed to the function"       )
							if not bin_string:
														raise ValueError("Empty string was passed to the function"       )
							SCREAMING_SNAKE_CASE__       :      List[Any]     =						""
							while len(SCREAMING_SNAKE_CASE__       ) % 3 != 0:
														SCREAMING_SNAKE_CASE__       :      str     =						"0" + bin_string
							SCREAMING_SNAKE_CASE__       :      List[Any]     =						[
							    bin_string[index : index + 3]
							    for index in range(len(SCREAMING_SNAKE_CASE__       )       )
							    if index % 3 == 0
							]
							for bin_group in bin_string_in_3_list:
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						0
														for index, val in enumerate(SCREAMING_SNAKE_CASE__       ):
																					oct_val += int(2 ** (2 - index) * int(SCREAMING_SNAKE_CASE__       )       )
														oct_string += str(SCREAMING_SNAKE_CASE__       )
							return oct_string


if __name__ == "__main__":
		from doctest import testmod

		testmod()






