






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





class   UpperCamelCase_ :



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



         """simple docstring"""





         UpperCAmelCase	    =			{}



  def 		UpperCamelCase_				(      self ,		snake_case__ ,		snake_case__ ,		snake_case__=1				)			->			List[Any]:



         """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 		UpperCamelCase_				(      self				)			->			str:



         """simple docstring"""





         return list(self.graph				)



  def 		UpperCamelCase_				(      self ,		snake_case__ ,		snake_case__				)			->			Dict:



         """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 		UpperCamelCase_				(      self ,		snake_case__=-2 ,		snake_case__=-1				)			->			Optional[Any]:



         """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 		UpperCamelCase_				(      self ,		snake_case__=-1				)			->			Optional[int]:



         """simple docstring"""





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



  def 		UpperCamelCase_				(      self ,		snake_case__=-2				)			->			Any:



         """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 		UpperCamelCase_				(      self ,		snake_case__				)			->			List[Any]:



         """simple docstring"""





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



  def 		UpperCamelCase_				(      self ,		snake_case__				)			->			List[str]:



         """simple docstring"""





         return len(self.graph[u]				)



  def 		UpperCamelCase_				(      self ,		snake_case__=-2				)			->			Union[str, Any]:



         """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 		UpperCamelCase_				(      self				)			->			str:



         """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 		UpperCamelCase_				(      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_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 		UpperCamelCase_				(      self ,		snake_case__=-2 ,		snake_case__=-1				)			->			List[str]:



         """simple docstring"""





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



  def 		UpperCamelCase_				(      self ,		snake_case__=-2				)			->			List[str]:



         """simple docstring"""





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





class   UpperCamelCase_ :



  def __init__(      self				)			->			Optional[Any]:



         """simple docstring"""





         UpperCAmelCase	    =			{}



  def 		UpperCamelCase_				(      self ,		snake_case__ ,		snake_case__ ,		snake_case__=1				)			->			List[str]:



         """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 		UpperCamelCase_				(      self ,		snake_case__ ,		snake_case__				)			->			Tuple:



         """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 		UpperCamelCase_				(      self ,		snake_case__=-2 ,		snake_case__=-1				)			->			int:



         """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 		UpperCamelCase_				(      self ,		snake_case__=-1				)			->			Optional[int]:



         """simple docstring"""





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



  def 		UpperCamelCase_				(      self ,		snake_case__=-2				)			->			List[str]:



         """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 		UpperCamelCase_				(      self ,		snake_case__				)			->			Union[str, Any]:



         """simple docstring"""





         return len(self.graph[u]				)



  def 		UpperCamelCase_				(      self				)			->			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 		UpperCamelCase_				(      self				)			->			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 		UpperCamelCase_				(      self				)			->			Optional[Any]:



         """simple docstring"""





         return list(self.graph				)



  def 		UpperCamelCase_				(      self ,		snake_case__=-2 ,		snake_case__=-1				)			->			str:



         """simple docstring"""





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



  def 		UpperCamelCase_				(      self ,		snake_case__=-2				)			->			Dict:



         """simple docstring"""





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








"""simple docstring"""







from typing import List, Optional, Union

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


lowerCAmelCase_	:    str            =      logging.get_logger(__name__)

lowerCAmelCase_	:    Optional[int]            =      {
    '''huggingface/time-series-transformer-tourism-monthly''': (
        '''https://huggingface.co/huggingface/time-series-transformer-tourism-monthly/resolve/main/config.json'''
    ),
    # See all TimeSeriesTransformer models at https://huggingface.co/models?filter=time_series_transformer
}





class   UpperCamelCase_ (       a_  ):
  _A       :					int				=	'time_series_transformer'
  _A       :					List[Any]				=	{
      'hidden_size': 'd_model',
      'num_attention_heads': 'encoder_attention_heads',
      'num_hidden_layers': 'encoder_layers',
  }



  def __init__(      self ,		snake_case__ = None ,		snake_case__ = None ,		snake_case__ = "student_t" ,		snake_case__ = "nll" ,		snake_case__ = 1 ,		snake_case__ = [1, 2, 3, 4, 5, 6, 7] ,		snake_case__ = "mean" ,		snake_case__ = 0 ,		snake_case__ = 0 ,		snake_case__ = 0 ,		snake_case__ = 0 ,		snake_case__ = None ,		snake_case__ = None ,		snake_case__ = 32 ,		snake_case__ = 32 ,		snake_case__ = 2 ,		snake_case__ = 2 ,		snake_case__ = 2 ,		snake_case__ = 2 ,		snake_case__ = True ,		snake_case__ = "gelu" ,		snake_case__ = 64 ,		snake_case__ = 0.1 ,		snake_case__ = 0.1 ,		snake_case__ = 0.1 ,		snake_case__ = 0.1 ,		snake_case__ = 0.1 ,		snake_case__ = 1_00 ,		snake_case__ = 0.02 ,		snake_case__=True ,		**snake_case__ ,		)			->			Union[str, Any]:



         """simple docstring"""





         UpperCAmelCase	    =			prediction_length
         UpperCAmelCase	    =			context_length or prediction_length
         UpperCAmelCase	    =			distribution_output
         UpperCAmelCase	    =			loss
         UpperCAmelCase	    =			input_size
         UpperCAmelCase	    =			num_time_features
         UpperCAmelCase	    =			lags_sequence
         UpperCAmelCase	    =			scaling
         UpperCAmelCase	    =			num_dynamic_real_features
         UpperCAmelCase	    =			num_static_real_features
         UpperCAmelCase	    =			num_static_categorical_features
         if cardinality and num_static_categorical_features > 0:
                if len(snake_case__				) != num_static_categorical_features:
                       raise ValueError(
                           """The cardinality should be a list of the same length as `num_static_categorical_features`"""				)
                UpperCAmelCase	    =			cardinality
         else:
                UpperCAmelCase	    =			[0]
         if embedding_dimension and num_static_categorical_features > 0:
                if len(snake_case__				) != num_static_categorical_features:
                       raise ValueError(
                           """The embedding dimension should be a list of the same length as `num_static_categorical_features`"""				)
                UpperCAmelCase	    =			embedding_dimension
         else:
                UpperCAmelCase	    =			[min(50 ,		(cat + 1) // 2				) for cat in self.cardinality]
         UpperCAmelCase	    =			num_parallel_samples

         # Transformer architecture configuration
         UpperCAmelCase	    =			input_size * len(snake_case__				) + self._number_of_features
         UpperCAmelCase	    =			d_model
         UpperCAmelCase	    =			encoder_attention_heads
         UpperCAmelCase	    =			decoder_attention_heads
         UpperCAmelCase	    =			encoder_ffn_dim
         UpperCAmelCase	    =			decoder_ffn_dim
         UpperCAmelCase	    =			encoder_layers
         UpperCAmelCase	    =			decoder_layers

         UpperCAmelCase	    =			dropout
         UpperCAmelCase	    =			attention_dropout
         UpperCAmelCase	    =			activation_dropout
         UpperCAmelCase	    =			encoder_layerdrop
         UpperCAmelCase	    =			decoder_layerdrop

         UpperCAmelCase	    =			activation_function
         UpperCAmelCase	    =			init_std

         UpperCAmelCase	    =			use_cache

         super().__init__(is_encoder_decoder=snake_case__ ,		**snake_case__				)



  @property
  def 		UpperCamelCase_				(      self				)			->			int:



         """simple docstring"""





         return (
             sum(self.embedding_dimension				)
             + self.num_dynamic_real_features
             + self.num_time_features
             + self.num_static_real_features
             + self.input_size * 2  # the log1p(abs(loc)) and log(scale) features
         )
