





'''simple docstring'''

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







class __a			:





   def __init__(       self					:      Tuple     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							{}





   def   UpperCAmelCase__  (       self					:      Optional[Any]					,lowerCamelCase					:      List[Any]					,lowerCamelCase					:      Dict					,lowerCamelCase					:      Optional[Any]=1     ):

      '''simple docstring'''

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





   def   UpperCAmelCase__  (       self					:      Optional[int]     ):

      '''simple docstring'''

      return list(self.graph     )





   def   UpperCAmelCase__  (       self					:      Optional[Any]					,lowerCamelCase					:      Tuple					,lowerCamelCase					:      Optional[Any]     ):

      '''simple docstring'''

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





   def   UpperCAmelCase__  (       self					:      Tuple					,lowerCamelCase					:      Any=-2					,lowerCamelCase					:      Optional[Any]=-1     ):

      '''simple docstring'''

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

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

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

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





   def   UpperCAmelCase__  (       self					:      str					,lowerCamelCase					:      str=-1     ):

      '''simple docstring'''

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





   def   UpperCAmelCase__  (       self					:      Any					,lowerCamelCase					:      str=-2     ):

      '''simple docstring'''

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





   def   UpperCAmelCase__  (       self					:      Union[str, Any]					,lowerCamelCase					:      Dict     ):

      '''simple docstring'''

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





   def   UpperCAmelCase__  (       self					:      List[Any]					,lowerCamelCase					:      Optional[int]     ):

      '''simple docstring'''

      return len(self.graph[u]     )





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

      '''simple docstring'''

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

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

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

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





   def   UpperCAmelCase__  (       self					:      Any     ):

      '''simple docstring'''

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

      while True:
         # check if there is any non isolated nodes
         if len(self.graph[s]     ) != 0:
            __SCREAMING_SNAKE_CASE   				=							s
            for node in self.graph[s]:
               if (
                   visited.count(node[1]     ) > 0
                   and node[1] != parent
                   and indirect_parents.count(node[1]     ) > 0
                   and not on_the_way_back
               ):
                  __SCREAMING_SNAKE_CASE   				=							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]     )
                  __SCREAMING_SNAKE_CASE   				=							node[1]
                  break

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

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





   def   UpperCAmelCase__  (       self					:      Tuple     ):

      '''simple docstring'''

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

      while True:
         # check if there is any non isolated nodes
         if len(self.graph[s]     ) != 0:
            __SCREAMING_SNAKE_CASE   				=							s
            for node in self.graph[s]:
               if (
                   visited.count(node[1]     ) > 0
                   and node[1] != parent
                   and indirect_parents.count(node[1]     ) > 0
                   and not on_the_way_back
               ):
                  __SCREAMING_SNAKE_CASE   				=							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]     )
                  __SCREAMING_SNAKE_CASE   				=							node[1]
                  break

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

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





   def   UpperCAmelCase__  (       self					:      Any					,lowerCamelCase					:      Dict=-2					,lowerCamelCase					:      Any=-1     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							time()
      self.dfs(lowerCamelCase					,lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							time()
      return end - begin





   def   UpperCAmelCase__  (       self					:      Tuple					,lowerCamelCase					:      Any=-2     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							time()
      self.bfs(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							time()
      return end - begin







class __a			:





   def __init__(       self					:      Tuple     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							{}





   def   UpperCAmelCase__  (       self					:      str					,lowerCamelCase					:      Any					,lowerCamelCase					:      Optional[int]					,lowerCamelCase					:      int=1     ):

      '''simple docstring'''

      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
         __SCREAMING_SNAKE_CASE   				=							[[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
         __SCREAMING_SNAKE_CASE   				=							[[w, u]]





   def   UpperCAmelCase__  (       self					:      Dict					,lowerCamelCase					:      str					,lowerCamelCase					:      Union[str, Any]     ):

      '''simple docstring'''

      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					:      List[str]					,lowerCamelCase					:      Any=-2					,lowerCamelCase					:      Tuple=-1     ):

      '''simple docstring'''

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

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

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

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





   def   UpperCAmelCase__  (       self					:      Union[str, Any]					,lowerCamelCase					:      List[str]=-1     ):

      '''simple docstring'''

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





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

      '''simple docstring'''

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





   def   UpperCAmelCase__  (       self					:      Optional[int]					,lowerCamelCase					:      Optional[Any]     ):

      '''simple docstring'''

      return len(self.graph[u]     )





   def   UpperCAmelCase__  (       self					:      Dict     ):

      '''simple docstring'''

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

      while True:
         # check if there is any non isolated nodes
         if len(self.graph[s]     ) != 0:
            __SCREAMING_SNAKE_CASE   				=							s
            for node in self.graph[s]:
               if (
                   visited.count(node[1]     ) > 0
                   and node[1] != parent
                   and indirect_parents.count(node[1]     ) > 0
                   and not on_the_way_back
               ):
                  __SCREAMING_SNAKE_CASE   				=							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]     )
                  __SCREAMING_SNAKE_CASE   				=							node[1]
                  break

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

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





   def   UpperCAmelCase__  (       self					:      Dict     ):

      '''simple docstring'''

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

      while True:
         # check if there is any non isolated nodes
         if len(self.graph[s]     ) != 0:
            __SCREAMING_SNAKE_CASE   				=							s
            for node in self.graph[s]:
               if (
                   visited.count(node[1]     ) > 0
                   and node[1] != parent
                   and indirect_parents.count(node[1]     ) > 0
                   and not on_the_way_back
               ):
                  __SCREAMING_SNAKE_CASE   				=							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]     )
                  __SCREAMING_SNAKE_CASE   				=							node[1]
                  break

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

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





   def   UpperCAmelCase__  (       self					:      str     ):

      '''simple docstring'''

      return list(self.graph     )





   def   UpperCAmelCase__  (       self					:      str					,lowerCamelCase					:      int=-2					,lowerCamelCase					:      List[str]=-1     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							time()
      self.dfs(lowerCamelCase					,lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							time()
      return end - begin





   def   UpperCAmelCase__  (       self					:      Tuple					,lowerCamelCase					:      List[str]=-2     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							time()
      self.bfs(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							time()
      return end - begin







"""simple docstring"""

from ...configuration_utils import PretrainedConfig
from ...utils import logging


SCREAMING_SNAKE_CASE_            =    logging.get_logger(__name__)

SCREAMING_SNAKE_CASE_            =    {
    '''tiiuae/falcon-40b''': '''https://huggingface.co/tiiuae/falcon-40b/resolve/main/config.json''',
    '''tiiuae/falcon-7b''': '''https://huggingface.co/tiiuae/falcon-7b/resolve/main/config.json''',
}
class   _UpperCAmelCase				(		SCREAMING_SNAKE_CASE_				):
      __SCREAMING_SNAKE_CASE :				Optional[Any]				   =						"falcon"
      __SCREAMING_SNAKE_CASE :				List[Any]				   =						["past_key_values"]




      def __init__(				self ,							lowercase_=6_5_0_2_4 ,							lowercase_=4_5_4_4 ,							lowercase_=3_2 ,							lowercase_=7_1 ,							lowercase_=1E-5 ,							lowercase_=0.0_2 ,							lowercase_=True ,							lowercase_=0.0 ,							lowercase_=0.0 ,							lowercase_=None ,							lowercase_=False ,							lowercase_=False ,							lowercase_=True ,							lowercase_=True ,							lowercase_=False ,							lowercase_=1_1 ,							lowercase_=1_1 ,							**lowercase_ ,							)    ->       Any:
          UpperCAmelCase          =       vocab_size
          # Backward compatibility with n_embed kwarg
          UpperCAmelCase          =       kwargs.pop('n_embed' ,							lowercase_				)
          UpperCAmelCase          =       hidden_size if n_embed is None else n_embed
          UpperCAmelCase          =       num_hidden_layers
          UpperCAmelCase          =       num_attention_heads
          UpperCAmelCase          =       layer_norm_epsilon
          UpperCAmelCase          =       initializer_range
          UpperCAmelCase          =       use_cache
          UpperCAmelCase          =       hidden_dropout
          UpperCAmelCase          =       attention_dropout

          UpperCAmelCase          =       bos_token_id
          UpperCAmelCase          =       eos_token_id
          UpperCAmelCase          =       num_attention_heads if num_kv_heads is None else num_kv_heads
          UpperCAmelCase          =       alibi
          UpperCAmelCase          =       new_decoder_architecture
          UpperCAmelCase          =       multi_query  # Ignored when new_decoder_architecture is True
          UpperCAmelCase          =       parallel_attn
          UpperCAmelCase          =       bias

          super().__init__(bos_token_id=lowercase_ ,							eos_token_id=lowercase_ ,							**lowercase_				)




      @property
      def      a_   (				self				)    ->       List[Any]:
          return self.hidden_size // self.num_attention_heads




      @property
      def      a_   (				self				)    ->       List[str]:
          return not self.alibi



