






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





class 					A__     :

     '''simple docstring'''






     def __init__( self      :    Dict ):






           """simple docstring"""




           UpperCamelCase					       =  {}







     def   _SCREAMING_SNAKE_CASE     ( self      :    List[str]   ,						_SCREAMING_SNAKE_CASE      :    Union[str, Any]   ,						_SCREAMING_SNAKE_CASE      :    Optional[int]   ,						_SCREAMING_SNAKE_CASE      :    Optional[Any]=1 ):






           """simple docstring"""




           if self.graph.get(_SCREAMING_SNAKE_CASE ):
                 if self.graph[u].count([w, v] ) == 0:
                       self.graph[u].append([w, v] )
           else:
                 UpperCamelCase					       =  [[w, v]]
           if not self.graph.get(_SCREAMING_SNAKE_CASE ):
                 UpperCamelCase					       =  []







     def   _SCREAMING_SNAKE_CASE     ( self      :    Optional[Any] ):






           """simple docstring"""




           return list(self.graph )







     def   _SCREAMING_SNAKE_CASE     ( self      :    int   ,						_SCREAMING_SNAKE_CASE      :    int   ,						_SCREAMING_SNAKE_CASE      :    int ):






           """simple docstring"""




           if self.graph.get(_SCREAMING_SNAKE_CASE ):
                 for _ in self.graph[u]:
                       if _[1] == v:
                             self.graph[u].remove(_SCREAMING_SNAKE_CASE )







     def   _SCREAMING_SNAKE_CASE     ( self      :    int   ,						_SCREAMING_SNAKE_CASE      :    List[Any]=-2   ,						_SCREAMING_SNAKE_CASE      :    Tuple=-1 ):






           """simple docstring"""




           if s == d:
                 return []
           UpperCamelCase					       =  []
           UpperCamelCase					       =  []
           if s == -2:
                 UpperCamelCase					       =  list(self.graph )[0]
           stack.append(_SCREAMING_SNAKE_CASE )
           visited.append(_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  s

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

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

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







     def   _SCREAMING_SNAKE_CASE     ( self      :    Optional[Any]   ,						_SCREAMING_SNAKE_CASE      :    List[str]=-1 ):






           """simple docstring"""




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







     def   _SCREAMING_SNAKE_CASE     ( self      :    Dict   ,						_SCREAMING_SNAKE_CASE      :    Optional[int]=-2 ):






           """simple docstring"""




           UpperCamelCase					       =  deque()
           UpperCamelCase					       =  []
           if s == -2:
                 UpperCamelCase					       =  list(self.graph )[0]
           d.append(_SCREAMING_SNAKE_CASE )
           visited.append(_SCREAMING_SNAKE_CASE )
           while d:
                 UpperCamelCase					       =  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   _SCREAMING_SNAKE_CASE     ( self      :    Tuple   ,						_SCREAMING_SNAKE_CASE      :    List[str] ):






           """simple docstring"""




           UpperCamelCase					       =  0
           for x in self.graph:
                 for y in self.graph[x]:
                       if y[1] == u:
                             count += 1
           return count







     def   _SCREAMING_SNAKE_CASE     ( self      :    List[str]   ,						_SCREAMING_SNAKE_CASE      :    Tuple ):






           """simple docstring"""




           return len(self.graph[u] )







     def   _SCREAMING_SNAKE_CASE     ( self      :    Dict   ,						_SCREAMING_SNAKE_CASE      :    List[str]=-2 ):






           """simple docstring"""




           UpperCamelCase					       =  []
           UpperCamelCase					       =  []
           if s == -2:
                 UpperCamelCase					       =  list(self.graph )[0]
           stack.append(_SCREAMING_SNAKE_CASE )
           visited.append(_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  s
           UpperCamelCase					       =  []

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

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

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







     def   _SCREAMING_SNAKE_CASE     ( self      :    List[Any] ):






           """simple docstring"""




           UpperCamelCase					       =  []
           UpperCamelCase					       =  []
           UpperCamelCase					       =  list(self.graph )[0]
           stack.append(_SCREAMING_SNAKE_CASE )
           visited.append(_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  -2
           UpperCamelCase					       =  []
           UpperCamelCase					       =  s
           UpperCamelCase					       =  False
           UpperCamelCase					       =  set()

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

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

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







     def   _SCREAMING_SNAKE_CASE     ( self      :    Dict ):






           """simple docstring"""




           UpperCamelCase					       =  []
           UpperCamelCase					       =  []
           UpperCamelCase					       =  list(self.graph )[0]
           stack.append(_SCREAMING_SNAKE_CASE )
           visited.append(_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  -2
           UpperCamelCase					       =  []
           UpperCamelCase					       =  s
           UpperCamelCase					       =  False
           UpperCamelCase					       =  set()

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

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

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







     def   _SCREAMING_SNAKE_CASE     ( self      :    List[str]   ,						_SCREAMING_SNAKE_CASE      :    List[str]=-2   ,						_SCREAMING_SNAKE_CASE      :    List[str]=-1 ):






           """simple docstring"""




           UpperCamelCase					       =  time()
           self.dfs(_SCREAMING_SNAKE_CASE   ,						_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  time()
           return end - begin







     def   _SCREAMING_SNAKE_CASE     ( self      :    Optional[Any]   ,						_SCREAMING_SNAKE_CASE      :    Optional[Any]=-2 ):






           """simple docstring"""




           UpperCamelCase					       =  time()
           self.bfs(_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  time()
           return end - begin





class 					A__     :

     '''simple docstring'''






     def __init__( self      :    Tuple ):






           """simple docstring"""




           UpperCamelCase					       =  {}







     def   _SCREAMING_SNAKE_CASE     ( self      :    Optional[int]   ,						_SCREAMING_SNAKE_CASE      :    str   ,						_SCREAMING_SNAKE_CASE      :    List[Any]   ,						_SCREAMING_SNAKE_CASE      :    Optional[int]=1 ):






           """simple docstring"""




           if self.graph.get(_SCREAMING_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
                 UpperCamelCase					       =  [[w, v]]
           # add the other way
           if self.graph.get(_SCREAMING_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
                 UpperCamelCase					       =  [[w, u]]







     def   _SCREAMING_SNAKE_CASE     ( self      :    str   ,						_SCREAMING_SNAKE_CASE      :    int   ,						_SCREAMING_SNAKE_CASE      :    Optional[int] ):






           """simple docstring"""




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







     def   _SCREAMING_SNAKE_CASE     ( self      :    int   ,						_SCREAMING_SNAKE_CASE      :    str=-2   ,						_SCREAMING_SNAKE_CASE      :    Any=-1 ):






           """simple docstring"""




           if s == d:
                 return []
           UpperCamelCase					       =  []
           UpperCamelCase					       =  []
           if s == -2:
                 UpperCamelCase					       =  list(self.graph )[0]
           stack.append(_SCREAMING_SNAKE_CASE )
           visited.append(_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  s

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

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

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







     def   _SCREAMING_SNAKE_CASE     ( self      :    Any   ,						_SCREAMING_SNAKE_CASE      :    Dict=-1 ):






           """simple docstring"""




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







     def   _SCREAMING_SNAKE_CASE     ( self      :    Union[str, Any]   ,						_SCREAMING_SNAKE_CASE      :    List[str]=-2 ):






           """simple docstring"""




           UpperCamelCase					       =  deque()
           UpperCamelCase					       =  []
           if s == -2:
                 UpperCamelCase					       =  list(self.graph )[0]
           d.append(_SCREAMING_SNAKE_CASE )
           visited.append(_SCREAMING_SNAKE_CASE )
           while d:
                 UpperCamelCase					       =  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   _SCREAMING_SNAKE_CASE     ( self      :    Optional[int]   ,						_SCREAMING_SNAKE_CASE      :    str ):






           """simple docstring"""




           return len(self.graph[u] )







     def   _SCREAMING_SNAKE_CASE     ( self      :    Tuple ):






           """simple docstring"""




           UpperCamelCase					       =  []
           UpperCamelCase					       =  []
           UpperCamelCase					       =  list(self.graph )[0]
           stack.append(_SCREAMING_SNAKE_CASE )
           visited.append(_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  -2
           UpperCamelCase					       =  []
           UpperCamelCase					       =  s
           UpperCamelCase					       =  False
           UpperCamelCase					       =  set()

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

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

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







     def   _SCREAMING_SNAKE_CASE     ( self      :    List[Any] ):






           """simple docstring"""




           UpperCamelCase					       =  []
           UpperCamelCase					       =  []
           UpperCamelCase					       =  list(self.graph )[0]
           stack.append(_SCREAMING_SNAKE_CASE )
           visited.append(_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  -2
           UpperCamelCase					       =  []
           UpperCamelCase					       =  s
           UpperCamelCase					       =  False
           UpperCamelCase					       =  set()

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

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

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







     def   _SCREAMING_SNAKE_CASE     ( self      :    List[Any] ):






           """simple docstring"""




           return list(self.graph )







     def   _SCREAMING_SNAKE_CASE     ( self      :    Dict   ,						_SCREAMING_SNAKE_CASE      :    Any=-2   ,						_SCREAMING_SNAKE_CASE      :    Optional[int]=-1 ):






           """simple docstring"""




           UpperCamelCase					       =  time()
           self.dfs(_SCREAMING_SNAKE_CASE   ,						_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  time()
           return end - begin







     def   _SCREAMING_SNAKE_CASE     ( self      :    int   ,						_SCREAMING_SNAKE_CASE      :    List[Any]=-2 ):






           """simple docstring"""




           UpperCamelCase					       =  time()
           self.bfs(_SCREAMING_SNAKE_CASE )
           UpperCamelCase					       =  time()
           return end - begin











def 		lowercase__  (				_UpperCamelCase) ->			list:
      """simple docstring"""

      if bit_count < 0:
            raise ValueError('The given input must be positive')

      # get the generated string sequence
      UpperCamelCase					       =  gray_code_sequence_string(_UpperCamelCase)
      #
      # convert them to integers
      for i in range(len(_UpperCamelCase)):
            UpperCamelCase					       =  int(sequence[i]       ,							2)

      return sequence
def 		lowercase__  (				_UpperCamelCase) ->			list:
      """simple docstring"""

      if bit_count == 0:
            return ["0"]

      if bit_count == 1:
            return ["0", "1"]

      UpperCamelCase					       =  1 << bit_count  # defines the length of the sequence
      # 1<< n is equivalent to 2^n

      # recursive answer will generate answer for n-1 bits
      UpperCamelCase					       =  gray_code_sequence_string(bit_count - 1)

      UpperCamelCase					       =  []

      # append 0 to first half of the smaller sequence generated
      for i in range(seq_len // 2):
            UpperCamelCase					       =  '0' + smaller_sequence[i]
            sequence.append(_UpperCamelCase)

      # append 1 to second half ... start from the end of the list
      for i in reversed(range(seq_len // 2)):
            UpperCamelCase					       =  '1' + smaller_sequence[i]
            sequence.append(_UpperCamelCase)

      return sequence


if __name__ == "__main__":
       import doctest

       doctest.testmod()



