


'''simple docstring'''


import argparse

import torch

from transformers import (
    SpeechTaConfig,
    SpeechTaFeatureExtractor,
    SpeechTaForSpeechToSpeech,
    SpeechTaForSpeechToText,
    SpeechTaForTextToSpeech,
    SpeechTaProcessor,
    SpeechTaTokenizer,
    logging,
)
from transformers.tokenization_utils import AddedToken


logging.set_verbosity_info()
lowerCamelCase__					=   logging.get_logger('transformers.models.speecht5')

lowerCamelCase__					=   {
    'speech_encoder_prenet.layer_norm': 'speecht5.encoder.prenet.feature_projection.layer_norm',
    'speech_encoder_prenet.post_extract_proj': 'speecht5.encoder.prenet.feature_projection.projection',
    'speech_encoder_prenet.pos_conv.0': 'speecht5.encoder.prenet.pos_conv_embed.conv',
    'speech_encoder_prenet.mask_emb': 'speecht5.encoder.prenet.masked_spec_embed',
}
lowerCamelCase__					=   {
    'text_encoder_prenet.encoder_prenet.0': 'speecht5.encoder.prenet.embed_tokens',
    'text_encoder_prenet.encoder_prenet.1.alpha': 'speecht5.encoder.prenet.encode_positions.alpha',
}
lowerCamelCase__					=   {
    'speech_decoder_prenet.decoder_prenet.0.0.prenet.0.0': 'speecht5.decoder.prenet.layers.0',
    'speech_decoder_prenet.decoder_prenet.0.0.prenet.1.0': 'speecht5.decoder.prenet.layers.1',
    'speech_decoder_prenet.decoder_prenet.0.1': 'speecht5.decoder.prenet.final_layer',
    'speech_decoder_prenet.decoder_prenet.1.alpha': 'speecht5.decoder.prenet.encode_positions.alpha',
    'speech_decoder_prenet.spkembs_layer.0': 'speecht5.decoder.prenet.speaker_embeds_layer',
}
lowerCamelCase__					=   {
    'speech_decoder_postnet.feat_out': 'speech_decoder_postnet.feat_out',
    'speech_decoder_postnet.prob_out': 'speech_decoder_postnet.prob_out',
    'speech_decoder_postnet.postnet.postnet.0.0': 'speech_decoder_postnet.layers.0.conv',
    'speech_decoder_postnet.postnet.postnet.0.1': 'speech_decoder_postnet.layers.0.batch_norm',
    'speech_decoder_postnet.postnet.postnet.1.0': 'speech_decoder_postnet.layers.1.conv',
    'speech_decoder_postnet.postnet.postnet.1.1': 'speech_decoder_postnet.layers.1.batch_norm',
    'speech_decoder_postnet.postnet.postnet.2.0': 'speech_decoder_postnet.layers.2.conv',
    'speech_decoder_postnet.postnet.postnet.2.1': 'speech_decoder_postnet.layers.2.batch_norm',
    'speech_decoder_postnet.postnet.postnet.3.0': 'speech_decoder_postnet.layers.3.conv',
    'speech_decoder_postnet.postnet.postnet.3.1': 'speech_decoder_postnet.layers.3.batch_norm',
    'speech_decoder_postnet.postnet.postnet.4.0': 'speech_decoder_postnet.layers.4.conv',
    'speech_decoder_postnet.postnet.postnet.4.1': 'speech_decoder_postnet.layers.4.batch_norm',
}
lowerCamelCase__					=   {
    'text_decoder_prenet.embed_tokens': 'speecht5.decoder.prenet.embed_tokens',
}
lowerCamelCase__					=   {
    'text_decoder_postnet.output_projection': 'text_decoder_postnet.lm_head',
}
lowerCamelCase__					=   {
    'encoder.layers.*.self_attn.k_proj': 'speecht5.encoder.wrapped_encoder.layers.*.attention.k_proj',
    'encoder.layers.*.self_attn.v_proj': 'speecht5.encoder.wrapped_encoder.layers.*.attention.v_proj',
    'encoder.layers.*.self_attn.q_proj': 'speecht5.encoder.wrapped_encoder.layers.*.attention.q_proj',
    'encoder.layers.*.self_attn.out_proj': 'speecht5.encoder.wrapped_encoder.layers.*.attention.out_proj',
    'encoder.layers.*.self_attn_layer_norm': 'speecht5.encoder.wrapped_encoder.layers.*.layer_norm',
    'encoder.layers.*.fc1': 'speecht5.encoder.wrapped_encoder.layers.*.feed_forward.intermediate_dense',
    'encoder.layers.*.fc2': 'speecht5.encoder.wrapped_encoder.layers.*.feed_forward.output_dense',
    'encoder.layers.*.final_layer_norm': 'speecht5.encoder.wrapped_encoder.layers.*.final_layer_norm',
    'encoder.layer_norm': 'speecht5.encoder.wrapped_encoder.layer_norm',
    'encoder.pos_emb.pe_k': 'speecht5.encoder.wrapped_encoder.embed_positions.pe_k',
}
lowerCamelCase__					=   {
    'decoder.layers.*.self_attn.k_proj': 'speecht5.decoder.wrapped_decoder.layers.*.self_attn.k_proj',
    'decoder.layers.*.self_attn.v_proj': 'speecht5.decoder.wrapped_decoder.layers.*.self_attn.v_proj',
    'decoder.layers.*.self_attn.q_proj': 'speecht5.decoder.wrapped_decoder.layers.*.self_attn.q_proj',
    'decoder.layers.*.self_attn.out_proj': 'speecht5.decoder.wrapped_decoder.layers.*.self_attn.out_proj',
    'decoder.layers.*.self_attn_layer_norm': 'speecht5.decoder.wrapped_decoder.layers.*.self_attn_layer_norm',
    'decoder.layers.*.encoder_attn.k_proj': 'speecht5.decoder.wrapped_decoder.layers.*.encoder_attn.k_proj',
    'decoder.layers.*.encoder_attn.v_proj': 'speecht5.decoder.wrapped_decoder.layers.*.encoder_attn.v_proj',
    'decoder.layers.*.encoder_attn.q_proj': 'speecht5.decoder.wrapped_decoder.layers.*.encoder_attn.q_proj',
    'decoder.layers.*.encoder_attn.out_proj': 'speecht5.decoder.wrapped_decoder.layers.*.encoder_attn.out_proj',
    'decoder.layers.*.encoder_attn_layer_norm': 'speecht5.decoder.wrapped_decoder.layers.*.encoder_attn_layer_norm',
    'decoder.layers.*.fc1': 'speecht5.decoder.wrapped_decoder.layers.*.feed_forward.intermediate_dense',
    'decoder.layers.*.fc2': 'speecht5.decoder.wrapped_decoder.layers.*.feed_forward.output_dense',
    'decoder.layers.*.final_layer_norm': 'speecht5.decoder.wrapped_decoder.layers.*.final_layer_norm',
}
lowerCamelCase__					=   {
    **MAPPING_SPEECH_ENCODER_PRENET,
    **MAPPING_ENCODER,
    **MAPPING_DECODER,
    **MAPPING_TEXT_DECODER_PRENET,
    **MAPPING_TEXT_DECODER_POSTNET,
}
lowerCamelCase__					=   {
    **MAPPING_TEXT_ENCODER_PRENET,
    **MAPPING_ENCODER,
    **MAPPING_DECODER,
    **MAPPING_SPEECH_DECODER_PRENET,
    **MAPPING_SPEECH_DECODER_POSTNET,
}
lowerCamelCase__					=   {
    **MAPPING_SPEECH_ENCODER_PRENET,
    **MAPPING_ENCODER,
    **MAPPING_DECODER,
    **MAPPING_SPEECH_DECODER_PRENET,
    **MAPPING_SPEECH_DECODER_POSTNET,
}
lowerCamelCase__					=   []
lowerCamelCase__					=   [
    'encoder.version',
    'encoder.layers.*.norm_k.weight',
    'encoder.layers.*.norm_k.bias',
    'decoder.version',
    'decoder.layers.*.norm_k.weight',
    'decoder.layers.*.norm_k.bias',
    'decoder.pos_emb.pe_k',
    'speech_encoder_prenet.embed_positions._float_tensor',
    'text_decoder_prenet.embed_positions._float_tensor',
]
lowerCamelCase__					=   IGNORE_KEYS + [
    'encoder.proj',
    'text_encoder_prenet.*',
    'speech_decoder_prenet.*',
    'speech_decoder_postnet.*',
]
lowerCamelCase__					=   IGNORE_KEYS + [
    'encoder.proj',
    'speech_encoder_prenet.*',
    'text_decoder_prenet.*',
    'text_decoder_postnet.*',
]
lowerCamelCase__					=   IGNORE_KEYS + [
    'encoder.proj',
    'text_encoder_prenet.*',
    'text_decoder_prenet.*',
    'text_decoder_postnet.*',
]






def        __lowerCAmelCase       (__lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase      ):
		for attribute in key.split("."      ):
				_UpperCAmelCase						:				Tuple	    =					getattr(__lowerCAmelCase					,       __lowerCAmelCase      )

		if weight_type is not None:
				_UpperCAmelCase						:				List[str]	    =					getattr(__lowerCAmelCase					,       __lowerCAmelCase      ).shape
		else:
				_UpperCAmelCase						:				List[Any]	    =					hf_pointer.shape

		if hf_shape != value.shape:
				raise ValueError(
				    F"""Shape of hf {key + '.' + weight_type if weight_type is not None else ''} is {hf_shape}, but should be"""
				    F""" {value.shape} for {full_name}"""      )

		if weight_type == "weight":
				_UpperCAmelCase						:				Any	    =					value
		elif weight_type == "weight_g":
				_UpperCAmelCase						:				List[Any]	    =					value
		elif weight_type == "weight_v":
				_UpperCAmelCase						:				Optional[int]	    =					value
		elif weight_type == "bias":
				_UpperCAmelCase						:				List[Any]	    =					value
		elif weight_type == "running_mean":
				_UpperCAmelCase						:				Union[str, Any]	    =					value
		elif weight_type == "running_var":
				_UpperCAmelCase						:				List[str]	    =					value
		elif weight_type == "num_batches_tracked":
				_UpperCAmelCase						:				str	    =					value
		else:
				_UpperCAmelCase						:				List[str]	    =					value

		logger.info(F"""{key + ('.' + weight_type if weight_type is not None else '')} was initialized from {full_name}."""      )






def        __lowerCAmelCase       (__lowerCAmelCase					,       __lowerCAmelCase      ):
		for key in ignore_keys:
				if key.endswith(".*"      ):
						if name.startswith(key[:-1]      ):
								return True
				elif ".*." in key:
						_UpperCAmelCase    ,			_UpperCAmelCase						:				List[Any]	    =					key.split(".*."      )
						if prefix in name and suffix in name:
								return True
				elif key in name:
						return True
		return False






def        __lowerCAmelCase       (__lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase      ):
		_UpperCAmelCase						:				List[Any]	    =					[]

		if task == "s2t":
				_UpperCAmelCase						:				Tuple	    =					hf_model.speechta.encoder.prenet.feature_encoder
				_UpperCAmelCase						:				int	    =					MAPPING_S2T
				_UpperCAmelCase						:				str	    =					IGNORE_KEYS_S2T
		elif task == "t2s":
				_UpperCAmelCase						:				Optional[int]	    =					None
				_UpperCAmelCase						:				Optional[int]	    =					MAPPING_T2S
				_UpperCAmelCase						:				Union[str, Any]	    =					IGNORE_KEYS_T2S
		elif task == "s2s":
				_UpperCAmelCase						:				Tuple	    =					hf_model.speechta.encoder.prenet.feature_encoder
				_UpperCAmelCase						:				Any	    =					MAPPING_S2S
				_UpperCAmelCase						:				Optional[int]	    =					IGNORE_KEYS_S2S
		else:
				raise ValueError(F"""Unsupported task: {task}"""      )

		for name, value in fairseq_dict.items():
				if should_ignore(__lowerCAmelCase					,       __lowerCAmelCase      ):
						logger.info(F"""{name} was ignored"""      )
						continue

				_UpperCAmelCase						:				List[Any]	    =					False
				if "conv_layers" in name:
						load_conv_layer(
						    __lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase					,       hf_model.config.feat_extract_norm == "group"					,       )
						_UpperCAmelCase						:				Tuple	    =					True
				else:
						for key, mapped_key in MAPPING.items():
								# mapped_key = "speecht5." + mapped_key if mapped_key not in TOP_LEVEL_KEYS else mapped_key

								if "*" in key:
										_UpperCAmelCase    ,			_UpperCAmelCase						:				Optional[Any]	    =					key.split(".*."      )
										if prefix in name and suffix in name:
												_UpperCAmelCase						:				Tuple	    =					suffix

                # if key in name or key.split("w2v_model.")[-1] == name.split(".")[0]:
								if key in name:
										_UpperCAmelCase						:				str	    =					True
										if "*" in mapped_key:
												_UpperCAmelCase						:				Union[str, Any]	    =					name.split(__lowerCAmelCase      )[0].split("."      )[-2]
												_UpperCAmelCase						:				Dict	    =					mapped_key.replace("*"					,       __lowerCAmelCase      )
										if "weight_g" in name:
												_UpperCAmelCase						:				Optional[int]	    =					"weight_g"
										elif "weight_v" in name:
												_UpperCAmelCase						:				List[Any]	    =					"weight_v"
										elif "bias" in name:
												_UpperCAmelCase						:				Any	    =					"bias"
										elif "weight" in name:
												_UpperCAmelCase						:				Optional[Any]	    =					"weight"
										elif "running_mean" in name:
												_UpperCAmelCase						:				List[str]	    =					"running_mean"
										elif "running_var" in name:
												_UpperCAmelCase						:				str	    =					"running_var"
										elif "num_batches_tracked" in name:
												_UpperCAmelCase						:				Any	    =					"num_batches_tracked"
										else:
												_UpperCAmelCase						:				Union[str, Any]	    =					None
										set_recursively(__lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase      )
								continue
				if not is_used:
						unused_weights.append(__lowerCAmelCase      )

		logger.warning(F"""Unused weights: {unused_weights}"""      )






def        __lowerCAmelCase       (__lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase      ):
		_UpperCAmelCase						:				Union[str, Any]	    =					full_name.split("conv_layers."      )[-1]
		_UpperCAmelCase						:				str	    =					name.split("."      )
		_UpperCAmelCase						:				int	    =					int(items[0]      )
		_UpperCAmelCase						:				Optional[int]	    =					int(items[1]      )

		if type_id == 0:
				if "bias" in name:
						if value.shape != feature_extractor.conv_layers[layer_id].conv.bias.data.shape:
								raise ValueError(
								    F"""{full_name} has size {value.shape}, but"""
								    F""" {feature_extractor.conv_layers[layer_id].conv.bias.data.shape} was found."""      )
						_UpperCAmelCase						:				List[str]	    =					value
						logger.info(F"""Feat extract conv layer {layer_id} was initialized from {full_name}."""      )
				elif "weight" in name:
						if value.shape != feature_extractor.conv_layers[layer_id].conv.weight.data.shape:
								raise ValueError(
								    F"""{full_name} has size {value.shape}, but"""
								    F""" {feature_extractor.conv_layers[layer_id].conv.weight.data.shape} was found."""      )
						_UpperCAmelCase						:				Optional[int]	    =					value
						logger.info(F"""Feat extract conv layer {layer_id} was initialized from {full_name}."""      )
		elif (type_id == 2 and not use_group_norm) or (type_id == 2 and layer_id == 0 and use_group_norm):
				if "bias" in name:
						if value.shape != feature_extractor.conv_layers[layer_id].layer_norm.bias.data.shape:
								raise ValueError(
								    F"""{full_name} has size {value.shape}, but"""
								    F""" {feature_extractor.conv_layers[layer_id].layer_norm.bias.data.shape} was found."""      )
						_UpperCAmelCase						:				List[str]	    =					value
						logger.info(F"""Feat extract layer norm weight of layer {layer_id} was initialized from {full_name}."""      )
				elif "weight" in name:
						if value.shape != feature_extractor.conv_layers[layer_id].layer_norm.weight.data.shape:
								raise ValueError(
								    F"""{full_name} has size {value.shape}, but"""
								    F""" {feature_extractor.conv_layers[layer_id].layer_norm.weight.data.shape} was found."""      )
						_UpperCAmelCase						:				str	    =					value
						logger.info(F"""Feat extract layer norm weight of layer {layer_id} was initialized from {full_name}."""      )
		else:
				unused_weights.append(__lowerCAmelCase      )






@torch.no_grad()
def        __lowerCAmelCase       (__lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase=None					,       __lowerCAmelCase=None					,       __lowerCAmelCase=None					,       ):
		if config_path is not None:
				_UpperCAmelCase						:				Dict	    =					SpeechTaConfig.from_pretrained(__lowerCAmelCase      )
		else:
				_UpperCAmelCase						:				Optional[int]	    =					SpeechTaConfig()

		if task == "s2t":
				_UpperCAmelCase						:				List[str]	    =					config.max_text_positions
				_UpperCAmelCase						:				Any	    =					SpeechTaForSpeechToText(__lowerCAmelCase      )
		elif task == "t2s":
				_UpperCAmelCase						:				int	    =					1_876
				_UpperCAmelCase						:				Union[str, Any]	    =					600
				_UpperCAmelCase						:				Union[str, Any]	    =					config.max_speech_positions
				_UpperCAmelCase						:				Optional[Any]	    =					SpeechTaForTextToSpeech(__lowerCAmelCase      )
		elif task == "s2s":
				_UpperCAmelCase						:				int	    =					1_876
				_UpperCAmelCase						:				Dict	    =					config.max_speech_positions
				_UpperCAmelCase						:				Dict	    =					SpeechTaForSpeechToSpeech(__lowerCAmelCase      )
		else:
				raise ValueError(F"""Unknown task name: {task}"""      )

		if vocab_path:
				_UpperCAmelCase						:				int	    =					SpeechTaTokenizer(__lowerCAmelCase					,       model_max_length=config.max_text_positions      )

				# Mask token behaves like a normal word, i.e. include the space before it
				_UpperCAmelCase						:				Tuple	    =					AddedToken("<mask>"					,       lstrip=__lowerCAmelCase					,       rstrip=__lowerCAmelCase      )
				_UpperCAmelCase						:				int	    =					mask_token
				tokenizer.add_special_tokens({"mask_token": mask_token}      )
				tokenizer.add_tokens(["<ctc_blank>"]      )

		_UpperCAmelCase						:				Tuple	    =					SpeechTaFeatureExtractor()
		_UpperCAmelCase						:				Dict	    =					SpeechTaProcessor(tokenizer=__lowerCAmelCase					,       feature_extractor=__lowerCAmelCase      )
		processor.save_pretrained(__lowerCAmelCase      )

		_UpperCAmelCase						:				Any	    =					torch.load(__lowerCAmelCase      )
		recursively_load_weights(fairseq_checkpoint["model"]					,       __lowerCAmelCase					,       __lowerCAmelCase      )

		model.save_pretrained(__lowerCAmelCase      )

		if repo_id:
				print("Pushing to the hub..."      )
				processor.push_to_hub(__lowerCAmelCase      )
				model.push_to_hub(__lowerCAmelCase      )


if __name__ == "__main__":
						lowerCamelCase__					=   argparse.ArgumentParser()
						parser.add_argument(
						    '--task',
						    default='s2t',
						    type=str,
						    help='Type of the SpeechT5 model you\'d like to convert. Should be one of \'s2t\', \'t2s\', \'s2s\'.',
						)
						parser.add_argument('--checkpoint_path', required=True, default=None, type=str, help='Path to fairseq checkpoint')
						parser.add_argument('--vocab_path', default=None, type=str, help='Path to SentencePiece model')
						parser.add_argument('--config_path', default=None, type=str, help='Path to hf config.json of model to convert')
						parser.add_argument(
						    '--pytorch_dump_folder_path', required=True, default=None, type=str, help='Path to the output PyTorch model.'
						)
						parser.add_argument(
						    '--push_to_hub', default=None, type=str, help='Where to upload the converted model on the 🤗 hub.'
						)

						lowerCamelCase__					=   parser.parse_args()
						convert_speechta_checkpoint(
						    args.task,
						    args.checkpoint_path,
						    args.pytorch_dump_folder_path,
						    args.config_path,
						    args.vocab_path,
						    args.push_to_hub,
						)







'''simple docstring'''


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






class 		lowerCAmelCase__	:




			def __init__(						self     :   Union[str, Any]       )      ->Union[str, Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				List[Any]	    =					{}




			def 							lowerCAmelCase__			(						self     :   Dict		,     lowerCamelCase__     :   Tuple		,     lowerCamelCase__     :   List[str]		,     lowerCamelCase__     :   int=1       )      ->Optional[Any]:



					'''simple docstring'''







					if self.graph.get(lowerCamelCase__       ):
							if self.graph[u].count([w, v]       ) == 0:
									self.graph[u].append([w, v]       )
					else:
							_UpperCAmelCase						:				Dict	    =					[[w, v]]
					if not self.graph.get(lowerCamelCase__       ):
							_UpperCAmelCase						:				str	    =					[]




			def 							lowerCAmelCase__			(						self     :   Any       )      ->Tuple:



					'''simple docstring'''







					return list(self.graph       )




			def 							lowerCAmelCase__			(						self     :   Tuple		,     lowerCamelCase__     :   Union[str, Any]		,     lowerCamelCase__     :   str       )      ->Any:



					'''simple docstring'''







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




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Optional[Any]=-2		,     lowerCamelCase__     :   Optional[int]=-1       )      ->int:



					'''simple docstring'''







					if s == d:
							return []
					_UpperCAmelCase						:				Tuple	    =					[]
					_UpperCAmelCase						:				Optional[int]	    =					[]
					if s == -2:
							_UpperCAmelCase						:				Union[str, Any]	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				Optional[Any]	    =					s

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

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

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




			def 							lowerCAmelCase__			(						self     :   List[Any]		,     lowerCamelCase__     :   Any=-1       )      ->str:



					'''simple docstring'''







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




			def 							lowerCAmelCase__			(						self     :   Any		,     lowerCamelCase__     :   Union[str, Any]=-2       )      ->Union[str, Any]:



					'''simple docstring'''







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



					'''simple docstring'''







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




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Union[str, Any]       )      ->int:



					'''simple docstring'''







					return len(self.graph[u]       )




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Any=-2       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					[]
					_UpperCAmelCase						:				List[str]	    =					[]
					if s == -2:
							_UpperCAmelCase						:				str	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				List[Any]	    =					s
					_UpperCAmelCase						:				Tuple	    =					[]

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

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

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




			def 							lowerCAmelCase__			(						self     :   Union[str, Any]       )      ->Optional[Any]:



					'''simple docstring'''







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

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

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

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




			def 							lowerCAmelCase__			(						self     :   int       )      ->Optional[int]:



					'''simple docstring'''







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

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

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

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




			def 							lowerCAmelCase__			(						self     :   str		,     lowerCamelCase__     :   Tuple=-2		,     lowerCamelCase__     :   Union[str, Any]=-1       )      ->Any:



					'''simple docstring'''







					_UpperCAmelCase						:				Dict	    =					time()
					self.dfs(lowerCamelCase__		,     lowerCamelCase__       )
					_UpperCAmelCase						:				Tuple	    =					time()
					return end - begin






			def 							lowerCAmelCase__			(						self     :   List[Any]		,     lowerCamelCase__     :   Dict=-2       )      ->Union[str, Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					time()
					self.bfs(lowerCamelCase__       )
					_UpperCAmelCase						:				Tuple	    =					time()
					return end - begin






class 		lowerCAmelCase__	:




			def __init__(						self     :   Tuple       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Any	    =					{}




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   List[str]		,     lowerCamelCase__     :   str		,     lowerCamelCase__     :   Tuple=1       )      ->int:



					'''simple docstring'''







					if self.graph.get(lowerCamelCase__       ):
							# if there already is a edge
							if self.graph[u].count([w, v]       ) == 0:
									self.graph[u].append([w, v]       )
					else:
							# if u does not exist
							_UpperCAmelCase						:				Dict	    =					[[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
							_UpperCAmelCase						:				Tuple	    =					[[w, u]]




			def 							lowerCAmelCase__			(						self     :   Dict		,     lowerCamelCase__     :   Any		,     lowerCamelCase__     :   Optional[Any]       )      ->Dict:



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



					'''simple docstring'''







					if s == d:
							return []
					_UpperCAmelCase						:				List[Any]	    =					[]
					_UpperCAmelCase						:				List[Any]	    =					[]
					if s == -2:
							_UpperCAmelCase						:				List[Any]	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				List[Any]	    =					s

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

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

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




			def 							lowerCAmelCase__			(						self     :   Any		,     lowerCamelCase__     :   Dict=-1       )      ->str:



					'''simple docstring'''







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




			def 							lowerCAmelCase__			(						self     :   str		,     lowerCamelCase__     :   Union[str, Any]=-2       )      ->Any:



					'''simple docstring'''







					_UpperCAmelCase						:				str	    =					deque()
					_UpperCAmelCase						:				Optional[int]	    =					[]
					if s == -2:
							_UpperCAmelCase						:				Union[str, Any]	    =					list(self.graph       )[0]
					d.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					while d:
							_UpperCAmelCase						:				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     :   Union[str, Any]		,     lowerCamelCase__     :   Dict       )      ->Optional[Any]:



					'''simple docstring'''







					return len(self.graph[u]       )




			def 							lowerCAmelCase__			(						self     :   str       )      ->Any:



					'''simple docstring'''







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

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

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

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




			def 							lowerCAmelCase__			(						self     :   Optional[Any]       )      ->Dict:



					'''simple docstring'''







					_UpperCAmelCase						:				List[Any]	    =					[]
					_UpperCAmelCase						:				List[str]	    =					[]
					_UpperCAmelCase						:				Tuple	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				Dict	    =					-2
					_UpperCAmelCase						:				Union[str, Any]	    =					[]
					_UpperCAmelCase						:				Dict	    =					s
					_UpperCAmelCase						:				Dict	    =					False
					_UpperCAmelCase						:				str	    =					set()

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

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

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




			def 							lowerCAmelCase__			(						self     :   Optional[Any]       )      ->int:



					'''simple docstring'''







					return list(self.graph       )




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Dict=-2		,     lowerCamelCase__     :   Dict=-1       )      ->List[Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					time()
					self.dfs(lowerCamelCase__		,     lowerCamelCase__       )
					_UpperCAmelCase						:				int	    =					time()
					return end - begin






			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Any=-2       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					time()
					self.bfs(lowerCamelCase__       )
					_UpperCAmelCase						:				Any	    =					time()
					return end - begin



