


import enum
import warnings

from ..tokenization_utils import TruncationStrategy
from ..utils import add_end_docstrings, is_tf_available, is_torch_available, logging
from .base import PIPELINE_INIT_ARGS, Pipeline


if is_tf_available():
 import tensorflow as tf

 from ..models.auto.modeling_tf_auto import TF_MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING

if is_torch_available():
 from ..models.auto.modeling_auto import MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING

__lowerCAmelCase			=							logging.get_logger(__name__)





class   __a      (   enum.Enum				):
 __lowercase			:							str       					=			0
 __lowercase			:							Union[str, Any]       					=			1





@add_end_docstrings(__UpperCamelCase				)
class   __a      (   __UpperCamelCase				):
 __lowercase			:							str       					=			'generated'
 def __init__(       self    ,			*lowerCAmelCase__    ,			**lowerCAmelCase__			) ->    int:




        '''simple docstring'''
        super().__init__(*lowerCAmelCase__    ,			**lowerCAmelCase__			)

        self.check_model_type(
            TF_MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING
            if self.framework == 'tf'
            else MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=None    ,			lowerCAmelCase__=None    ,			lowerCAmelCase__=None    ,			lowerCAmelCase__=None    ,			lowerCAmelCase__=None    ,			lowerCAmelCase__=None    ,			**lowerCAmelCase__    ,			) ->    Optional[int]:




        '''simple docstring'''
        lowercase__:       str        =       {}
        if truncation is not None:
               lowercase__:       List[Any]        =       truncation

        lowercase__:       List[Any]        =       generate_kwargs

        lowercase__:       Dict        =       {}
        if return_tensors is not None and return_type is None:
               lowercase__:       List[str]        =       ReturnType.TENSORS if return_tensors else ReturnType.TEXT
        if return_type is not None:
               lowercase__:       Union[str, Any]        =       return_type

        if clean_up_tokenization_spaces is not None:
               lowercase__:       Optional[Any]        =       clean_up_tokenization_spaces

        if stop_sequence is not None:
               lowercase__:       Union[str, Any]        =       self.tokenizer.encode(lowerCAmelCase__    ,			add_special_tokens=lowerCAmelCase__			)
               if len(lowerCAmelCase__			) > 1:
                      warnings.warn(
                          'Stopping on a multiple token sequence is not yet supported on transformers. The first token of'
                          ' the stop sequence will be used as the stop sequence string in the interim.'			)
               lowercase__:       Optional[int]        =       stop_sequence_ids[0]

        return preprocess_params, forward_params, postprocess_params
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__    ,			lowerCAmelCase__			) ->    Union[str, Any]:




        '''simple docstring'''
        return True
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			*lowerCAmelCase__    ,			lowerCAmelCase__			) ->    Dict:




        '''simple docstring'''
        lowercase__:       Tuple        =       self.model.config.prefix if self.model.config.prefix is not None else ''
        if isinstance(args[0]    ,			lowerCAmelCase__			):
               if self.tokenizer.pad_token_id is None:
                      raise ValueError('Please make sure that the tokenizer has a pad_token_id when using a batch input'			)
               lowercase__:       Dict        =       ([prefix + arg for arg in args[0]],)
               lowercase__:       Optional[int]        =       True

        elif isinstance(args[0]    ,			lowerCAmelCase__			):
               lowercase__:       Tuple        =       (prefix + args[0],)
               lowercase__:       str        =       False
        else:
               raise ValueError(
                   F' `args[0]`: {args[0]} have the wrong format. The should be either of type `str` or type `list`'			)
        lowercase__:       Optional[Any]        =       self.tokenizer(*lowerCAmelCase__    ,			padding=lowerCAmelCase__    ,			truncation=lowerCAmelCase__    ,			return_tensors=self.framework			)
        # This is produced by tokenizers but is an invalid generate kwargs
        if "token_type_ids" in inputs:
               del inputs["token_type_ids"]
        return inputs
 def __call__(       self    ,			*lowerCAmelCase__    ,			**lowerCAmelCase__			) ->    Dict:




        '''simple docstring'''
        lowercase__:       int        =       super().__call__(*lowerCAmelCase__    ,			**lowerCAmelCase__			)
        if (
            isinstance(args[0]    ,			lowerCAmelCase__			)
            and all(isinstance(lowerCAmelCase__    ,			lowerCAmelCase__			) for el in args[0]			)
            and all(len(lowerCAmelCase__			) == 1 for res in result			)
        ):
               return [res[0] for res in result]
        return result
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__=TruncationStrategy.DO_NOT_TRUNCATE    ,			**lowerCAmelCase__			) ->    Tuple:




        '''simple docstring'''
        lowercase__:       int        =       self._parse_and_tokenize(lowerCAmelCase__    ,			truncation=lowerCAmelCase__    ,			**lowerCAmelCase__			)
        return inputs
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			**lowerCAmelCase__			) ->    Any:




        '''simple docstring'''
        if self.framework == "pt":
               lowercase__      ,						lowercase__:       Any        =       model_inputs['input_ids'].shape
        elif self.framework == "tf":
               lowercase__      ,						lowercase__:       int        =       tf.shape(model_inputs['input_ids']			).numpy()

        lowercase__:       Dict        =       generate_kwargs.get('min_length'    ,			self.model.config.min_length			)
        lowercase__:       List[str]        =       generate_kwargs.get('max_length'    ,			self.model.config.max_length			)
        self.check_inputs(lowerCAmelCase__    ,			generate_kwargs['min_length']    ,			generate_kwargs['max_length']			)
        lowercase__:       Dict        =       self.model.generate(**lowerCAmelCase__    ,			**lowerCAmelCase__			)
        lowercase__:       int        =       output_ids.shape[0]
        if self.framework == "pt":
               lowercase__:       List[Any]        =       output_ids.reshape(lowerCAmelCase__    ,			out_b // in_b    ,			*output_ids.shape[1:]			)
        elif self.framework == "tf":
               lowercase__:       Any        =       tf.reshape(lowerCAmelCase__    ,			(in_b, out_b // in_b, *output_ids.shape[1:])			)
        return {"output_ids": output_ids}
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__=ReturnType.TEXT    ,			lowerCAmelCase__=False			) ->    Tuple:




        '''simple docstring'''
        lowercase__:       Any        =       []
        for output_ids in model_outputs["output_ids"][0]:
               if return_type == ReturnType.TENSORS:
                      lowercase__:       Tuple        =       {F'{self.return_name}_token_ids': output_ids}
               elif return_type == ReturnType.TEXT:
                      lowercase__:       List[str]        =       {
                          F'{self.return_name}_text': self.tokenizer.decode(
                              lowerCAmelCase__    ,			skip_special_tokens=lowerCAmelCase__    ,			clean_up_tokenization_spaces=lowerCAmelCase__    ,			)
                      }
               records.append(lowerCAmelCase__			)
        return records





@add_end_docstrings(__UpperCamelCase				)
class   __a      (   __UpperCamelCase				):
 __lowercase			:							Any       					=			'summary'
 def __call__(       self    ,			*lowerCAmelCase__    ,			**lowerCAmelCase__			) ->    List[str]:




        '''simple docstring'''
        return super().__call__(*lowerCAmelCase__    ,			**lowerCAmelCase__			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__    ,			lowerCAmelCase__			) ->    bool:




        '''simple docstring'''
        if max_length < min_length:
               logger.warning(F'Your min_length={min_length} must be inferior than your max_length={max_length}.'			)

        if input_length < max_length:
               logger.warning(
                   F'Your max_length is set to {max_length}, but your input_length is only {input_length}. Since this is '
                   'a summarization task, where outputs shorter than the input are typically wanted, you might '
                   F'consider decreasing max_length manually, e.g. summarizer(\'...\', max_length={input_length//2})'			)





@add_end_docstrings(__UpperCamelCase				)
class   __a      (   __UpperCamelCase				):
 __lowercase			:							Tuple       					=			'translation'
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__    ,			lowerCAmelCase__			) ->    Optional[Any]:




        '''simple docstring'''
        if input_length > 0.9 * max_length:
               logger.warning(
                   F'Your input_length: {input_length} is bigger than 0.9 * max_length: {max_length}. You might consider '
                   'increasing your max_length manually, e.g. translator(\'...\', max_length=400)'			)
        return True
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			*lowerCAmelCase__    ,			lowerCAmelCase__=TruncationStrategy.DO_NOT_TRUNCATE    ,			lowerCAmelCase__=None    ,			lowerCAmelCase__=None			) ->    Tuple:




        '''simple docstring'''
        if getattr(self.tokenizer    ,			'_build_translation_inputs'    ,			lowerCAmelCase__			):
               return self.tokenizer._build_translation_inputs(
                   *lowerCAmelCase__    ,			return_tensors=self.framework    ,			truncation=lowerCAmelCase__    ,			src_lang=lowerCAmelCase__    ,			tgt_lang=lowerCAmelCase__			)
        else:
               return super()._parse_and_tokenize(*lowerCAmelCase__    ,			truncation=lowerCAmelCase__			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=None    ,			lowerCAmelCase__=None    ,			**lowerCAmelCase__			) ->    List[Any]:




        '''simple docstring'''
        lowercase__      ,						lowercase__      ,						lowercase__:       List[str]        =       super()._sanitize_parameters(**lowerCAmelCase__			)
        if src_lang is not None:
               lowercase__:       List[str]        =       src_lang
        if tgt_lang is not None:
               lowercase__:       Optional[Any]        =       tgt_lang
        if src_lang is None and tgt_lang is None:
               # Backward compatibility, direct arguments use is preferred.
               lowercase__:       Union[str, Any]        =       kwargs.get('task'    ,			self.task			)
               lowercase__:       Any        =       task.split('_'			)
               if task and len(lowerCAmelCase__			) == 4:
                      # translation, XX, to YY
                      lowercase__:       Dict        =       items[1]
                      lowercase__:       Optional[int]        =       items[3]
        return preprocess_params, forward_params, postprocess_params
 def __call__(       self    ,			*lowerCAmelCase__    ,			**lowerCAmelCase__			) ->    List[Any]:




        '''simple docstring'''
        return super().__call__(*lowerCAmelCase__    ,			**lowerCAmelCase__			)






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





class   __a      :
 def __init__(       self			) ->    Dict:




        '''simple docstring'''
        lowercase__:       Dict        =       {}
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__    ,			lowerCAmelCase__=1			) ->    Optional[int]:




        '''simple docstring'''
        if self.graph.get(lowerCAmelCase__			):
               if self.graph[u].count([w, v]			) == 0:
                      self.graph[u].append([w, v]			)
        else:
               lowercase__:       int        =       [[w, v]]
        if not self.graph.get(lowerCAmelCase__			):
               lowercase__:       Union[str, Any]        =       []
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    Any:




        '''simple docstring'''
        return list(self.graph			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__			) ->    Optional[int]:




        '''simple docstring'''
        if self.graph.get(lowerCAmelCase__			):
               for _ in self.graph[u]:
                      if _[1] == v:
                             self.graph[u].remove(lowerCAmelCase__			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2    ,			lowerCAmelCase__=-1			) ->    Union[str, Any]:




        '''simple docstring'''
        if s == d:
               return []
        lowercase__:       Tuple        =       []
        lowercase__:       Tuple        =       []
        if s == -2:
               lowercase__:       Any        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       Dict        =       s

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

            # check if all the children are visited
               if s == ss:
                      stack.pop()
                      if len(lowerCAmelCase__			) != 0:
                             lowercase__:       Optional[int]        =       stack[len(lowerCAmelCase__			) - 1]
               else:
                      lowercase__:       Dict        =       ss

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return visited
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-1			) ->    List[str]:




        '''simple docstring'''
        if c == -1:
               lowercase__:       int        =       floor(random() * 10_000			) + 10
        for i in range(lowerCAmelCase__			):
               # every vertex has max 100 edges
               for _ in range(floor(random() * 102			) + 1			):
                      lowercase__:       str        =       floor(random() * c			) + 1
                      if n != i:
                             self.add_pair(lowerCAmelCase__    ,			lowerCAmelCase__    ,			1			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2			) ->    Dict:




        '''simple docstring'''
        lowercase__:       int        =       deque()
        lowercase__:       Dict        =       []
        if s == -2:
               lowercase__:       Optional[int]        =       list(self.graph			)[0]
        d.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        while d:
               lowercase__:       str        =       d.popleft()
               if len(self.graph[s]			) != 0:
                      for node in self.graph[s]:
                             if visited.count(node[1]			) < 1:
                                    d.append(node[1]			)
                                    visited.append(node[1]			)
        return visited
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__			) ->    Dict:




        '''simple docstring'''
        lowercase__:       Tuple        =       0
        for x in self.graph:
               for y in self.graph[x]:
                      if y[1] == u:
                             count += 1
        return count
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__			) ->    Union[str, Any]:




        '''simple docstring'''
        return len(self.graph[u]			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2			) ->    Optional[Any]:




        '''simple docstring'''
        lowercase__:       Tuple        =       []
        lowercase__:       str        =       []
        if s == -2:
               lowercase__:       Dict        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       List[Any]        =       s
        lowercase__:       Any        =       []

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

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

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return sorted_nodes
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    Any:




        '''simple docstring'''
        lowercase__:       List[Any]        =       []
        lowercase__:       int        =       []
        lowercase__:       List[str]        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       Dict        =       -2
        lowercase__:       Union[str, Any]        =       []
        lowercase__:       List[str]        =       s
        lowercase__:       Dict        =       False
        lowercase__:       Union[str, Any]        =       set()

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

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

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return list(lowerCAmelCase__			)
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    Optional[Any]:




        '''simple docstring'''
        lowercase__:       Any        =       []
        lowercase__:       int        =       []
        lowercase__:       Dict        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       Optional[int]        =       -2
        lowercase__:       List[Any]        =       []
        lowercase__:       List[str]        =       s
        lowercase__:       List[Any]        =       False
        lowercase__:       str        =       set()

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

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

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return False
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2    ,			lowerCAmelCase__=-1			) ->    Dict:




        '''simple docstring'''
        lowercase__:       Union[str, Any]        =       time()
        self.dfs(lowerCAmelCase__    ,			lowerCAmelCase__			)
        lowercase__:       Optional[Any]        =       time()
        return end - begin
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2			) ->    List[str]:




        '''simple docstring'''
        lowercase__:       str        =       time()
        self.bfs(lowerCAmelCase__			)
        lowercase__:       List[str]        =       time()
        return end - begin





class   __a      :
 def __init__(       self			) ->    Tuple:




        '''simple docstring'''
        lowercase__:       Dict        =       {}
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__    ,			lowerCAmelCase__=1			) ->    List[Any]:




        '''simple docstring'''
        # 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
               lowercase__:       str        =       [[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
               lowercase__:       Union[str, Any]        =       [[w, u]]
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__			) ->    str:




        '''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 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2    ,			lowerCAmelCase__=-1			) ->    List[str]:




        '''simple docstring'''
        if s == d:
               return []
        lowercase__:       str        =       []
        lowercase__:       int        =       []
        if s == -2:
               lowercase__:       Tuple        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       int        =       s

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

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

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return visited
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-1			) ->    Optional[Any]:




        '''simple docstring'''
        if c == -1:
               lowercase__:       Any        =       floor(random() * 10_000			) + 10
        for i in range(lowerCAmelCase__			):
               # every vertex has max 100 edges
               for _ in range(floor(random() * 102			) + 1			):
                      lowercase__:       Optional[Any]        =       floor(random() * c			) + 1
                      if n != i:
                             self.add_pair(lowerCAmelCase__    ,			lowerCAmelCase__    ,			1			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2			) ->    List[Any]:




        '''simple docstring'''
        lowercase__:       str        =       deque()
        lowercase__:       List[Any]        =       []
        if s == -2:
               lowercase__:       str        =       list(self.graph			)[0]
        d.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        while d:
               lowercase__:       Union[str, Any]        =       d.popleft()
               if len(self.graph[s]			) != 0:
                      for node in self.graph[s]:
                             if visited.count(node[1]			) < 1:
                                    d.append(node[1]			)
                                    visited.append(node[1]			)
        return visited
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__			) ->    List[Any]:




        '''simple docstring'''
        return len(self.graph[u]			)
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    str:




        '''simple docstring'''
        lowercase__:       str        =       []
        lowercase__:       Dict        =       []
        lowercase__:       Optional[int]        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       Dict        =       -2
        lowercase__:       Dict        =       []
        lowercase__:       List[Any]        =       s
        lowercase__:       Union[str, Any]        =       False
        lowercase__:       List[str]        =       set()

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

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

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return list(lowerCAmelCase__			)
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    Any:




        '''simple docstring'''
        lowercase__:       Tuple        =       []
        lowercase__:       Optional[int]        =       []
        lowercase__:       Optional[Any]        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       Tuple        =       -2
        lowercase__:       Any        =       []
        lowercase__:       int        =       s
        lowercase__:       Optional[int]        =       False
        lowercase__:       List[Any]        =       set()

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

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

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return False
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    List[Any]:




        '''simple docstring'''
        return list(self.graph			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2    ,			lowerCAmelCase__=-1			) ->    Union[str, Any]:




        '''simple docstring'''
        lowercase__:       Dict        =       time()
        self.dfs(lowerCAmelCase__    ,			lowerCAmelCase__			)
        lowercase__:       List[Any]        =       time()
        return end - begin
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2			) ->    List[Any]:




        '''simple docstring'''
        lowercase__:       str        =       time()
        self.bfs(lowerCAmelCase__			)
        lowercase__:       List[str]        =       time()
        return end - begin


