

"""simple docstring"""





import argparse
import json
from pathlib import Path

import requests
import timm
import torch
from huggingface_hub import hf_hub_download
from PIL import Image
from timm.data import resolve_data_config
from timm.data.transforms_factory import create_transform

from transformers import (
    BitConfig,
    ViTHybridConfig,
    ViTHybridForImageClassification,
    ViTHybridImageProcessor,
    ViTHybridModel,
)
from transformers.image_utils import PILImageResampling
from transformers.utils import logging


logging.set_verbosity_info()
__UpperCamelCase    : Tuple				 =						logging.get_logger(__name__)

def     __SCREAMING_SNAKE_CASE    ( A_		,	A_=False					):
	lowerCAmelCase__      :		Optional[int]    							=      []

	# fmt: off
	# stem:
	rename_keys.append(('''cls_token''', '''vit.embeddings.cls_token''')					)
	rename_keys.append(('''pos_embed''', '''vit.embeddings.position_embeddings''')					)

	rename_keys.append(('''patch_embed.proj.weight''', '''vit.embeddings.patch_embeddings.projection.weight''')					)
	rename_keys.append(('''patch_embed.proj.bias''', '''vit.embeddings.patch_embeddings.projection.bias''')					)

	# backbone
	rename_keys.append(('''patch_embed.backbone.stem.conv.weight''', '''vit.embeddings.patch_embeddings.backbone.bit.embedder.convolution.weight''')					)
	rename_keys.append(('''patch_embed.backbone.stem.norm.weight''', '''vit.embeddings.patch_embeddings.backbone.bit.embedder.norm.weight''')					)
	rename_keys.append(('''patch_embed.backbone.stem.norm.bias''', '''vit.embeddings.patch_embeddings.backbone.bit.embedder.norm.bias''')					)

	for stage_idx in range(len(config.backbone_config.depths					)					):
		for layer_idx in range(config.backbone_config.depths[stage_idx]					):
			rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.{layer_idx}.conv1.weight', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.{layer_idx}.conv1.weight')					)
			rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.{layer_idx}.norm1.weight', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.{layer_idx}.norm1.weight')					)
			rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.{layer_idx}.norm1.bias', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.{layer_idx}.norm1.bias')					)
			rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.{layer_idx}.conv2.weight', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.{layer_idx}.conv2.weight')					)
			rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.{layer_idx}.norm2.weight', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.{layer_idx}.norm2.weight')					)
			rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.{layer_idx}.norm2.bias', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.{layer_idx}.norm2.bias')					)
			rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.{layer_idx}.conv3.weight', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.{layer_idx}.conv3.weight')					)
			rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.{layer_idx}.norm3.weight', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.{layer_idx}.norm3.weight')					)
			rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.{layer_idx}.norm3.bias', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.{layer_idx}.norm3.bias')					)

		rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.0.downsample.conv.weight', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.0.downsample.conv.weight')					)
		rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.0.downsample.norm.weight', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.0.downsample.norm.weight')					)
		rename_keys.append((f'patch_embed.backbone.stages.{stage_idx}.blocks.0.downsample.norm.bias', f'vit.embeddings.patch_embeddings.backbone.bit.encoder.stages.{stage_idx}.layers.0.downsample.norm.bias')					)

	# transformer encoder
	for i in range(config.num_hidden_layers					):
		# encoder layers: output projection, 2 feedforward neural networks and 2 layernorms
		rename_keys.append((f'blocks.{i}.norm1.weight', f'vit.encoder.layer.{i}.layernorm_before.weight')					)
		rename_keys.append((f'blocks.{i}.norm1.bias', f'vit.encoder.layer.{i}.layernorm_before.bias')					)
		rename_keys.append((f'blocks.{i}.attn.proj.weight', f'vit.encoder.layer.{i}.attention.output.dense.weight')					)
		rename_keys.append((f'blocks.{i}.attn.proj.bias', f'vit.encoder.layer.{i}.attention.output.dense.bias')					)
		rename_keys.append((f'blocks.{i}.norm2.weight', f'vit.encoder.layer.{i}.layernorm_after.weight')					)
		rename_keys.append((f'blocks.{i}.norm2.bias', f'vit.encoder.layer.{i}.layernorm_after.bias')					)
		rename_keys.append((f'blocks.{i}.mlp.fc1.weight', f'vit.encoder.layer.{i}.intermediate.dense.weight')					)
		rename_keys.append((f'blocks.{i}.mlp.fc1.bias', f'vit.encoder.layer.{i}.intermediate.dense.bias')					)
		rename_keys.append((f'blocks.{i}.mlp.fc2.weight', f'vit.encoder.layer.{i}.output.dense.weight')					)
		rename_keys.append((f'blocks.{i}.mlp.fc2.bias', f'vit.encoder.layer.{i}.output.dense.bias')					)

	if base_model:
		# layernorm + pooler
		rename_keys.extend(
		    [
		        ('''norm.weight''', '''layernorm.weight'''),
		        ('''norm.bias''', '''layernorm.bias'''),
		        ('''pre_logits.fc.weight''', '''pooler.dense.weight'''),
		        ('''pre_logits.fc.bias''', '''pooler.dense.bias'''),
		    ]					)

		# if just the base model, we should remove "vit" from all keys that start with "vit"
		lowerCAmelCase__      :		Optional[Any]    							=      [(pair[0], pair[1][4:]) if pair[1].startswith('''vit'''					) else pair for pair in rename_keys]
	else:
		# layernorm + classification head
		rename_keys.extend(
		    [
		        ('''norm.weight''', '''vit.layernorm.weight'''),
		        ('''norm.bias''', '''vit.layernorm.bias'''),
		        ('''head.weight''', '''classifier.weight'''),
		        ('''head.bias''', '''classifier.bias'''),
		    ]					)
	# fmt: on

	return rename_keys

def     __SCREAMING_SNAKE_CASE    ( A_		,	A_		,	A_=False					):
	for i in range(config.num_hidden_layers					):
		if base_model:
			lowerCAmelCase__      :		List[Any]    							=      ''''''
		else:
			lowerCAmelCase__      :		Optional[int]    							=      '''vit.'''
		# read in weights + bias of input projection layer (in timm, this is a single matrix + bias)
		lowerCAmelCase__      :		List[str]    							=      state_dict.pop(f'blocks.{i}.attn.qkv.weight'					)
		lowerCAmelCase__      :		List[Any]    							=      state_dict.pop(f'blocks.{i}.attn.qkv.bias'					)
		# next, add query, keys and values (in that order) to the state dict
		lowerCAmelCase__      :		Optional[Any]    							=      in_proj_weight[
		    : config.hidden_size, :
		]
		lowerCAmelCase__      :		Optional[Any]    							=      in_proj_bias[: config.hidden_size]
		lowerCAmelCase__      :		Dict    							=      in_proj_weight[
		    config.hidden_size : config.hidden_size * 2, :
		]
		lowerCAmelCase__      :		Any    							=      in_proj_bias[
		    config.hidden_size : config.hidden_size * 2
		]
		lowerCAmelCase__      :		Optional[Any]    							=      in_proj_weight[
		    -config.hidden_size :, :
		]
		lowerCAmelCase__      :		Dict    							=      in_proj_bias[-config.hidden_size :]

def     __SCREAMING_SNAKE_CASE    ( A_					):
	lowerCAmelCase__      :		Optional[Any]    							=      ['''head.weight''', '''head.bias''']
	for k in ignore_keys:
		state_dict.pop(A_		,	A_					)

def     __SCREAMING_SNAKE_CASE    ( A_		,	A_		,	A_					):
	lowerCAmelCase__      :		Any    							=      dct.pop(A_					)
	lowerCAmelCase__      :		List[str]    							=      val

def     __SCREAMING_SNAKE_CASE    ( ):
	lowerCAmelCase__      :		Optional[Any]    							=      '''http://images.cocodataset.org/val2017/000000039769.jpg'''
	lowerCAmelCase__      :		List[Any]    							=      Image.open(requests.get(A_		,	stream=A_					).raw					)
	return im

@torch.no_grad()
def     __SCREAMING_SNAKE_CASE    ( A_		,	A_		,	A_=False					):
	lowerCAmelCase__      :		List[Any]    							=      BitConfig(
	    global_padding='''same'''		,	layer_type='''bottleneck'''		,	depths=(3, 4, 9)		,	out_features=['''stage3''']		,	embedding_dynamic_padding=A_		,	)
	lowerCAmelCase__      :		Tuple    							=      ViTHybridConfig(backbone_config=A_		,	image_size=3_84		,	num_labels=10_00					)
	lowerCAmelCase__      :		str    							=      False

	# load original model from timm
	lowerCAmelCase__      :		List[str]    							=      timm.create_model(A_		,	pretrained=A_					)
	timm_model.eval()

	# load state_dict of original model, remove and rename some keys
	lowerCAmelCase__      :		Optional[int]    							=      timm_model.state_dict()
	if base_model:
		remove_classification_head_(A_					)
	lowerCAmelCase__      :		int    							=      create_rename_keys(A_		,	A_					)
	for src, dest in rename_keys:
		rename_key(A_		,	A_		,	A_					)
	read_in_q_k_v(A_		,	A_		,	A_					)

	lowerCAmelCase__      :		Dict    							=      '''huggingface/label-files'''
	lowerCAmelCase__      :		Optional[int]    							=      '''imagenet-1k-id2label.json'''
	lowerCAmelCase__      :		Optional[int]    							=      json.load(open(hf_hub_download(A_		,	A_		,	repo_type='''dataset'''					)		,	'''r'''					)					)
	lowerCAmelCase__      :		Any    							=      {int(A_					): v for k, v in idalabel.items()}
	lowerCAmelCase__      :		Dict    							=      idalabel
	lowerCAmelCase__      :		List[Any]    							=      {v: k for k, v in idalabel.items()}

	# load HuggingFace model
	if vit_name[-5:] == "in21k":
		lowerCAmelCase__      :		List[Any]    							=      ViTHybridModel(A_					).eval()
	else:
		lowerCAmelCase__      :		Optional[int]    							=      ViTHybridForImageClassification(A_					).eval()
	model.load_state_dict(A_					)

	# create image processor
	lowerCAmelCase__      :		List[Any]    							=      create_transform(**resolve_data_config({}		,	model=A_					)					)
	lowerCAmelCase__      :		Optional[Any]    							=      transform.transforms

	lowerCAmelCase__      :		Optional[Any]    							=      {
	    '''bilinear''': PILImageResampling.BILINEAR,
	    '''bicubic''': PILImageResampling.BICUBIC,
	    '''nearest''': PILImageResampling.NEAREST,
	}

	lowerCAmelCase__      :		Optional[int]    							=      ViTHybridImageProcessor(
	    do_resize=A_		,	size={'''shortest_edge''': timm_transforms[0].size}		,	resample=pillow_resamplings[timm_transforms[0].interpolation.value]		,	do_center_crop=A_		,	crop_size={'''height''': timm_transforms[1].size[0], '''width''': timm_transforms[1].size[1]}		,	do_normalize=A_		,	image_mean=timm_transforms[-1].mean.tolist()		,	image_std=timm_transforms[-1].std.tolist()		,	)

	lowerCAmelCase__      :		str    							=      prepare_img()
	lowerCAmelCase__      :		str    							=      transform(A_					).unsqueeze(0					)
	lowerCAmelCase__      :		Optional[Any]    							=      processor(A_		,	return_tensors='''pt'''					).pixel_values

	# verify pixel values
	assert torch.allclose(A_		,	A_					)

	# verify logits
	with torch.no_grad():
		lowerCAmelCase__      :		List[Any]    							=      model(A_					)
		lowerCAmelCase__      :		Tuple    							=      outputs.logits

	print('''Predicted class:'''		,	logits.argmax(-1					).item()					)
	if base_model:
		lowerCAmelCase__      :		Tuple    							=      timm_model.forward_features(A_					)
		assert timm_pooled_output.shape == outputs.pooler_output.shape
		assert torch.allclose(A_		,	outputs.pooler_output		,	atol=1e-3					)
	else:
		lowerCAmelCase__      :		Optional[Any]    							=      timm_model(A_					)
		assert timm_logits.shape == outputs.logits.shape
		assert torch.allclose(A_		,	outputs.logits		,	atol=1e-3					)
	print('''Looks ok!'''					)

	if pytorch_dump_folder_path is not None:
		Path(A_					).mkdir(exist_ok=A_					)
		print(f'Saving model {vit_name} to {pytorch_dump_folder_path}'					)
		model.save_pretrained(A_					)
		print(f'Saving processor to {pytorch_dump_folder_path}'					)
		processor.save_pretrained(A_					)

	if push_to_hub:
		print(f'Pushing model and processor to the hub {vit_name}'					)
		model.push_to_hub(f'ybelkada/{vit_name}'					)
		processor.push_to_hub(f'ybelkada/{vit_name}'					)


if __name__ == "__main__":
							__UpperCamelCase    : str				 =						argparse.ArgumentParser()
							# Required parameters
							parser.add_argument(
							    '''--vit_name''',
							    default='''vit_base_r50_s16_384''',
							    type=str,
							    help='''Name of the hybrid ViT timm model you\'d like to convert.''',
							)
							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 to upload the model to the HuggingFace hub.'''
							)

							__UpperCamelCase    : str				 =						parser.parse_args()
							convert_vit_checkpoint(args.vit_name, 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 							SCREAMING_SNAKE_CASE   :






					"""simple docstring"""



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







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







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







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







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

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

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

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







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







					def 			__lowerCAmelCase					(			self     :							Optional[Any]  ,lowercase_     :							Union[str, Any]=-2						):
						lowerCAmelCase__      :		Tuple    							=      deque()
						lowerCAmelCase__      :		Tuple    							=      []
						if s == -2:
							lowerCAmelCase__      :		Any    							=      list(self.graph						)[0]
						d.append(lowercase_						)
						visited.append(lowercase_						)
						while d:
							lowerCAmelCase__      :		Dict    							=      d.popleft()
							if len(self.graph[s]						) != 0:
								for node in self.graph[s]:
									if visited.count(node[1]						) < 1:
										d.append(node[1]						)
										visited.append(node[1]						)
						return visited







					def 			__lowerCAmelCase					(			self     :							Union[str, Any]  ,lowercase_     :							Optional[Any]						):
						lowerCAmelCase__      :		Optional[Any]    							=      0
						for x in self.graph:
							for y in self.graph[x]:
								if y[1] == u:
									count += 1
						return count







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







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

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

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

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







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

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

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

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







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

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

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

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







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







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







class 							SCREAMING_SNAKE_CASE   :






					"""simple docstring"""



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







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







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







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

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

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

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







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







					def 			__lowerCAmelCase					(			self     :							Optional[Any]  ,lowercase_     :							List[Any]=-2						):
						lowerCAmelCase__      :		Tuple    							=      deque()
						lowerCAmelCase__      :		List[Any]    							=      []
						if s == -2:
							lowerCAmelCase__      :		Tuple    							=      list(self.graph						)[0]
						d.append(lowercase_						)
						visited.append(lowercase_						)
						while d:
							lowerCAmelCase__      :		Any    							=      d.popleft()
							if len(self.graph[s]						) != 0:
								for node in self.graph[s]:
									if visited.count(node[1]						) < 1:
										d.append(node[1]						)
										visited.append(node[1]						)
						return visited







					def 			__lowerCAmelCase					(			self     :							Any  ,lowercase_     :							Any						):
						return len(self.graph[u]						)







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

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

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

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







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

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

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

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







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







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







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




