'''simple docstring'''

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


class     __UpperCAmelCase       :





  def __init__(	self ):
     lowerCAmelCase_			=      {}





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase=1 ):
     if self.graph.get(_lowerCamelCase ):
        if self.graph[u].count([w, v] ) == 0:
           self.graph[u].append([w, v] )
     else:
        lowerCAmelCase_			=      [[w, v]]
     if not self.graph.get(_lowerCamelCase ):
        lowerCAmelCase_			=      []





  def 						UpperCAmelCase_	(	self ):
     return list(self.graph )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     if self.graph.get(_lowerCamelCase ):
        for _ in self.graph[u]:
           if _[1] == v:
              self.graph[u].remove(_lowerCamelCase )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     if s == d:
        return []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      s

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

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

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





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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      deque()
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     d.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     while d:
        lowerCAmelCase_			=      d.popleft()
        if len(self.graph[s] ) != 0:
           for node in self.graph[s]:
              if visited.count(node[1] ) < 1:
                 d.append(node[1] )
                 visited.append(node[1] )
     return visited





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase ):
     lowerCAmelCase_			=      0
     for x in self.graph:
        for y in self.graph[x]:
           if y[1] == u:
              count += 1
     return count





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase ):
     return len(self.graph[u] )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      []

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

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

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





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

     while True:
        # check if there is any non isolated nodes
        if len(self.graph[s] ) != 0:
           lowerCAmelCase_			=      s
           for node in self.graph[s]:
              if (
                  visited.count(node[1] ) > 0
                  and node[1] != parent
                  and indirect_parents.count(node[1] ) > 0
                  and not on_the_way_back
              ):
                 lowerCAmelCase_			=      len(_lowerCamelCase ) - 1
                 while len_stack >= 0:
                    if stack[len_stack] == node[1]:
                       anticipating_nodes.add(node[1] )
                       break
                    else:
                       anticipating_nodes.add(stack[len_stack] )
                       len_stack -= 1
              if visited.count(node[1] ) < 1:
                 stack.append(node[1] )
                 visited.append(node[1] )
                 lowerCAmelCase_			=      node[1]
                 break

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

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





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

     while True:
        # check if there is any non isolated nodes
        if len(self.graph[s] ) != 0:
           lowerCAmelCase_			=      s
           for node in self.graph[s]:
              if (
                  visited.count(node[1] ) > 0
                  and node[1] != parent
                  and indirect_parents.count(node[1] ) > 0
                  and not on_the_way_back
              ):
                 lowerCAmelCase_			=      len(_lowerCamelCase ) - 1
                 while len_stack_minus_one >= 0:
                    if stack[len_stack_minus_one] == node[1]:
                       anticipating_nodes.add(node[1] )
                       break
                    else:
                       return True
              if visited.count(node[1] ) < 1:
                 stack.append(node[1] )
                 visited.append(node[1] )
                 lowerCAmelCase_			=      node[1]
                 break

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

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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     lowerCAmelCase_			=      time()
     self.dfs(_lowerCamelCase    ,     _lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin







  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      time()
     self.bfs(_lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin






class     __UpperCAmelCase       :





  def __init__(	self ):
     lowerCAmelCase_			=      {}





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase=1 ):
     # check if the u exists
     if self.graph.get(_lowerCamelCase ):
        # if there already is a edge
        if self.graph[u].count([w, v] ) == 0:
           self.graph[u].append([w, v] )
     else:
        # if u does not exist
        lowerCAmelCase_			=      [[w, v]]
     # add the other way
     if self.graph.get(_lowerCamelCase ):
        # if there already is a edge
        if self.graph[v].count([w, u] ) == 0:
           self.graph[v].append([w, u] )
     else:
        # if u does not exist
        lowerCAmelCase_			=      [[w, u]]





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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     if s == d:
        return []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      s

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

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

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





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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      deque()
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     d.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     while d:
        lowerCAmelCase_			=      d.popleft()
        if len(self.graph[s] ) != 0:
           for node in self.graph[s]:
              if visited.count(node[1] ) < 1:
                 d.append(node[1] )
                 visited.append(node[1] )
     return visited





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase ):
     return len(self.graph[u] )





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

     while True:
        # check if there is any non isolated nodes
        if len(self.graph[s] ) != 0:
           lowerCAmelCase_			=      s
           for node in self.graph[s]:
              if (
                  visited.count(node[1] ) > 0
                  and node[1] != parent
                  and indirect_parents.count(node[1] ) > 0
                  and not on_the_way_back
              ):
                 lowerCAmelCase_			=      len(_lowerCamelCase ) - 1
                 while len_stack >= 0:
                    if stack[len_stack] == node[1]:
                       anticipating_nodes.add(node[1] )
                       break
                    else:
                       anticipating_nodes.add(stack[len_stack] )
                       len_stack -= 1
              if visited.count(node[1] ) < 1:
                 stack.append(node[1] )
                 visited.append(node[1] )
                 lowerCAmelCase_			=      node[1]
                 break

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

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





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

     while True:
        # check if there is any non isolated nodes
        if len(self.graph[s] ) != 0:
           lowerCAmelCase_			=      s
           for node in self.graph[s]:
              if (
                  visited.count(node[1] ) > 0
                  and node[1] != parent
                  and indirect_parents.count(node[1] ) > 0
                  and not on_the_way_back
              ):
                 lowerCAmelCase_			=      len(_lowerCamelCase ) - 1
                 while len_stack_minus_one >= 0:
                    if stack[len_stack_minus_one] == node[1]:
                       anticipating_nodes.add(node[1] )
                       break
                    else:
                       return True
              if visited.count(node[1] ) < 1:
                 stack.append(node[1] )
                 visited.append(node[1] )
                 lowerCAmelCase_			=      node[1]
                 break

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

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





  def 						UpperCAmelCase_	(	self ):
     return list(self.graph )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     lowerCAmelCase_			=      time()
     self.dfs(_lowerCamelCase    ,     _lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin







  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      time()
     self.bfs(_lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin






'''simple docstring'''

from __future__ import annotations

from typing import Any



def snake_case_      (					__snake_case  :							list[Any])			->					None:
   create_state_space_tree(__snake_case	,   []	,   0)



def snake_case_      (					__snake_case  :							list[Any]	,   __snake_case  :							list[Any]	,   __snake_case  :							int)			->					None:

   if index == len(__snake_case):
      print(__snake_case)
      return

   create_state_space_tree(__snake_case	,   __snake_case	,   index + 1)
   current_subsequence.append(sequence[index])
   create_state_space_tree(__snake_case	,   __snake_case	,   index + 1)
   current_subsequence.pop()


if __name__ == "__main__":
 A_     :						list[Any]    							=[3, 1, 2, 4]
 generate_all_subsequences(seq)

 seq.clear()
 seq.extend(['''A''', '''B''', '''C'''])
 generate_all_subsequences(seq)





