

"""simple docstring"""





from collections import OrderedDict
from typing import TYPE_CHECKING, Any, Mapping, Optional, Union

from ...configuration_utils import PretrainedConfig
from ...onnx import OnnxConfig, OnnxSeqaSeqConfigWithPast
from ...utils import logging


if TYPE_CHECKING:
							from ...feature_extraction_utils import FeatureExtractionMixin
							from ...tokenization_utils_base import PreTrainedTokenizerBase
							from ...utils import TensorType

__UpperCamelCase    : Optional[Any]				 =						logging.get_logger(__name__)

__UpperCamelCase    : Any				 =						{
    '''openai/whisper-base''': '''https://huggingface.co/openai/whisper-base/resolve/main/config.json''',
}

# fmt: off
__UpperCamelCase    : Dict				 =						[
    1, 2, 7, 8, 9, 1_0, 1_4, 2_5,
    2_6, 2_7, 2_8, 2_9, 3_1, 5_8, 5_9, 6_0, 6_1, 6_2,
    6_3, 9_0, 9_1, 9_2, 9_3, 3_5_7, 3_6_6, 4_3_8, 5_3_2, 6_8_5,
    7_0_5, 7_9_6, 9_3_0, 1_0_5_8, 1_2_2_0, 1_2_6_7, 1_2_7_9, 1_3_0_3, 1_3_4_3, 1_3_7_7,
    1_3_9_1, 1_6_3_5, 1_7_8_2, 1_8_7_5, 2_1_6_2, 2_3_6_1, 2_4_8_8, 3_4_6_7, 4_0_0_8, 4_2_1_1,
    4_6_0_0, 4_8_0_8, 5_2_9_9, 5_8_5_5, 6_3_2_9, 7_2_0_3, 9_6_0_9, 9_9_5_9, 1_0_5_6_3, 1_0_7_8_6,
    1_1_4_2_0, 1_1_7_0_9, 1_1_9_0_7, 1_3_1_6_3, 1_3_6_9_7, 1_3_7_0_0, 1_4_8_0_8, 1_5_3_0_6, 1_6_4_1_0, 1_6_7_9_1,
    1_7_9_9_2, 1_9_2_0_3, 1_9_5_1_0, 2_0_7_2_4, 2_2_3_0_5, 2_2_9_3_5, 2_7_0_0_7, 3_0_1_0_9, 3_0_4_2_0, 3_3_4_0_9,
    3_4_9_4_9, 4_0_2_8_3, 4_0_4_9_3, 4_0_5_4_9, 4_7_2_8_2, 4_9_1_4_6, 5_0_2_5_7, 5_0_3_5_9, 5_0_3_6_0, 5_0_3_6_1
]
__UpperCamelCase    : Optional[Any]				 =						[
    1, 2, 7, 8, 9, 1_0, 1_4, 2_5,
    2_6, 2_7, 2_8, 2_9, 3_1, 5_8, 5_9, 6_0, 6_1, 6_2,
    6_3, 9_0, 9_1, 9_2, 9_3, 3_5_9, 5_0_3, 5_2_2, 5_4_2, 8_7_3,
    8_9_3, 9_0_2, 9_1_8, 9_2_2, 9_3_1, 1_3_5_0, 1_8_5_3, 1_9_8_2, 2_4_6_0, 2_6_2_7,
    3_2_4_6, 3_2_5_3, 3_2_6_8, 3_5_3_6, 3_8_4_6, 3_9_6_1, 4_1_8_3, 4_6_6_7, 6_5_8_5, 6_6_4_7,
    7_2_7_3, 9_0_6_1, 9_3_8_3, 1_0_4_2_8, 1_0_9_2_9, 1_1_9_3_8, 1_2_0_3_3, 1_2_3_3_1, 1_2_5_6_2, 1_3_7_9_3,
    1_4_1_5_7, 1_4_6_3_5, 1_5_2_6_5, 1_5_6_1_8, 1_6_5_5_3, 1_6_6_0_4, 1_8_3_6_2, 1_8_9_5_6, 2_0_0_7_5, 2_1_6_7_5,
    2_2_5_2_0, 2_6_1_3_0, 2_6_1_6_1, 2_6_4_3_5, 2_8_2_7_9, 2_9_4_6_4, 3_1_6_5_0, 3_2_3_0_2, 3_2_4_7_0, 3_6_8_6_5,
    4_2_8_6_3, 4_7_4_2_5, 4_9_8_7_0, 5_0_2_5_4, 5_0_2_5_8, 5_0_3_6_0, 5_0_3_6_1, 5_0_3_6_2
]







class 							SCREAMING_SNAKE_CASE   (						a_			):






					"""simple docstring"""



					lowercase__												=			"whisper"
					lowercase__												=			["past_key_values"]
					lowercase__												=			{"num_attention_heads": "encoder_attention_heads", "hidden_size": "d_model"}







					def __init__(			self     :							List[str]  ,lowercase_     :							Optional[Any]=5_1_8_6_5  ,lowercase_     :							Tuple=8_0  ,lowercase_     :							Tuple=6  ,lowercase_     :							List[str]=4  ,lowercase_     :							int=6  ,lowercase_     :							Tuple=4  ,lowercase_     :							Any=1_5_3_6  ,lowercase_     :							Optional[int]=1_5_3_6  ,lowercase_     :							Tuple=0.0  ,lowercase_     :							str=0.0  ,lowercase_     :							int=5_0_2_5_7  ,lowercase_     :							str=True  ,lowercase_     :							Dict=True  ,lowercase_     :							List[Any]="gelu"  ,lowercase_     :							Tuple=2_5_6  ,lowercase_     :							List[str]=0.0  ,lowercase_     :							Dict=0.0  ,lowercase_     :							List[str]=0.0  ,lowercase_     :							Union[str, Any]=0.02  ,lowercase_     :							Any=False  ,lowercase_     :							int=1_5_0_0  ,lowercase_     :							Union[str, Any]=4_4_8  ,lowercase_     :							Union[str, Any]=5_0_2_5_6  ,lowercase_     :							Union[str, Any]=5_0_2_5_6  ,lowercase_     :							Tuple=5_0_2_5_6  ,lowercase_     :							Union[str, Any]=None  ,lowercase_     :							str=[2_2_0, 5_0_2_5_6]  ,lowercase_     :							Dict=False  ,lowercase_     :							Union[str, Any]=2_5_6  ,lowercase_     :							List[str]=False  ,lowercase_     :							Any=0.05  ,lowercase_     :							Optional[Any]=1_0  ,lowercase_     :							List[Any]=2  ,lowercase_     :							Optional[int]=0.0  ,lowercase_     :							Any=1_0  ,lowercase_     :							int=0  ,lowercase_     :							Optional[Any]=7  ,**lowercase_     :							int  ,):
						lowerCAmelCase__      :		Dict    							=      vocab_size
						lowerCAmelCase__      :		Any    							=      num_mel_bins
						lowerCAmelCase__      :		Optional[int]    							=      d_model
						lowerCAmelCase__      :		Dict    							=      encoder_layers
						lowerCAmelCase__      :		str    							=      encoder_attention_heads
						lowerCAmelCase__      :		Optional[Any]    							=      decoder_layers
						lowerCAmelCase__      :		int    							=      decoder_attention_heads
						lowerCAmelCase__      :		List[str]    							=      decoder_ffn_dim
						lowerCAmelCase__      :		int    							=      encoder_ffn_dim
						lowerCAmelCase__      :		List[str]    							=      dropout
						lowerCAmelCase__      :		Optional[Any]    							=      attention_dropout
						lowerCAmelCase__      :		Dict    							=      activation_dropout
						lowerCAmelCase__      :		Any    							=      activation_function
						lowerCAmelCase__      :		Union[str, Any]    							=      init_std
						lowerCAmelCase__      :		str    							=      encoder_layerdrop
						lowerCAmelCase__      :		List[Any]    							=      decoder_layerdrop
						lowerCAmelCase__      :		Optional[int]    							=      use_cache
						lowerCAmelCase__      :		Optional[int]    							=      encoder_layers
						lowerCAmelCase__      :		Union[str, Any]    							=      scale_embedding  # scale factor will be sqrt(d_model) if True
						lowerCAmelCase__      :		Union[str, Any]    							=      max_source_positions
						lowerCAmelCase__      :		Optional[int]    							=      max_target_positions

						# Audio Classification-specific parameters. Feel free to ignore for other classes.
						lowerCAmelCase__      :		str    							=      classifier_proj_size
						lowerCAmelCase__      :		str    							=      use_weighted_layer_sum

						# fine-tuning config parameters for SpecAugment: https://arxiv.org/abs/1904.08779
						lowerCAmelCase__      :		Optional[int]    							=      apply_spec_augment
						lowerCAmelCase__      :		Union[str, Any]    							=      mask_time_prob
						lowerCAmelCase__      :		Any    							=      mask_time_length
						lowerCAmelCase__      :		Dict    							=      mask_time_min_masks
						lowerCAmelCase__      :		Union[str, Any]    							=      mask_feature_prob
						lowerCAmelCase__      :		Optional[Any]    							=      mask_feature_length
						lowerCAmelCase__      :		List[Any]    							=      mask_feature_min_masks

						lowerCAmelCase__      :		Tuple    							=      median_filter_width

						super().__init__(
						    pad_token_id=lowercase_  ,bos_token_id=lowercase_  ,eos_token_id=lowercase_  ,is_encoder_decoder=lowercase_  ,decoder_start_token_id=lowercase_  ,suppress_tokens=lowercase_  ,begin_suppress_tokens=lowercase_  ,**lowercase_  ,)







class 							SCREAMING_SNAKE_CASE   (						a_			):






					"""simple docstring"""



					@property
					def 			__lowerCAmelCase					(			self     :							str						):
						lowerCAmelCase__      :		List[Any]    							=      OrderedDict(
						    [
						        ('''input_features''', {0: '''batch''', 1: '''feature_size''', 2: '''encoder_sequence'''}),
						    ]						)
						if self.use_past:
							lowerCAmelCase__      :		Optional[int]    							=      {0: '''batch'''}
						else:
							lowerCAmelCase__      :		Optional[Any]    							=      {0: '''batch''', 1: '''decoder_sequence'''}

						if self.use_past:
							self.fill_with_past_key_values_(lowercase_  ,direction='''inputs'''						)

						return common_inputs







					def 			__lowerCAmelCase					(			self     :							int  ,lowercase_     :							Union["PreTrainedTokenizerBase", "FeatureExtractionMixin"]  ,lowercase_     :							int = -1  ,lowercase_     :							int = -1  ,lowercase_     :							bool = False  ,lowercase_     :							Optional["TensorType"] = None  ,lowercase_     :							int = 2_2_0_5_0  ,lowercase_     :							float = 5.0  ,lowercase_     :							int = 2_2_0  ,):
						lowerCAmelCase__      :		Optional[Any]    							=      OrderedDict()
						lowerCAmelCase__      :		int    							=      OnnxConfig.generate_dummy_inputs(
						    self  ,preprocessor=preprocessor.feature_extractor  ,batch_size=lowercase_  ,framework=lowercase_  ,sampling_rate=lowercase_  ,time_duration=lowercase_  ,frequency=lowercase_  ,)
						lowerCAmelCase__      :		Optional[int]    							=      encoder_inputs['''input_features'''].shape[2]
						lowerCAmelCase__      :		Dict    							=      encoder_sequence_length // 2 if self.use_past else seq_length

						lowerCAmelCase__      :		Any    							=      super().generate_dummy_inputs(
						    preprocessor.tokenizer  ,lowercase_  ,lowercase_  ,lowercase_  ,lowercase_						)

						lowerCAmelCase__      :		Optional[int]    							=      encoder_inputs.pop('''input_features'''						)
						lowerCAmelCase__      :		str    							=      decoder_inputs.pop('''decoder_input_ids'''						)

						if "past_key_values" in decoder_inputs:
							lowerCAmelCase__      :		Optional[Any]    							=      decoder_inputs.pop('''past_key_values'''						)

						return dummy_inputs







					@property
					def 			__lowerCAmelCase					(			self     :							List[Any]						):
						return 1E-3







"""simple docstring"""





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







class 							SCREAMING_SNAKE_CASE   :






					"""simple docstring"""



					def __init__(			self     :							Union[str, Any]						):
						lowerCAmelCase__      :		List[str]    							=      {}







					def 			__lowerCAmelCase					(			self     :							Optional[Any]  ,lowercase_     :							Optional[Any]  ,lowercase_     :							str  ,lowercase_     :							List[str]=1						):
						if self.graph.get(lowercase_						):
							if self.graph[u].count([w, v]						) == 0:
								self.graph[u].append([w, v]						)
						else:
							lowerCAmelCase__      :		Optional[int]    							=      [[w, v]]
						if not self.graph.get(lowercase_						):
							lowerCAmelCase__      :		Union[str, Any]    							=      []







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







					def 			__lowerCAmelCase					(			self     :							Dict  ,lowercase_     :							Tuple  ,lowercase_     :							Tuple						):
						if self.graph.get(lowercase_						):
							for _ in self.graph[u]:
								if _[1] == v:
									self.graph[u].remove(lowercase_						)







					def 			__lowerCAmelCase					(			self     :							int  ,lowercase_     :							Any=-2  ,lowercase_     :							List[Any]=-1						):
						if s == d:
							return []
						lowerCAmelCase__      :		int    							=      []
						lowerCAmelCase__      :		List[Any]    							=      []
						if s == -2:
							lowerCAmelCase__      :		int    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		int    							=      s

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

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

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







					def 			__lowerCAmelCase					(			self     :							Dict  ,lowercase_     :							Optional[Any]=-1						):
						if c == -1:
							lowerCAmelCase__      :		Any    							=      floor(random() * 1_0_0_0_0						) + 1_0
						for i in range(lowercase_						):
							# every vertex has max 100 edges
							for _ in range(floor(random() * 1_0_2						) + 1						):
								lowerCAmelCase__      :		Any    							=      floor(random() * c						) + 1
								if n != i:
									self.add_pair(lowercase_  ,lowercase_  ,1						)







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







					def 			__lowerCAmelCase					(			self     :							str  ,lowercase_     :							Optional[int]						):
						return len(self.graph[u]						)







					def 			__lowerCAmelCase					(			self     :							List[str]  ,lowercase_     :							List[str]=-2						):
						lowerCAmelCase__      :		Union[str, Any]    							=      []
						lowerCAmelCase__      :		Any    							=      []
						if s == -2:
							lowerCAmelCase__      :		Any    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		Tuple    							=      s
						lowerCAmelCase__      :		Optional[int]    							=      []

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

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

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







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

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

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

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







					def 			__lowerCAmelCase					(			self     :							int						):
						lowerCAmelCase__      :		Tuple    							=      []
						lowerCAmelCase__      :		Tuple    							=      []
						lowerCAmelCase__      :		Any    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		List[str]    							=      -2
						lowerCAmelCase__      :		int    							=      []
						lowerCAmelCase__      :		int    							=      s
						lowerCAmelCase__      :		List[Any]    							=      False
						lowerCAmelCase__      :		List[str]    							=      set()

						while True:
							# check if there is any non isolated nodes
							if len(self.graph[s]						) != 0:
								lowerCAmelCase__      :		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
									):
										lowerCAmelCase__      :		List[Any]    							=      len(lowercase_						) - 1
										while len_stack_minus_one >= 0:
											if stack[len_stack_minus_one] == node[1]:
												anticipating_nodes.add(node[1]						)
												break
											else:
												return True
									if visited.count(node[1]						) < 1:
										stack.append(node[1]						)
										visited.append(node[1]						)
										lowerCAmelCase__      :		Optional[Any]    							=      node[1]
										break

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

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







					def 			__lowerCAmelCase					(			self     :							Any  ,lowercase_     :							List[Any]=-2  ,lowercase_     :							Union[str, Any]=-1						):
						lowerCAmelCase__      :		Optional[int]    							=      time()
						self.dfs(lowercase_  ,lowercase_						)
						lowerCAmelCase__      :		Any    							=      time()
						return end - begin







					def 			__lowerCAmelCase					(			self     :							Any  ,lowercase_     :							Dict=-2						):
						lowerCAmelCase__      :		List[str]    							=      time()
						self.bfs(lowercase_						)
						lowerCAmelCase__      :		List[Any]    							=      time()
						return end - begin







class 							SCREAMING_SNAKE_CASE   :






					"""simple docstring"""



					def __init__(			self     :							Union[str, Any]						):
						lowerCAmelCase__      :		Tuple    							=      {}







					def 			__lowerCAmelCase					(			self     :							List[Any]  ,lowercase_     :							Optional[int]  ,lowercase_     :							Dict  ,lowercase_     :							Any=1						):
						# check if the u exists
						if self.graph.get(lowercase_						):
							# if there already is a edge
							if self.graph[u].count([w, v]						) == 0:
								self.graph[u].append([w, v]						)
						else:
							# if u does not exist
							lowerCAmelCase__      :		List[Any]    							=      [[w, v]]
						# add the other way
						if self.graph.get(lowercase_						):
							# if there already is a edge
							if self.graph[v].count([w, u]						) == 0:
								self.graph[v].append([w, u]						)
						else:
							# if u does not exist
							lowerCAmelCase__      :		int    							=      [[w, u]]







					def 			__lowerCAmelCase					(			self     :							Dict  ,lowercase_     :							Union[str, Any]  ,lowercase_     :							Dict						):
						if self.graph.get(lowercase_						):
							for _ in self.graph[u]:
								if _[1] == v:
									self.graph[u].remove(lowercase_						)
        # the other way round
						if self.graph.get(lowercase_						):
							for _ in self.graph[v]:
								if _[1] == u:
									self.graph[v].remove(lowercase_						)







					def 			__lowerCAmelCase					(			self     :							int  ,lowercase_     :							Optional[int]=-2  ,lowercase_     :							str=-1						):
						if s == d:
							return []
						lowerCAmelCase__      :		Optional[Any]    							=      []
						lowerCAmelCase__      :		Any    							=      []
						if s == -2:
							lowerCAmelCase__      :		Tuple    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		int    							=      s

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

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

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







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







					def 			__lowerCAmelCase					(			self     :							Optional[Any]  ,lowercase_     :							List[Any]=-2						):
						lowerCAmelCase__      :		Tuple    							=      deque()
						lowerCAmelCase__      :		List[Any]    							=      []
						if s == -2:
							lowerCAmelCase__      :		Tuple    							=      list(self.graph						)[0]
						d.append(lowercase_						)
						visited.append(lowercase_						)
						while d:
							lowerCAmelCase__      :		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 			__lowerCAmelCase					(			self     :							Any  ,lowercase_     :							Any						):
						return len(self.graph[u]						)







					def 			__lowerCAmelCase					(			self     :							Any						):
						lowerCAmelCase__      :		List[Any]    							=      []
						lowerCAmelCase__      :		int    							=      []
						lowerCAmelCase__      :		List[Any]    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		Optional[int]    							=      -2
						lowerCAmelCase__      :		List[str]    							=      []
						lowerCAmelCase__      :		Tuple    							=      s
						lowerCAmelCase__      :		Tuple    							=      False
						lowerCAmelCase__      :		Union[str, Any]    							=      set()

						while True:
							# check if there is any non isolated nodes
							if len(self.graph[s]						) != 0:
								lowerCAmelCase__      :		Union[str, 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
									):
										lowerCAmelCase__      :		Tuple    							=      len(lowercase_						) - 1
										while len_stack >= 0:
											if stack[len_stack] == node[1]:
												anticipating_nodes.add(node[1]						)
												break
											else:
												anticipating_nodes.add(stack[len_stack]						)
												len_stack -= 1
									if visited.count(node[1]						) < 1:
										stack.append(node[1]						)
										visited.append(node[1]						)
										lowerCAmelCase__      :		Optional[int]    							=      node[1]
										break

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

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







					def 			__lowerCAmelCase					(			self     :							Optional[Any]						):
						lowerCAmelCase__      :		Optional[Any]    							=      []
						lowerCAmelCase__      :		Union[str, Any]    							=      []
						lowerCAmelCase__      :		Tuple    							=      list(self.graph						)[0]
						stack.append(lowercase_						)
						visited.append(lowercase_						)
						lowerCAmelCase__      :		Dict    							=      -2
						lowerCAmelCase__      :		Union[str, Any]    							=      []
						lowerCAmelCase__      :		Optional[Any]    							=      s
						lowerCAmelCase__      :		Any    							=      False
						lowerCAmelCase__      :		Optional[int]    							=      set()

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

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

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







					def 			__lowerCAmelCase					(			self     :							str						):
						return list(self.graph						)







					def 			__lowerCAmelCase					(			self     :							Any  ,lowercase_     :							Optional[int]=-2  ,lowercase_     :							Any=-1						):
						lowerCAmelCase__      :		Dict    							=      time()
						self.dfs(lowercase_  ,lowercase_						)
						lowerCAmelCase__      :		List[str]    							=      time()
						return end - begin







					def 			__lowerCAmelCase					(			self     :							Union[str, Any]  ,lowercase_     :							int=-2						):
						lowerCAmelCase__      :		Dict    							=      time()
						self.bfs(lowercase_						)
						lowerCAmelCase__      :		Any    							=      time()
						return end - begin




