



"""simple docstring"""




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






class       UpperCAmelCase_    :



      def __init__(	self	:      Any		):
           _UpperCAmelCase     :      Optional[Any]														=       {}



      def 		snake_case_   (	self	:      str	,      A	:      int	,      A	:      int	,      A	:      int=1		):
           if self.graph.get(A		):
                if self.graph[u].count([w, v]		) == 0:
                     self.graph[u].append([w, v]		)
           else:
                _UpperCAmelCase     :      str														=       [[w, v]]
           if not self.graph.get(A		):
                _UpperCAmelCase     :      Union[str, Any]														=       []



      def 		snake_case_   (	self	:      List[Any]		):
           return list(self.graph		)



      def 		snake_case_   (	self	:      Tuple	,      A	:      str	,      A	:      List[str]		):
           if self.graph.get(A		):
                for _ in self.graph[u]:
                     if _[1] == v:
                          self.graph[u].remove(A		)



      def 		snake_case_   (	self	:      Optional[int]	,      A	:      Optional[Any]=-2	,      A	:      int=-1		):
           if s == d:
                return []
           _UpperCAmelCase     :      Any														=       []
           _UpperCAmelCase     :      Optional[int]														=       []
           if s == -2:
                _UpperCAmelCase     :      List[str]														=       list(self.graph		)[0]
           stack.append(A		)
           visited.append(A		)
           _UpperCAmelCase     :      Union[str, Any]														=       s

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

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

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



      def 		snake_case_   (	self	:      int	,      A	:      str=-1		):
           if c == -1:
                _UpperCAmelCase     :      Any														=       floor(random() * 1_0_0_0_0		) + 1_0
           for i in range(A		):
                # every vertex has max 100 edges
                for _ in range(floor(random() * 1_0_2		) + 1		):
                     _UpperCAmelCase     :      List[str]														=       floor(random() * c		) + 1
                     if n != i:
                          self.add_pair(A	,      A	,      1		)



      def 		snake_case_   (	self	:      Optional[Any]	,      A	:      Union[str, Any]=-2		):
           _UpperCAmelCase     :      int														=       deque()
           _UpperCAmelCase     :      Dict														=       []
           if s == -2:
                _UpperCAmelCase     :      Any														=       list(self.graph		)[0]
           d.append(A		)
           visited.append(A		)
           while d:
                _UpperCAmelCase     :      Dict														=       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 		snake_case_   (	self	:      Dict	,      A	:      List[Any]		):
           _UpperCAmelCase     :      str														=       0
           for x in self.graph:
                for y in self.graph[x]:
                     if y[1] == u:
                          count += 1
           return count



      def 		snake_case_   (	self	:      Tuple	,      A	:      Dict		):
           return len(self.graph[u]		)



      def 		snake_case_   (	self	:      List[Any]	,      A	:      Union[str, Any]=-2		):
           _UpperCAmelCase     :      Optional[int]														=       []
           _UpperCAmelCase     :      Any														=       []
           if s == -2:
                _UpperCAmelCase     :      Tuple														=       list(self.graph		)[0]
           stack.append(A		)
           visited.append(A		)
           _UpperCAmelCase     :      Dict														=       s
           _UpperCAmelCase     :      Dict														=       []

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

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

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



      def 		snake_case_   (	self	:      Union[str, Any]		):
           _UpperCAmelCase     :      Any														=       []
           _UpperCAmelCase     :      str														=       []
           _UpperCAmelCase     :      Optional[Any]														=       list(self.graph		)[0]
           stack.append(A		)
           visited.append(A		)
           _UpperCAmelCase     :      Dict														=       -2
           _UpperCAmelCase     :      Union[str, Any]														=       []
           _UpperCAmelCase     :      Optional[Any]														=       s
           _UpperCAmelCase     :      str														=       False
           _UpperCAmelCase     :      Optional[Any]														=       set()

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

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

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



      def 		snake_case_   (	self	:      str		):
           _UpperCAmelCase     :      str														=       []
           _UpperCAmelCase     :      str														=       []
           _UpperCAmelCase     :      Optional[int]														=       list(self.graph		)[0]
           stack.append(A		)
           visited.append(A		)
           _UpperCAmelCase     :      str														=       -2
           _UpperCAmelCase     :      List[Any]														=       []
           _UpperCAmelCase     :      List[Any]														=       s
           _UpperCAmelCase     :      Union[str, Any]														=       False
           _UpperCAmelCase     :      Optional[int]														=       set()

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

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

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



      def 		snake_case_   (	self	:      Any	,      A	:      Optional[int]=-2	,      A	:      str=-1		):
           _UpperCAmelCase     :      List[str]														=       time()
           self.dfs(A	,      A		)
           _UpperCAmelCase     :      List[Any]														=       time()
           return end - begin



      def 		snake_case_   (	self	:      Union[str, Any]	,      A	:      Optional[Any]=-2		):
           _UpperCAmelCase     :      str														=       time()
           self.bfs(A		)
           _UpperCAmelCase     :      Union[str, Any]														=       time()
           return end - begin







class       UpperCAmelCase_    :



      def __init__(	self	:      int		):
           _UpperCAmelCase     :      Tuple														=       {}



      def 		snake_case_   (	self	:      Optional[int]	,      A	:      str	,      A	:      List[str]	,      A	:      str=1		):
           # check if the u exists
           if self.graph.get(A		):
                # 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     :      List[Any]														=       [[w, v]]
           # add the other way
           if self.graph.get(A		):
                # 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     :      Union[str, Any]														=       [[w, u]]



      def 		snake_case_   (	self	:      Dict	,      A	:      Any	,      A	:      int		):
           if self.graph.get(A		):
                for _ in self.graph[u]:
                     if _[1] == v:
                          self.graph[u].remove(A		)
        # the other way round
           if self.graph.get(A		):
                for _ in self.graph[v]:
                     if _[1] == u:
                          self.graph[v].remove(A		)



      def 		snake_case_   (	self	:      List[Any]	,      A	:      Dict=-2	,      A	:      Optional[int]=-1		):
           if s == d:
                return []
           _UpperCAmelCase     :      str														=       []
           _UpperCAmelCase     :      List[Any]														=       []
           if s == -2:
                _UpperCAmelCase     :      Tuple														=       list(self.graph		)[0]
           stack.append(A		)
           visited.append(A		)
           _UpperCAmelCase     :      List[str]														=       s

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

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

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



      def 		snake_case_   (	self	:      Any	,      A	:      str=-1		):
           if c == -1:
                _UpperCAmelCase     :      Tuple														=       floor(random() * 1_0_0_0_0		) + 1_0
           for i in range(A		):
                # every vertex has max 100 edges
                for _ in range(floor(random() * 1_0_2		) + 1		):
                     _UpperCAmelCase     :      List[str]														=       floor(random() * c		) + 1
                     if n != i:
                          self.add_pair(A	,      A	,      1		)



      def 		snake_case_   (	self	:      Union[str, Any]	,      A	:      Tuple=-2		):
           _UpperCAmelCase     :      int														=       deque()
           _UpperCAmelCase     :      Dict														=       []
           if s == -2:
                _UpperCAmelCase     :      Dict														=       list(self.graph		)[0]
           d.append(A		)
           visited.append(A		)
           while d:
                _UpperCAmelCase     :      Dict														=       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 		snake_case_   (	self	:      List[str]	,      A	:      Dict		):
           return len(self.graph[u]		)



      def 		snake_case_   (	self	:      Tuple		):
           _UpperCAmelCase     :      int														=       []
           _UpperCAmelCase     :      Optional[int]														=       []
           _UpperCAmelCase     :      Optional[int]														=       list(self.graph		)[0]
           stack.append(A		)
           visited.append(A		)
           _UpperCAmelCase     :      int														=       -2
           _UpperCAmelCase     :      Optional[Any]														=       []
           _UpperCAmelCase     :      Any														=       s
           _UpperCAmelCase     :      Optional[int]														=       False
           _UpperCAmelCase     :      List[Any]														=       set()

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

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

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



      def 		snake_case_   (	self	:      Optional[int]		):
           _UpperCAmelCase     :      Tuple														=       []
           _UpperCAmelCase     :      Optional[Any]														=       []
           _UpperCAmelCase     :      List[str]														=       list(self.graph		)[0]
           stack.append(A		)
           visited.append(A		)
           _UpperCAmelCase     :      Dict														=       -2
           _UpperCAmelCase     :      str														=       []
           _UpperCAmelCase     :      Optional[int]														=       s
           _UpperCAmelCase     :      List[str]														=       False
           _UpperCAmelCase     :      List[str]														=       set()

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

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

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



      def 		snake_case_   (	self	:      List[Any]		):
           return list(self.graph		)



      def 		snake_case_   (	self	:      str	,      A	:      Optional[Any]=-2	,      A	:      Optional[int]=-1		):
           _UpperCAmelCase     :      Optional[int]														=       time()
           self.dfs(A	,      A		)
           _UpperCAmelCase     :      Union[str, Any]														=       time()
           return end - begin



      def 		snake_case_   (	self	:      str	,      A	:      Any=-2		):
           _UpperCAmelCase     :      Optional[int]														=       time()
           self.bfs(A		)
           _UpperCAmelCase     :      List[str]														=       time()
           return end - begin





"""simple docstring"""




def 		__snake_case		( SCREAMING_SNAKE_CASE__      :		str							)    ->  bool:





     '''simple docstring'''

     _UpperCAmelCase     :      str														=       0
     for ch in input_str:
          _UpperCAmelCase     :      Optional[int]														=       ord(SCREAMING_SNAKE_CASE__							)
          _UpperCAmelCase     :      int														=       pow(2		,    SCREAMING_SNAKE_CASE__							)

          # If we already turned on bit for current character's unicode
          if bitmap >> ch_unicode & 1 == 1:
               return False
          bitmap |= ch_bit_index_on
     return True


if __name__ == "__main__":
 import doctest

 doctest.testmod()
