


'''simple docstring'''


import argparse
import json
import pickle
from pathlib import Path

import requests
import torch
from huggingface_hub import hf_hub_download
from PIL import Image

from transformers import MaskFormerConfig, MaskFormerForInstanceSegmentation, MaskFormerImageProcessor, SwinConfig
from transformers.utils import logging


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






def        __lowerCAmelCase       (__lowerCAmelCase      ):
		_UpperCAmelCase						:				Union[str, Any]	    =					SwinConfig.from_pretrained(
		    "microsoft/swin-tiny-patch4-window7-224"					,       out_features=["stage1", "stage2", "stage3", "stage4"]      )
		_UpperCAmelCase						:				Tuple	    =					MaskFormerConfig(backbone_config=__lowerCAmelCase      )

		_UpperCAmelCase						:				str	    =					"huggingface/label-files"
		if "ade20k-full" in model_name:
				# this should be ok
				_UpperCAmelCase						:				Optional[int]	    =					847
				_UpperCAmelCase						:				Dict	    =					"maskformer-ade20k-full-id2label.json"
		elif "ade" in model_name:
				# this should be ok
				_UpperCAmelCase						:				Tuple	    =					150
				_UpperCAmelCase						:				Union[str, Any]	    =					"ade20k-id2label.json"
		elif "coco-stuff" in model_name:
				# this should be ok
				_UpperCAmelCase						:				List[Any]	    =					171
				_UpperCAmelCase						:				int	    =					"maskformer-coco-stuff-id2label.json"
		elif "coco" in model_name:
				# TODO
				_UpperCAmelCase						:				str	    =					133
				_UpperCAmelCase						:				Optional[int]	    =					"coco-panoptic-id2label.json"
		elif "cityscapes" in model_name:
				# this should be ok
				_UpperCAmelCase						:				List[Any]	    =					19
				_UpperCAmelCase						:				Optional[int]	    =					"cityscapes-id2label.json"
		elif "vistas" in model_name:
				# this should be ok
				_UpperCAmelCase						:				List[Any]	    =					65
				_UpperCAmelCase						:				List[Any]	    =					"mapillary-vistas-id2label.json"

		_UpperCAmelCase						:				Any	    =					json.load(open(hf_hub_download(__lowerCAmelCase					,       __lowerCAmelCase					,       repo_type="dataset"      )					,       "r"      )      )
		_UpperCAmelCase						:				List[Any]	    =					{int(__lowerCAmelCase      ): v for k, v in idalabel.items()}

		return config






def        __lowerCAmelCase       (__lowerCAmelCase      ):
		_UpperCAmelCase						:				str	    =					[]
		# stem
		# fmt: off
		rename_keys.append(("backbone.patch_embed.proj.weight", "model.pixel_level_module.encoder.model.embeddings.patch_embeddings.projection.weight")      )
		rename_keys.append(("backbone.patch_embed.proj.bias", "model.pixel_level_module.encoder.model.embeddings.patch_embeddings.projection.bias")      )
		rename_keys.append(("backbone.patch_embed.norm.weight", "model.pixel_level_module.encoder.model.embeddings.norm.weight")      )
		rename_keys.append(("backbone.patch_embed.norm.bias", "model.pixel_level_module.encoder.model.embeddings.norm.bias")      )
		# stages
		for i in range(len(config.backbone_config.depths      )      ):
				for j in range(config.backbone_config.depths[i]      ):
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.norm1.weight""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.layernorm_before.weight""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.norm1.bias""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.layernorm_before.bias""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.attn.relative_position_bias_table""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.attention.self.relative_position_bias_table""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.attn.relative_position_index""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.attention.self.relative_position_index""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.attn.proj.weight""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.attention.output.dense.weight""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.attn.proj.bias""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.attention.output.dense.bias""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.norm2.weight""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.layernorm_after.weight""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.norm2.bias""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.layernorm_after.bias""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.mlp.fc1.weight""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.intermediate.dense.weight""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.mlp.fc1.bias""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.intermediate.dense.bias""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.mlp.fc2.weight""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.output.dense.weight""")      )
						rename_keys.append((F"""backbone.layers.{i}.blocks.{j}.mlp.fc2.bias""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.output.dense.bias""")      )

				if i < 3:
						rename_keys.append((F"""backbone.layers.{i}.downsample.reduction.weight""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.downsample.reduction.weight""")      )
						rename_keys.append((F"""backbone.layers.{i}.downsample.norm.weight""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.downsample.norm.weight""")      )
						rename_keys.append((F"""backbone.layers.{i}.downsample.norm.bias""", F"""model.pixel_level_module.encoder.model.encoder.layers.{i}.downsample.norm.bias""")      )
				rename_keys.append((F"""backbone.norm{i}.weight""", F"""model.pixel_level_module.encoder.hidden_states_norms.{i}.weight""")      )
				rename_keys.append((F"""backbone.norm{i}.bias""", F"""model.pixel_level_module.encoder.hidden_states_norms.{i}.bias""")      )

		# FPN
		rename_keys.append(("sem_seg_head.layer_4.weight", "model.pixel_level_module.decoder.fpn.stem.0.weight")      )
		rename_keys.append(("sem_seg_head.layer_4.norm.weight", "model.pixel_level_module.decoder.fpn.stem.1.weight")      )
		rename_keys.append(("sem_seg_head.layer_4.norm.bias", "model.pixel_level_module.decoder.fpn.stem.1.bias")      )
		for source_index, target_index in zip(range(3					,       0					,       -1      )					,       range(0					,       3      )      ):
				rename_keys.append((F"""sem_seg_head.adapter_{source_index}.weight""", F"""model.pixel_level_module.decoder.fpn.layers.{target_index}.proj.0.weight""")      )
				rename_keys.append((F"""sem_seg_head.adapter_{source_index}.norm.weight""", F"""model.pixel_level_module.decoder.fpn.layers.{target_index}.proj.1.weight""")      )
				rename_keys.append((F"""sem_seg_head.adapter_{source_index}.norm.bias""", F"""model.pixel_level_module.decoder.fpn.layers.{target_index}.proj.1.bias""")      )
				rename_keys.append((F"""sem_seg_head.layer_{source_index}.weight""", F"""model.pixel_level_module.decoder.fpn.layers.{target_index}.block.0.weight""")      )
				rename_keys.append((F"""sem_seg_head.layer_{source_index}.norm.weight""", F"""model.pixel_level_module.decoder.fpn.layers.{target_index}.block.1.weight""")      )
				rename_keys.append((F"""sem_seg_head.layer_{source_index}.norm.bias""", F"""model.pixel_level_module.decoder.fpn.layers.{target_index}.block.1.bias""")      )
		rename_keys.append(("sem_seg_head.mask_features.weight", "model.pixel_level_module.decoder.mask_projection.weight")      )
		rename_keys.append(("sem_seg_head.mask_features.bias", "model.pixel_level_module.decoder.mask_projection.bias")      )

		# Transformer decoder
		for idx in range(config.decoder_config.decoder_layers      ):
				# self-attention out projection
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.self_attn.out_proj.weight""", F"""model.transformer_module.decoder.layers.{idx}.self_attn.out_proj.weight""")      )
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.self_attn.out_proj.bias""", F"""model.transformer_module.decoder.layers.{idx}.self_attn.out_proj.bias""")      )
				# cross-attention out projection
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.multihead_attn.out_proj.weight""", F"""model.transformer_module.decoder.layers.{idx}.encoder_attn.out_proj.weight""")      )
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.multihead_attn.out_proj.bias""", F"""model.transformer_module.decoder.layers.{idx}.encoder_attn.out_proj.bias""")      )
				# MLP 1
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.linear1.weight""", F"""model.transformer_module.decoder.layers.{idx}.fc1.weight""")      )
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.linear1.bias""", F"""model.transformer_module.decoder.layers.{idx}.fc1.bias""")      )
				# MLP 2
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.linear2.weight""", F"""model.transformer_module.decoder.layers.{idx}.fc2.weight""")      )
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.linear2.bias""", F"""model.transformer_module.decoder.layers.{idx}.fc2.bias""")      )
				# layernorm 1 (self-attention layernorm)
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm1.weight""", F"""model.transformer_module.decoder.layers.{idx}.self_attn_layer_norm.weight""")      )
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm1.bias""", F"""model.transformer_module.decoder.layers.{idx}.self_attn_layer_norm.bias""")      )
				# layernorm 2 (cross-attention layernorm)
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm2.weight""", F"""model.transformer_module.decoder.layers.{idx}.encoder_attn_layer_norm.weight""")      )
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm2.bias""", F"""model.transformer_module.decoder.layers.{idx}.encoder_attn_layer_norm.bias""")      )
				# layernorm 3 (final layernorm)
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm3.weight""", F"""model.transformer_module.decoder.layers.{idx}.final_layer_norm.weight""")      )
				rename_keys.append((F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm3.bias""", F"""model.transformer_module.decoder.layers.{idx}.final_layer_norm.bias""")      )

		rename_keys.append(("sem_seg_head.predictor.transformer.decoder.norm.weight", "model.transformer_module.decoder.layernorm.weight")      )
		rename_keys.append(("sem_seg_head.predictor.transformer.decoder.norm.bias", "model.transformer_module.decoder.layernorm.bias")      )

		# heads on top
		rename_keys.append(("sem_seg_head.predictor.query_embed.weight", "model.transformer_module.queries_embedder.weight")      )

		rename_keys.append(("sem_seg_head.predictor.input_proj.weight", "model.transformer_module.input_projection.weight")      )
		rename_keys.append(("sem_seg_head.predictor.input_proj.bias", "model.transformer_module.input_projection.bias")      )

		rename_keys.append(("sem_seg_head.predictor.class_embed.weight", "class_predictor.weight")      )
		rename_keys.append(("sem_seg_head.predictor.class_embed.bias", "class_predictor.bias")      )

		for i in range(3      ):
				rename_keys.append((F"""sem_seg_head.predictor.mask_embed.layers.{i}.weight""", F"""mask_embedder.{i}.0.weight""")      )
				rename_keys.append((F"""sem_seg_head.predictor.mask_embed.layers.{i}.bias""", F"""mask_embedder.{i}.0.bias""")      )
		# fmt: on

		return rename_keys






def        __lowerCAmelCase       (__lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase      ):
		_UpperCAmelCase						:				Optional[int]	    =					dct.pop(__lowerCAmelCase      )
		_UpperCAmelCase						:				Optional[Any]	    =					val






def        __lowerCAmelCase       (__lowerCAmelCase					,       __lowerCAmelCase      ):
		_UpperCAmelCase						:				Union[str, Any]	    =					[int(backbone_config.embed_dim * 2**i      ) for i in range(len(backbone_config.depths      )      )]
		for i in range(len(backbone_config.depths      )      ):
				_UpperCAmelCase						:				List[str]	    =					num_features[i]
				for j in range(backbone_config.depths[i]      ):
						# fmt: off
						# read in weights + bias of input projection layer (in original implementation, this is a single matrix + bias)
						_UpperCAmelCase						:				Dict	    =					state_dict.pop(F"""backbone.layers.{i}.blocks.{j}.attn.qkv.weight"""      )
						_UpperCAmelCase						:				int	    =					state_dict.pop(F"""backbone.layers.{i}.blocks.{j}.attn.qkv.bias"""      )
						# next, add query, keys and values (in that order) to the state dict
						_UpperCAmelCase						:				Any	    =					in_proj_weight[:dim, :]
						_UpperCAmelCase						:				List[str]	    =					in_proj_bias[: dim]
						_UpperCAmelCase						:				List[Any]	    =					in_proj_weight[
						    dim : dim * 2, :
						]
						_UpperCAmelCase						:				List[str]	    =					in_proj_bias[
						    dim : dim * 2
						]
						_UpperCAmelCase						:				Optional[Any]	    =					in_proj_weight[
						    -dim :, :
						]
						_UpperCAmelCase						:				int	    =					in_proj_bias[-dim :]
						# fmt: on






def        __lowerCAmelCase       (__lowerCAmelCase					,       __lowerCAmelCase      ):
		# fmt: off
		_UpperCAmelCase						:				str	    =					config.decoder_config.hidden_size
		for idx in range(config.decoder_config.decoder_layers      ):
				# read in weights + bias of self-attention input projection layer (in the original implementation, this is a single matrix + bias)
				_UpperCAmelCase						:				str	    =					state_dict.pop(F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.self_attn.in_proj_weight"""      )
				_UpperCAmelCase						:				List[str]	    =					state_dict.pop(F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.self_attn.in_proj_bias"""      )
				# next, add query, keys and values (in that order) to the state dict
				_UpperCAmelCase						:				Union[str, Any]	    =					in_proj_weight[: hidden_size, :]
				_UpperCAmelCase						:				int	    =					in_proj_bias[:config.hidden_size]
				_UpperCAmelCase						:				Union[str, Any]	    =					in_proj_weight[hidden_size : hidden_size * 2, :]
				_UpperCAmelCase						:				Optional[Any]	    =					in_proj_bias[hidden_size : hidden_size * 2]
				_UpperCAmelCase						:				Union[str, Any]	    =					in_proj_weight[-hidden_size :, :]
				_UpperCAmelCase						:				Any	    =					in_proj_bias[-hidden_size :]
				# read in weights + bias of cross-attention input projection layer (in the original implementation, this is a single matrix + bias)
				_UpperCAmelCase						:				List[str]	    =					state_dict.pop(F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.multihead_attn.in_proj_weight"""      )
				_UpperCAmelCase						:				Optional[int]	    =					state_dict.pop(F"""sem_seg_head.predictor.transformer.decoder.layers.{idx}.multihead_attn.in_proj_bias"""      )
				# next, add query, keys and values (in that order) to the state dict
				_UpperCAmelCase						:				str	    =					in_proj_weight[: hidden_size, :]
				_UpperCAmelCase						:				List[str]	    =					in_proj_bias[:config.hidden_size]
				_UpperCAmelCase						:				Any	    =					in_proj_weight[hidden_size : hidden_size * 2, :]
				_UpperCAmelCase						:				Optional[Any]	    =					in_proj_bias[hidden_size : hidden_size * 2]
				_UpperCAmelCase						:				Tuple	    =					in_proj_weight[-hidden_size :, :]
				_UpperCAmelCase						:				Tuple	    =					in_proj_bias[-hidden_size :]
		# fmt: on






def        __lowerCAmelCase       ():
		_UpperCAmelCase						:				Optional[int]	    =					"http://images.cocodataset.org/val2017/000000039769.jpg"
		_UpperCAmelCase						:				Optional[int]	    =					Image.open(requests.get(__lowerCAmelCase					,       stream=__lowerCAmelCase      ).raw      )
		return im






@torch.no_grad()
def        __lowerCAmelCase       (__lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase = False      ):
		_UpperCAmelCase						:				List[str]	    =					get_maskformer_config(__lowerCAmelCase      )

		# load original state_dict
		with open(__lowerCAmelCase					,       "rb"      ) as f:
				_UpperCAmelCase						:				Union[str, Any]	    =					pickle.load(__lowerCAmelCase      )
		_UpperCAmelCase						:				Union[str, Any]	    =					data["model"]

		# for name, param in state_dict.items():
		#     print(name, param.shape)

		# rename keys
		_UpperCAmelCase						:				int	    =					create_rename_keys(__lowerCAmelCase      )
		for src, dest in rename_keys:
				rename_key(__lowerCAmelCase					,       __lowerCAmelCase					,       __lowerCAmelCase      )
		read_in_swin_q_k_v(__lowerCAmelCase					,       config.backbone_config      )
		read_in_decoder_q_k_v(__lowerCAmelCase					,       __lowerCAmelCase      )

		# update to torch tensors
		for key, value in state_dict.items():
				_UpperCAmelCase						:				Optional[Any]	    =					torch.from_numpy(__lowerCAmelCase      )

		# load 🤗 model
		_UpperCAmelCase						:				Optional[Any]	    =					MaskFormerForInstanceSegmentation(__lowerCAmelCase      )
		model.eval()

		for name, param in model.named_parameters():
				print(__lowerCAmelCase					,       param.shape      )

		_UpperCAmelCase    ,			_UpperCAmelCase						:				Optional[Any]	    =					model.load_state_dict(__lowerCAmelCase					,       strict=__lowerCAmelCase      )
		assert missing_keys == [
		    "model.pixel_level_module.encoder.model.layernorm.weight",
		    "model.pixel_level_module.encoder.model.layernorm.bias",
		]
		assert len(__lowerCAmelCase      ) == 0, F"""Unexpected keys: {unexpected_keys}"""

		# verify results
		_UpperCAmelCase						:				Dict	    =					prepare_img()
		if "vistas" in model_name:
				_UpperCAmelCase						:				Optional[Any]	    =					65
		elif "cityscapes" in model_name:
				_UpperCAmelCase						:				Dict	    =					65_535
		else:
				_UpperCAmelCase						:				List[str]	    =					255
		_UpperCAmelCase						:				Any	    =					True if "ade" in model_name else False
		_UpperCAmelCase						:				Tuple	    =					MaskFormerImageProcessor(ignore_index=__lowerCAmelCase					,       reduce_labels=__lowerCAmelCase      )

		_UpperCAmelCase						:				Tuple	    =					image_processor(__lowerCAmelCase					,       return_tensors="pt"      )

		_UpperCAmelCase						:				List[str]	    =					model(**__lowerCAmelCase      )

		print("Logits:"					,       outputs.class_queries_logits[0, :3, :3]      )

		if model_name == "maskformer-swin-tiny-ade":
				_UpperCAmelCase						:				Optional[Any]	    =					torch.tensor(
				    [[3.6_3_5_3, -4.4_7_7_0, -2.6_0_6_5], [0.5_0_8_1, -4.2_3_9_4, -3.5_3_4_3], [2.1_9_0_9, -5.0_3_5_3, -1.9_3_2_3]]      )
		assert torch.allclose(outputs.class_queries_logits[0, :3, :3]					,       __lowerCAmelCase					,       atol=1e-4      )
		print("Looks ok!"      )

		if pytorch_dump_folder_path is not None:
				print(F"""Saving model and image processor to {pytorch_dump_folder_path}"""      )
				Path(__lowerCAmelCase      ).mkdir(exist_ok=__lowerCAmelCase      )
				model.save_pretrained(__lowerCAmelCase      )
				image_processor.save_pretrained(__lowerCAmelCase      )

		if push_to_hub:
				print("Pushing model and image processor to the hub..."      )
				model.push_to_hub(F"""nielsr/{model_name}"""      )
				image_processor.push_to_hub(F"""nielsr/{model_name}"""      )


if __name__ == "__main__":
						lowerCamelCase__					=   argparse.ArgumentParser()
						# Required parameters
						parser.add_argument(
						    '--model_name',
						    default='maskformer-swin-tiny-ade',
						    type=str,
						    help=('Name of the MaskFormer model you\'d like to convert',),
						)
						parser.add_argument(
						    '--checkpoint_path',
						    default='/Users/nielsrogge/Documents/MaskFormer_checkpoints/MaskFormer-Swin-tiny-ADE20k/model.pkl',
						    type=str,
						    help='Path to the original state dict (.pth file).',
						)
						parser.add_argument(
						    '--pytorch_dump_folder_path', default=None, type=str, help='Path to the output PyTorch model directory.'
						)
						parser.add_argument(
						    '--push_to_hub', action='store_true', help='Whether or not to push the converted model to the 🤗 hub.'
						)

						lowerCamelCase__					=   parser.parse_args()
						convert_maskformer_checkpoint(
						    args.model_name, args.checkpoint_path, args.pytorch_dump_folder_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



