



from typing import Optional, Tuple, Union

import tensorflow as tf

from ...activations_tf import ACTaFN
from ...file_utils import add_code_sample_docstrings, add_start_docstrings, add_start_docstrings_to_model_forward
from ...modeling_tf_outputs import (
    TFBaseModelOutputWithNoAttention,
    TFBaseModelOutputWithPoolingAndNoAttention,
    TFSequenceClassifierOutput,
)
from ...modeling_tf_utils import TFPreTrainedModel, TFSequenceClassificationLoss, keras_serializable, unpack_inputs
from ...tf_utils import shape_list
from ...utils import logging
from .configuration_regnet import RegNetConfig


SCREAMING_SNAKE_CASE     				=						logging.get_logger(__name__)

# General docstring
SCREAMING_SNAKE_CASE     				=						"RegNetConfig"

# Base docstring
SCREAMING_SNAKE_CASE     				=						"facebook/regnet-y-040"
SCREAMING_SNAKE_CASE     				=						[1, 1088, 7, 7]

# Image classification docstring
SCREAMING_SNAKE_CASE     				=						"facebook/regnet-y-040"
SCREAMING_SNAKE_CASE     				=						"tabby, tabby cat"

SCREAMING_SNAKE_CASE     				=						[
    "facebook/regnet-y-040",
    # See all regnet models at https://huggingface.co/models?filter=regnet
]



class 	lowerCamelCase      (						tf.keras.layers.Layer  ):







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase    ,	lowerCAmelCase = 3    ,	lowerCAmelCase = 1    ,	lowerCAmelCase = 1    ,	lowerCAmelCase = "relu"    ,	**lowerCAmelCase    ,	):
							super().__init__(**lowerCAmelCase     )
							# The padding and conv has been verified in
							# https://colab.research.google.com/gist/sayakpaul/854bc10eeaf21c9ee2119e0b9f3841a7/scratchpad.ipynb
							UpperCAmelCase_						=				tf.keras.layers.ZeroPaddingaD(padding=kernel_size // 2     )
							UpperCAmelCase_						=				tf.keras.layers.ConvaD(
							    filters=lowerCAmelCase    ,	kernel_size=lowerCAmelCase    ,	strides=lowerCAmelCase    ,	padding="VALID"    ,	groups=lowerCAmelCase    ,	use_bias=lowerCAmelCase    ,	name="convolution"    ,	)
							UpperCAmelCase_						=				tf.keras.layers.BatchNormalization(epsilon=1e-5    ,	momentum=0.9    ,	name="normalization"     )
							UpperCAmelCase_						=				ACTaFN[activation] if activation is not None else tf.identity



					def    A__		(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				self.convolution(self.padding(lowerCAmelCase     )     )
							UpperCAmelCase_						=				self.normalization(lowerCAmelCase     )
							UpperCAmelCase_						=				self.activation(lowerCAmelCase     )
							return hidden_state





class 	lowerCamelCase      (						tf.keras.layers.Layer  ):







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase    ,	**lowerCAmelCase     ):
							super().__init__(**lowerCAmelCase     )
							UpperCAmelCase_						=				config.num_channels
							UpperCAmelCase_						=				TFRegNetConvLayer(
							    out_channels=config.embedding_size    ,	kernel_size=3    ,	stride=2    ,	activation=config.hidden_act    ,	name="embedder"    ,	)



					def    A__		(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				shape_list(lowerCAmelCase     )[1]
							if tf.executing_eagerly() and num_channels != self.num_channels:
									raise ValueError(
									    "Make sure that the channel dimension of the pixel values match with the one set in the configuration."     )

							# When running on CPU, `tf.keras.layers.Conv2D` doesn't support `NCHW` format.
							# So change the input format from `NCHW` to `NHWC`.
							# shape = (batch_size, in_height, in_width, in_channels=num_channels)
							UpperCAmelCase_						=				tf.transpose(lowerCAmelCase    ,	perm=(0, 2, 3, 1)     )
							UpperCAmelCase_						=				self.embedder(lowerCAmelCase     )
							return hidden_state





class 	lowerCamelCase      (						tf.keras.layers.Layer  ):







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase    ,	lowerCAmelCase = 2    ,	**lowerCAmelCase     ):
							super().__init__(**lowerCAmelCase     )
							UpperCAmelCase_						=				tf.keras.layers.ConvaD(
							    filters=lowerCAmelCase    ,	kernel_size=1    ,	strides=lowerCAmelCase    ,	use_bias=lowerCAmelCase    ,	name="convolution"     )
							UpperCAmelCase_						=				tf.keras.layers.BatchNormalization(epsilon=1e-5    ,	momentum=0.9    ,	name="normalization"     )



					def    A__		(			self    ,	lowerCAmelCase    ,	lowerCAmelCase = False     ):
							return self.normalization(self.convolution(lowerCAmelCase     )    ,	training=lowerCAmelCase     )





class 	lowerCamelCase      (						tf.keras.layers.Layer  ):







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	**lowerCAmelCase     ):
							super().__init__(**lowerCAmelCase     )
							UpperCAmelCase_						=				tf.keras.layers.GlobalAveragePoolingaD(keepdims=lowerCAmelCase    ,	name="pooler"     )
							UpperCAmelCase_						=				[
							    tf.keras.layers.ConvaD(filters=lowerCAmelCase    ,	kernel_size=1    ,	activation="relu"    ,	name="attention.0"     ),
							    tf.keras.layers.ConvaD(filters=lowerCAmelCase    ,	kernel_size=1    ,	activation="sigmoid"    ,	name="attention.2"     ),
							]



					def    A__		(			self    ,	lowerCAmelCase     ):
							# [batch_size, h, w, num_channels] -> [batch_size, 1, 1, num_channels]
							UpperCAmelCase_						=				self.pooler(lowerCAmelCase     )
							for layer_module in self.attention:
									UpperCAmelCase_						=				layer_module(lowerCAmelCase     )
							UpperCAmelCase_						=				hidden_state * pooled
							return hidden_state





class 	lowerCamelCase      (						tf.keras.layers.Layer  ):







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase = 1    ,	**lowerCAmelCase     ):
							super().__init__(**lowerCAmelCase     )
							UpperCAmelCase_						=				in_channels != out_channels or stride != 1
							UpperCAmelCase_						=				max(1    ,	out_channels // config.groups_width     )
							UpperCAmelCase_						=				(
							    TFRegNetShortCut(lowerCAmelCase    ,	stride=lowerCAmelCase    ,	name="shortcut"     )
							    if should_apply_shortcut
							    else tf.keras.layers.Activation("linear"    ,	name="shortcut"     )
							)
							# `self.layers` instead of `self.layer` because that is a reserved argument.
							UpperCAmelCase_						=				[
							    TFRegNetConvLayer(lowerCAmelCase    ,	kernel_size=1    ,	activation=config.hidden_act    ,	name="layer.0"     ),
							    TFRegNetConvLayer(
							        lowerCAmelCase    ,	stride=lowerCAmelCase    ,	groups=lowerCAmelCase    ,	activation=config.hidden_act    ,	name="layer.1"     ),
							    TFRegNetConvLayer(lowerCAmelCase    ,	kernel_size=1    ,	activation=lowerCAmelCase    ,	name="layer.2"     ),
							]
							UpperCAmelCase_						=				ACTaFN[config.hidden_act]



					def    A__		(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				hidden_state
							for layer_module in self.layers:
									UpperCAmelCase_						=				layer_module(lowerCAmelCase     )
							UpperCAmelCase_						=				self.shortcut(lowerCAmelCase     )
							hidden_state += residual
							UpperCAmelCase_						=				self.activation(lowerCAmelCase     )
							return hidden_state





class 	lowerCamelCase      (						tf.keras.layers.Layer  ):







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase = 1    ,	**lowerCAmelCase     ):
							super().__init__(**lowerCAmelCase     )
							UpperCAmelCase_						=				in_channels != out_channels or stride != 1
							UpperCAmelCase_						=				max(1    ,	out_channels // config.groups_width     )
							UpperCAmelCase_						=				(
							    TFRegNetShortCut(lowerCAmelCase    ,	stride=lowerCAmelCase    ,	name="shortcut"     )
							    if should_apply_shortcut
							    else tf.keras.layers.Activation("linear"    ,	name="shortcut"     )
							)
							UpperCAmelCase_						=				[
							    TFRegNetConvLayer(lowerCAmelCase    ,	kernel_size=1    ,	activation=config.hidden_act    ,	name="layer.0"     ),
							    TFRegNetConvLayer(
							        lowerCAmelCase    ,	stride=lowerCAmelCase    ,	groups=lowerCAmelCase    ,	activation=config.hidden_act    ,	name="layer.1"     ),
							    TFRegNetSELayer(lowerCAmelCase    ,	reduced_channels=int(round(in_channels / 4     )     )    ,	name="layer.2"     ),
							    TFRegNetConvLayer(lowerCAmelCase    ,	kernel_size=1    ,	activation=lowerCAmelCase    ,	name="layer.3"     ),
							]
							UpperCAmelCase_						=				ACTaFN[config.hidden_act]



					def    A__		(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				hidden_state
							for layer_module in self.layers:
									UpperCAmelCase_						=				layer_module(lowerCAmelCase     )
							UpperCAmelCase_						=				self.shortcut(lowerCAmelCase     )
							hidden_state += residual
							UpperCAmelCase_						=				self.activation(lowerCAmelCase     )
							return hidden_state





class 	lowerCamelCase      (						tf.keras.layers.Layer  ):







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase = 2    ,	lowerCAmelCase = 2    ,	**lowerCAmelCase     ):
							super().__init__(**lowerCAmelCase     )

							UpperCAmelCase_						=				TFRegNetXLayer if config.layer_type == "x" else TFRegNetYLayer
							UpperCAmelCase_						=				[
							    # downsampling is done in the first layer with stride of 2
							    layer(lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	stride=lowerCAmelCase    ,	name="layers.0"     ),
							    *[layer(lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	name=f'''layers.{i+1}'''     ) for i in range(depth - 1     )],
							]



					def    A__		(			self    ,	lowerCAmelCase     ):
							for layer_module in self.layers:
									UpperCAmelCase_						=				layer_module(lowerCAmelCase     )
							return hidden_state





class 	lowerCamelCase      (						tf.keras.layers.Layer  ):







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase    ,	**lowerCAmelCase     ):
							super().__init__(**lowerCAmelCase     )
							UpperCAmelCase_						=				[]
							# based on `downsample_in_first_stage`, the first layer of the first stage may or may not downsample the input
							self.stages.append(
							    TFRegNetStage(
							        lowerCAmelCase    ,	config.embedding_size    ,	config.hidden_sizes[0]    ,	stride=2 if config.downsample_in_first_stage else 1    ,	depth=config.depths[0]    ,	name="stages.0"    ,	)     )
							UpperCAmelCase_						=				zip(config.hidden_sizes    ,	config.hidden_sizes[1:]     )
							for i, ((in_channels, out_channels), depth) in enumerate(zip(lowerCAmelCase    ,	config.depths[1:]     )     ):
									self.stages.append(TFRegNetStage(lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	depth=lowerCAmelCase    ,	name=f'''stages.{i+1}'''     )     )



					def    A__		(			self    ,	lowerCAmelCase    ,	lowerCAmelCase = False    ,	lowerCAmelCase = True     ):
							UpperCAmelCase_						=				() if output_hidden_states else None

							for stage_module in self.stages:
									if output_hidden_states:
											UpperCAmelCase_						=				hidden_states + (hidden_state,)

									UpperCAmelCase_						=				stage_module(lowerCAmelCase     )

							if output_hidden_states:
									UpperCAmelCase_						=				hidden_states + (hidden_state,)

							if not return_dict:
									return tuple(v for v in [hidden_state, hidden_states] if v is not None     )

							return TFBaseModelOutputWithNoAttention(last_hidden_state=lowerCAmelCase    ,	hidden_states=lowerCAmelCase     )





@keras_serializable
class 	lowerCamelCase      (						tf.keras.layers.Layer  ):







					'''simple docstring'''







					lowerCAmelCase_				:    Tuple									=  RegNetConfig



					def __init__(			self    ,	lowerCAmelCase    ,	**lowerCAmelCase     ):
							super().__init__(**lowerCAmelCase     )
							UpperCAmelCase_						=				config
							UpperCAmelCase_						=				TFRegNetEmbeddings(lowerCAmelCase    ,	name="embedder"     )
							UpperCAmelCase_						=				TFRegNetEncoder(lowerCAmelCase    ,	name="encoder"     )
							UpperCAmelCase_						=				tf.keras.layers.GlobalAveragePoolingaD(keepdims=lowerCAmelCase    ,	name="pooler"     )



					@unpack_inputs
					def    A__		(			self    ,	lowerCAmelCase    ,	lowerCAmelCase = None    ,	lowerCAmelCase = None    ,	lowerCAmelCase = False    ,	):
							UpperCAmelCase_						=				(
							    output_hidden_states if output_hidden_states is not None else self.config.output_hidden_states
							)
							UpperCAmelCase_						=				return_dict if return_dict is not None else self.config.use_return_dict

							UpperCAmelCase_						=				self.embedder(lowerCAmelCase    ,	training=lowerCAmelCase     )

							UpperCAmelCase_						=				self.encoder(
							    lowerCAmelCase    ,	output_hidden_states=lowerCAmelCase    ,	return_dict=lowerCAmelCase    ,	training=lowerCAmelCase     )

							UpperCAmelCase_						=				encoder_outputs[0]
							UpperCAmelCase_						=				self.pooler(lowerCAmelCase     )

							# Change to NCHW output format have uniformity in the modules
							UpperCAmelCase_						=				tf.transpose(lowerCAmelCase    ,	perm=(0, 3, 1, 2)     )
							UpperCAmelCase_						=				tf.transpose(lowerCAmelCase    ,	perm=(0, 3, 1, 2)     )

							# Change the other hidden state outputs to NCHW as well
							if output_hidden_states:
									UpperCAmelCase_						=				tuple([tf.transpose(lowerCAmelCase    ,	perm=(0, 3, 1, 2)     ) for h in encoder_outputs[1]]     )

							if not return_dict:
									return (last_hidden_state, pooled_output) + encoder_outputs[1:]

							return TFBaseModelOutputWithPoolingAndNoAttention(
							    last_hidden_state=lowerCAmelCase    ,	pooler_output=lowerCAmelCase    ,	hidden_states=hidden_states if output_hidden_states else encoder_outputs.hidden_states    ,	)





class 	lowerCamelCase      (						lowercase__  ):







					'''simple docstring'''







					lowerCAmelCase_				:    Tuple									=  RegNetConfig
					lowerCAmelCase_				:    Union[str, Any]									=  'regnet'
					lowerCAmelCase_				:    Optional[int]									=  'pixel_values'



					@property
					def    A__		(			self     ):
							return {"pixel_values": tf.TensorSpec(shape=(None, self.config.num_channels, 224, 224)    ,	dtype=tf.floataa     )}





SCREAMING_SNAKE_CASE     				=						R"\n    Parameters:\n    This model is a Tensorflow\n    [tf.keras.layers.Layer](https://www.tensorflow.org/api_docs/python/tf/keras/layers/Layer) sub-class. Use it as a\n    regular Tensorflow Module and refer to the Tensorflow documentation for all matter related to general usage and\n    behavior.\n        config ([`RegNetConfig`]): Model configuration class with all the parameters of the model.\n            Initializing with a config file does not load the weights associated with the model, only the\n            configuration. Check out the [`~TFPreTrainedModel.from_pretrained`] method to load the model weights.\n"

SCREAMING_SNAKE_CASE     				=						R"\n    Args:\n        pixel_values (`tf.Tensor` of shape `(batch_size, num_channels, height, width)`):\n            Pixel values. Pixel values can be obtained using [`AutoImageProcessor`]. See\n            [`ConveNextImageProcessor.__call__`] for details.\n        output_hidden_states (`bool`, *optional*):\n            Whether or not to return the hidden states of all layers. See `hidden_states` under returned tensors for\n            more detail.\n        return_dict (`bool`, *optional*):\n            Whether or not to return a [`~utils.ModelOutput`] instead of a plain tuple.\n"



@add_start_docstrings(
    'The bare RegNet model outputting raw features without any specific head on top.',     lowercase__,     )
class 	lowerCamelCase      (						lowercase__  ):







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase    ,	*lowerCAmelCase    ,	**lowerCAmelCase     ):
							super().__init__(lowerCAmelCase    ,	*lowerCAmelCase    ,	**lowerCAmelCase     )
							UpperCAmelCase_						=				TFRegNetMainLayer(lowerCAmelCase    ,	name="regnet"     )



					@unpack_inputs
					@add_start_docstrings_to_model_forward(lowerCAmelCase     )
					@add_code_sample_docstrings(
					    checkpoint=_CHECKPOINT_FOR_DOC    ,	output_type=lowerCAmelCase    ,	config_class=_CONFIG_FOR_DOC    ,	modality="vision"    ,	expected_output=_EXPECTED_OUTPUT_SHAPE    ,	)
					def    A__		(			self    ,	lowerCAmelCase    ,	lowerCAmelCase = None    ,	lowerCAmelCase = None    ,	lowerCAmelCase=False    ,	):
							UpperCAmelCase_						=				(
							    output_hidden_states if output_hidden_states is not None else self.config.output_hidden_states
							)
							UpperCAmelCase_						=				return_dict if return_dict is not None else self.config.use_return_dict

							UpperCAmelCase_						=				self.regnet(
							    pixel_values=lowerCAmelCase    ,	output_hidden_states=lowerCAmelCase    ,	return_dict=lowerCAmelCase    ,	training=lowerCAmelCase    ,	)
							if not return_dict:
									return (outputs[0],) + outputs[1:]

							return TFBaseModelOutputWithPoolingAndNoAttention(
							    last_hidden_state=outputs.last_hidden_state    ,	pooler_output=outputs.pooler_output    ,	hidden_states=outputs.hidden_states    ,	)





@add_start_docstrings(
    '\n    RegNet Model with an image classification head on top (a linear layer on top of the pooled features), e.g. for\n    ImageNet.\n    ',     lowercase__,     )
class 	lowerCamelCase      (						lowercase__,     lowercase__  ):







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase    ,	*lowerCAmelCase    ,	**lowerCAmelCase     ):
							super().__init__(lowerCAmelCase    ,	*lowerCAmelCase    ,	**lowerCAmelCase     )
							UpperCAmelCase_						=				config.num_labels
							UpperCAmelCase_						=				TFRegNetMainLayer(lowerCAmelCase    ,	name="regnet"     )
							# classification head
							UpperCAmelCase_						=				[
							    tf.keras.layers.Flatten(),
							    tf.keras.layers.Dense(config.num_labels    ,	name="classifier.1"     ) if config.num_labels > 0 else tf.identity,
							]



					@unpack_inputs
					@add_start_docstrings_to_model_forward(lowerCAmelCase     )
					@add_code_sample_docstrings(
					    checkpoint=_IMAGE_CLASS_CHECKPOINT    ,	output_type=lowerCAmelCase    ,	config_class=_CONFIG_FOR_DOC    ,	expected_output=_IMAGE_CLASS_EXPECTED_OUTPUT    ,	)
					def    A__		(			self    ,	lowerCAmelCase = None    ,	lowerCAmelCase = None    ,	lowerCAmelCase = None    ,	lowerCAmelCase = None    ,	lowerCAmelCase=False    ,	):
							UpperCAmelCase_						=				(
							    output_hidden_states if output_hidden_states is not None else self.config.output_hidden_states
							)
							UpperCAmelCase_						=				return_dict if return_dict is not None else self.config.use_return_dict

							UpperCAmelCase_						=				self.regnet(
							    lowerCAmelCase    ,	output_hidden_states=lowerCAmelCase    ,	return_dict=lowerCAmelCase    ,	training=lowerCAmelCase     )

							UpperCAmelCase_						=				outputs.pooler_output if return_dict else outputs[1]

							UpperCAmelCase_						=				self.classifier[0](lowerCAmelCase     )
							UpperCAmelCase_						=				self.classifier[1](lowerCAmelCase     )

							UpperCAmelCase_						=				None if labels is None else self.hf_compute_loss(labels=lowerCAmelCase    ,	logits=lowerCAmelCase     )

							if not return_dict:
									UpperCAmelCase_						=				(logits,) + outputs[2:]
									return ((loss,) + output) if loss is not None else output

							return TFSequenceClassifierOutput(loss=lowerCAmelCase    ,	logits=lowerCAmelCase    ,	hidden_states=outputs.hidden_states     )






import heapq as hq
import math
from collections.abc import Iterator



class 	lowerCamelCase      :







					'''simple docstring'''







					def __init__(			self    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				str(id_     )
							UpperCAmelCase_						=				None
							UpperCAmelCase_						=				None
							UpperCAmelCase_						=				[]
							UpperCAmelCase_						=				{}  # {vertex:distance}



					def __lt__(			self    ,	lowerCAmelCase     ):
							return self.key < other.key



					def __repr__(			self     ):
							return self.id



					def    A__		(			self    ,	lowerCAmelCase     ):
							self.neighbors.append(lowerCAmelCase     )



					def    A__		(			self    ,	lowerCAmelCase    ,	lowerCAmelCase     ):
							UpperCAmelCase_						=				weight







def snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							Optional[int]:
		# add the neighbors:
		graph[a - 1].add_neighbor(graph[b - 1] )
		graph[b - 1].add_neighbor(graph[a - 1] )
		# add the edges:
		graph[a - 1].add_edge(graph[b - 1]			,     __SCREAMING_SNAKE_CASE )
		graph[b - 1].add_edge(graph[a - 1]			,     __SCREAMING_SNAKE_CASE )







def snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							list:
		UpperCAmelCase_						=				[]
		for u in graph:
				UpperCAmelCase_						=				math.inf
				UpperCAmelCase_						=				None
		UpperCAmelCase_						=				0
		UpperCAmelCase_						=				graph[:]
		while q:
				UpperCAmelCase_						=				min(__SCREAMING_SNAKE_CASE )
				q.remove(__SCREAMING_SNAKE_CASE )
				for v in u.neighbors:
						if (v in q) and (u.edges[v.id] < v.key):
								UpperCAmelCase_						=				u
								UpperCAmelCase_						=				u.edges[v.id]
		for i in range(1			,     len(__SCREAMING_SNAKE_CASE ) ):
				a.append((int(graph[i].id ) + 1, int(graph[i].pi.id ) + 1) )
		return a







def snake_case__  (			__SCREAMING_SNAKE_CASE			,     __SCREAMING_SNAKE_CASE )		->							Iterator[tuple]:
		for u in graph:
				UpperCAmelCase_						=				math.inf
				UpperCAmelCase_						=				None
		UpperCAmelCase_						=				0

		UpperCAmelCase_						=				list(__SCREAMING_SNAKE_CASE )
		hq.heapify(__SCREAMING_SNAKE_CASE )

		while h:
				UpperCAmelCase_						=				hq.heappop(__SCREAMING_SNAKE_CASE )
				for v in u.neighbors:
						if (v in h) and (u.edges[v.id] < v.key):
								UpperCAmelCase_						=				u
								UpperCAmelCase_						=				u.edges[v.id]
								hq.heapify(__SCREAMING_SNAKE_CASE )

		for i in range(1			,     len(__SCREAMING_SNAKE_CASE ) ):
				yield (int(graph[i].id ) + 1, int(graph[i].pi.id ) + 1)







def snake_case__  (			)		->							None:
		pass


if __name__ == "__main__":
			import doctest

			doctest.testmod()

