




"""simple docstring"""







import argparse

import fairseq
import torch
from torch import nn

from transformers import (
    MBartaaTokenizer,
    MBartConfig,
    MBartForCausalLM,
    SpeechEncoderDecoderConfig,
    SpeechEncoderDecoderModel,
    WavaVecaConfig,
    WavaVecaFeatureExtractor,
    WavaVecaModel,
    logging,
)


logging.set_verbosity_info()
a      =							logging.get_logger(__name__)

a      =							{
    'post_extract_proj': 'feature_projection.projection',
    'encoder.pos_conv.0': 'encoder.pos_conv_embed.conv',
    'self_attn.k_proj': 'encoder.layers.*.attention.k_proj',
    'self_attn.v_proj': 'encoder.layers.*.attention.v_proj',
    'self_attn.q_proj': 'encoder.layers.*.attention.q_proj',
    'self_attn.out_proj': 'encoder.layers.*.attention.out_proj',
    'self_attn_layer_norm': 'encoder.layers.*.layer_norm',
    'fc1': 'encoder.layers.*.feed_forward.intermediate_dense',
    'fc2': 'encoder.layers.*.feed_forward.output_dense',
    'final_layer_norm': 'encoder.layers.*.final_layer_norm',
    'encoder.layer_norm': 'encoder.layer_norm',
    'w2v_model.layer_norm': 'feature_projection.layer_norm',
    'quantizer.weight_proj': 'quantizer.weight_proj',
    'quantizer.vars': 'quantizer.codevectors',
    'project_q': 'project_q',
    'final_proj': 'project_hid',
    'w2v_encoder.proj': 'lm_head',
    'mask_emb': 'masked_spec_embed',
}
a      =							[
    'lm_head',
    'quantizer.weight_proj',
    'quantizer.codevectors',
    'project_q',
    'project_hid',
]





def 							lowercase					(snake_case__   : str      ,       snake_case__   : Dict      ,       snake_case__   : List[str]      ,       snake_case__   : Dict      ,       snake_case__   : List[Any] )     ->  Dict:


				'''simple docstring'''






				for attribute in key.split(""".""" ):
								lowerCAmelCase  =				getattr(snake_case__      ,       snake_case__ )

				if weight_type is not None:
								lowerCAmelCase  =				getattr(snake_case__      ,       snake_case__ ).shape
				else:
								lowerCAmelCase  =				hf_pointer.shape

				assert hf_shape == value.shape, (
				    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":
								lowerCAmelCase  =				value
				elif weight_type == "weight_g":
								lowerCAmelCase  =				value
				elif weight_type == "weight_v":
								lowerCAmelCase  =				value
				elif weight_type == "bias":
								lowerCAmelCase  =				value
				else:
								lowerCAmelCase  =				value

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





def 							lowercase					(snake_case__   : Tuple      ,       snake_case__   : Union[str, Any] )     ->  List[Any]:


				'''simple docstring'''






				lowerCAmelCase  =				[]
				lowerCAmelCase  =				fairseq_model.state_dict()

				lowerCAmelCase  =				hf_model.feature_extractor
				lowerCAmelCase  =				hf_model.adapter

				for name, value in fairseq_dict.items():
								lowerCAmelCase  =				False
								if "conv_layers" in name:
												load_conv_layer(
												    snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       hf_model.config.feat_extract_norm == """group"""      ,       )
												lowerCAmelCase  =				True
								elif any(x in name for x in ["""adaptor""", """w2v_encoder.proj.""", """w2v_proj_ln."""] ):
												load_adapter(snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__ )
												lowerCAmelCase  =				True
								else:
												for key, mapped_key in MAPPING.items():
																if key in name or key.split("""w2v_model.""" )[-1] == name.split(""".""" )[0]:
																				lowerCAmelCase  =				True
																				if "*" in mapped_key:
																								lowerCAmelCase  =				name.split(snake_case__ )[0].split(""".""" )[-2]
																								lowerCAmelCase  =				mapped_key.replace("""*"""      ,       snake_case__ )
																				if "weight_g" in name:
																								lowerCAmelCase  =				"""weight_g"""
																				elif "weight_v" in name:
																								lowerCAmelCase  =				"""weight_v"""
																				elif "bias" in name:
																								lowerCAmelCase  =				"""bias"""
																				elif "weight" in name:
																								lowerCAmelCase  =				"""weight"""
																				else:
																								lowerCAmelCase  =				None
																				set_recursively(snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__ )
																continue
								if not is_used:
												unused_weights.append(snake_case__ )

				logger.warning(f'''Unused weights: {unused_weights}''' )





def 							lowercase					(snake_case__   : str      ,       snake_case__   : Optional[int]      ,       snake_case__   : Any      ,       snake_case__   : Dict      ,       snake_case__   : Dict )     ->  str:


				'''simple docstring'''






				lowerCAmelCase  =				full_name.split("""conv_layers.""" )[-1]
				lowerCAmelCase  =				name.split(""".""" )
				lowerCAmelCase  =				int(items[0] )
				lowerCAmelCase  =				int(items[1] )

				if type_id == 0:
								if "bias" in name:
												assert value.shape == feature_extractor.conv_layers[layer_id].conv.bias.data.shape, (
												    f'''{full_name} has size {value.shape}, but'''
												    f''' {feature_extractor.conv_layers[layer_id].conv.bias.data.shape} was found.'''
												)
												lowerCAmelCase  =				value
												logger.info(f'''Feat extract conv layer {layer_id} was initialized from {full_name}.''' )
								elif "weight" in name:
												assert value.shape == feature_extractor.conv_layers[layer_id].conv.weight.data.shape, (
												    f'''{full_name} has size {value.shape}, but'''
												    f''' {feature_extractor.conv_layers[layer_id].conv.weight.data.shape} was found.'''
												)
												lowerCAmelCase  =				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:
												assert value.shape == feature_extractor.conv_layers[layer_id].layer_norm.bias.data.shape, (
												    f'''{full_name} has size {value.shape}, but {feature_extractor[layer_id].layer_norm.bias.data.shape} was'''
												    " found."
												)
												lowerCAmelCase  =				value
												logger.info(f'''Feat extract layer norm weight of layer {layer_id} was initialized from {full_name}.''' )
								elif "weight" in name:
												assert value.shape == feature_extractor.conv_layers[layer_id].layer_norm.weight.data.shape, (
												    f'''{full_name} has size {value.shape}, but'''
												    f''' {feature_extractor[layer_id].layer_norm.weight.data.shape} was found.'''
												)
												lowerCAmelCase  =				value
												logger.info(f'''Feat extract layer norm weight of layer {layer_id} was initialized from {full_name}.''' )
				else:
								unused_weights.append(snake_case__ )





def 							lowercase					(snake_case__   : int      ,       snake_case__   : Optional[int]      ,       snake_case__   : Optional[Any]      ,       snake_case__   : int )     ->  Union[str, Any]:


				'''simple docstring'''






				lowerCAmelCase  =				full_name.split("""adaptor.""" )[-1]
				lowerCAmelCase  =				name.split(""".""" )

				if items[1].isdigit():
								lowerCAmelCase  =				int(items[1] )
				else:
								lowerCAmelCase  =				None

				if "adaptor" not in full_name:
								if "proj_ln" in full_name:
												# has to be layer norm
												if "bias" in name:
																assert (
																    value.shape == adapter.proj_layer_norm.bias.data.shape
																), f'''{full_name} has size {value.shape}, but {adapter.proj_layer_norm.bias.data.shape} was found.'''
																lowerCAmelCase  =				value
																logger.info(f'''Adapter proj layer norm bias was initialized from {full_name}.''' )
												if "weight" in name:
																assert (
																    value.shape == adapter.proj_layer_norm.weight.data.shape
																), f'''{full_name} has size {value.shape}, but {adapter.proj_layer_norm.weight.data.shape} was found.'''
																lowerCAmelCase  =				value
								else:
												# has to be projection layer
												if "bias" in name:
																assert (
																    value.shape == adapter.proj.bias.data.shape
																), f'''{full_name} has size {value.shape}, but {adapter.proj.bias.data.shape} was found.'''
																lowerCAmelCase  =				value
																logger.info(f'''Adapter proj layer bias was initialized from {full_name}.''' )
												if "weight" in name:
																assert (
																    value.shape == adapter.proj.weight.data.shape
																), f'''{full_name} has size {value.shape}, but {adapter.proj.weight.data.shape} was found.'''
																lowerCAmelCase  =				value
																logger.info(f'''Adapter proj layer weight was initialized from {full_name}.''' )
				elif isinstance(snake_case__      ,       snake_case__ ):
								if "bias" in name:
												assert (
												    value.shape == adapter.layers[layer_id].conv.bias.data.shape
												), f'''{full_name} has size {value.shape}, but {adapter.layers[layer_id].conv.bias.data.shape} was found.'''
												lowerCAmelCase  =				value
												logger.info(f'''Adapter layer {layer_id} bias was initialized from {full_name}.''' )
								elif "weight" in name:
												assert (
												    value.shape == adapter.layers[layer_id].conv.weight.data.shape
												), f'''{full_name} has size {value.shape}, but {adapter.layers[layer_id].conv.weight.data.shape} was found.'''
												lowerCAmelCase  =				value
												logger.info(f'''Adapter layer {layer_id} bias was initialized from {full_name}.''' )
				else:
								unused_weights.append(snake_case__ )





def 							lowercase					(snake_case__   : Dict )     ->  List[str]:


				'''simple docstring'''






				lowerCAmelCase ,						lowerCAmelCase  =				emb.weight.shape
				lowerCAmelCase  =				nn.Linear(snake_case__      ,       snake_case__      ,       bias=snake_case__ )
				lowerCAmelCase  =				emb.weight.data
				return lin_layer





@torch.no_grad()
def 							lowercase					(snake_case__   : Dict      ,       snake_case__   : Optional[int]      ,       snake_case__   : Optional[int]      ,       snake_case__   : Tuple      ,       snake_case__   : List[str]      ,       snake_case__   : Union[str, Any]      ,       snake_case__   : Tuple      ,       snake_case__   : Tuple      ,       snake_case__   : str      ,       snake_case__   : Union[str, Any]      ,       snake_case__   : Optional[int]      ,       )     ->  Optional[int]:


				'''simple docstring'''






				lowerCAmelCase  =				WavaVecaConfig.from_pretrained(
				    snake_case__      ,       add_adapter=snake_case__      ,       adapter_stride=snake_case__      ,       adapter_kernel_size=snake_case__      ,       use_auth_token=snake_case__      ,       output_hidden_size=snake_case__      ,       )
				lowerCAmelCase  =				MBartConfig.from_pretrained(snake_case__ )

				# load model
				lowerCAmelCase ,						lowerCAmelCase ,						lowerCAmelCase  =				fairseq.checkpoint_utils.load_model_ensemble_and_task(
				    [checkpoint_path]      ,       arg_overrides={
				        """config_yaml""": config_yaml_path,
				        """data""": """/""".join(dict_path.split("""/""" )[:-1] ),
				        """w2v_path""": checkpoint_path,
				        """load_pretrained_decoder_from""": None,
				    }      ,       )
				lowerCAmelCase  =				model[0].eval()

				# load feature extractor
				lowerCAmelCase  =				WavaVecaFeatureExtractor.from_pretrained(snake_case__      ,       use_auth_token=snake_case__ )

				# set weights for wav2vec2 encoder
				lowerCAmelCase  =				WavaVecaModel(snake_case__ )

				recursively_load_weights_wavaveca(model.encoder      ,       snake_case__ )

				# load decoder weights
				lowerCAmelCase  =				MBartForCausalLM(snake_case__ )
				lowerCAmelCase ,						lowerCAmelCase  =				hf_decoder.model.decoder.load_state_dict(model.decoder.state_dict()      ,       strict=snake_case__ )
				logger.warning(f'''The following keys are missing when loading the decoder weights: {missing_keys}''' )
				logger.warning(f'''The following keys are unexpected when loading the decoder weights: {unexpected_keys}''' )

				lowerCAmelCase  =				SpeechEncoderDecoderModel(encoder=snake_case__      ,       decoder=snake_case__ )
				lowerCAmelCase  =				False

				lowerCAmelCase  =				MBartaaTokenizer(snake_case__ )
				tokenizer.save_pretrained(snake_case__ )

				lowerCAmelCase  =				hf_wavavec.config.to_dict()
				lowerCAmelCase  =				tokenizer.pad_token_id
				lowerCAmelCase  =				tokenizer.bos_token_id
				lowerCAmelCase  =				tokenizer.eos_token_id
				lowerCAmelCase  =				"""mbart50"""
				lowerCAmelCase  =				"""wav2vec2"""

				lowerCAmelCase  =				tokenizer.eos_token_id
				lowerCAmelCase  =				250_004
				lowerCAmelCase  =				tokenizer.eos_token_id

				lowerCAmelCase  =				SpeechEncoderDecoderConfig.from_dict(snake_case__ )

				hf_wavavec.save_pretrained(snake_case__ )
				feature_extractor.save_pretrained(snake_case__ )


if __name__ == "__main__":
		a      =							argparse.ArgumentParser()
		parser.add_argument('--pytorch_dump_folder_path', default=None, type=str, help='Path to the output PyTorch model.')
		parser.add_argument('--checkpoint_path', default=None, type=str, help='Path to fairseq checkpoint')
		parser.add_argument('--dict_path', default=None, type=str, help='Path to dict of fine-tuned model')
		parser.add_argument('--config_yaml_path', default=None, type=str, help='Path to yaml file of fine-tuned model')
		parser.add_argument(
		    '--encoder_config_path',
		    default='facebook/wav2vec2-xls-r-1b',
		    type=str,
		    help='Path to hf encoder wav2vec2 checkpoint config',
		)
		parser.add_argument(
		    '--decoder_config_path',
		    default='facebook/mbart-large-50-one-to-many-mmt',
		    type=str,
		    help='Path to hf decoder checkpoint config',
		)
		parser.add_argument('--add_adapter', default=True, type=bool, help='whethere to add model adapter layers')
		parser.add_argument('--adapter_stride', default=2, type=int, help='stride of adapter layers')
		parser.add_argument('--adapter_kernel_size', default=3, type=int, help='kernel size of adapter layers')
		parser.add_argument('--encoder_output_dim', default=1_0_2_4, type=int, help='encoder output dim')
		parser.add_argument('--start_token_id', default=2_5_0_0_0_4, type=int, help='`decoder_start_token_id` of model config')

		a      =							parser.parse_args()
		convert_wavaveca_checkpoint(
		    args.checkpoint_path,
		    args.pytorch_dump_folder_path,
		    args.dict_path,
		    args.config_yaml_path,
		    encoder_config_path=args.encoder_config_path,
		    decoder_config_path=args.decoder_config_path,
		    add_adapter=args.add_adapter,
		    adapter_kernel_size=args.adapter_kernel_size,
		    adapter_stride=args.adapter_stride,
		    decoder_start_token_id=args.start_token_id,
		    encoder_output_dim=args.encoder_output_dim,
		)











"""simple docstring"""







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






class       SCREAMING_SNAKE_CASE__					:


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


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


						def   __lowercase (							self				:			Optional[int]					):
										return list(self.graph					)


						def   __lowercase (							self				:			Optional[Any]						,						lowerCAmelCase				:			Optional[Any]						,						lowerCAmelCase				:			Dict					):
										if self.graph.get(lowerCAmelCase					):
														for _ in self.graph[u]:
																		if _[1] == v:
																						self.graph[u].remove(lowerCAmelCase					)


						def   __lowercase (							self				:			List[str]						,						lowerCAmelCase				:			Tuple=-2						,						lowerCAmelCase				:			List[Any]=-1					):
										if s == d:
														return []
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				s

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

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

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


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


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


						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			Tuple					):
										return len(self.graph[u]					)


						def   __lowercase (							self				:			Optional[int]						,						lowerCAmelCase				:			Optional[Any]=-2					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				s
										lowerCAmelCase  =				[]

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

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

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


						def   __lowercase (							self				:			Any					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


						def   __lowercase (							self				:			Tuple					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


						def   __lowercase (							self				:			List[Any]						,						lowerCAmelCase				:			Any=-2						,						lowerCAmelCase				:			Tuple=-1					):
										lowerCAmelCase  =				time()
										self.dfs(lowerCAmelCase						,						lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin




						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			str=-2					):
										lowerCAmelCase  =				time()
										self.bfs(lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin






class       SCREAMING_SNAKE_CASE__					:


						def __init__(							self				:			int					):
										lowerCAmelCase  =				{}


						def   __lowercase (							self				:			Optional[Any]						,						lowerCAmelCase				:			Tuple						,						lowerCAmelCase				:			str						,						lowerCAmelCase				:			str=1					):
										# 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
														lowerCAmelCase  =				[[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
														lowerCAmelCase  =				[[w, u]]


						def   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			Any						,						lowerCAmelCase				:			int					):
										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   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			Optional[int]=-2						,						lowerCAmelCase				:			Optional[Any]=-1					):
										if s == d:
														return []
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				s

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

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

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


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


						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			Tuple=-2					):
										lowerCAmelCase  =				deque()
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										d.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										while d:
														lowerCAmelCase  =				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   __lowercase (							self				:			List[str]						,						lowerCAmelCase				:			str					):
										return len(self.graph[u]					)


						def   __lowercase (							self				:			Optional[Any]					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


						def   __lowercase (							self				:			int					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


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


						def   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			Dict=-2						,						lowerCAmelCase				:			List[str]=-1					):
										lowerCAmelCase  =				time()
										self.dfs(lowerCAmelCase						,						lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin




						def   __lowercase (							self				:			str						,						lowerCAmelCase				:			Union[str, Any]=-2					):
										lowerCAmelCase  =				time()
										self.bfs(lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin





