
'''simple docstring'''



import os
import shutil
import sys
import tempfile
import unittest
from pathlib import Path

import pytest

import transformers
from transformers import (
    BERT_PRETRAINED_CONFIG_ARCHIVE_MAP,
    GPT2_PRETRAINED_CONFIG_ARCHIVE_MAP,
    AutoTokenizer,
    BertConfig,
    BertTokenizer,
    BertTokenizerFast,
    CTRLTokenizer,
    GPTaTokenizer,
    GPTaTokenizerFast,
    PreTrainedTokenizerFast,
    RobertaTokenizer,
    RobertaTokenizerFast,
    is_tokenizers_available,
)
from transformers.models.auto.configuration_auto import CONFIG_MAPPING, AutoConfig
from transformers.models.auto.tokenization_auto import (
    TOKENIZER_MAPPING,
    get_tokenizer_config,
    tokenizer_class_from_name,
)
from transformers.models.roberta.configuration_roberta import RobertaConfig
from transformers.testing_utils import (
    DUMMY_DIFF_TOKENIZER_IDENTIFIER,
    DUMMY_UNKNOWN_IDENTIFIER,
    SMALL_MODEL_IDENTIFIER,
    RequestCounter,
    require_tokenizers,
    slow,
)


sys.path.append(str(Path(__file__).parent.parent.parent.parent / """utils"""))

from test_module.custom_configuration import CustomConfig  # noqa E402
from test_module.custom_tokenization import CustomTokenizer  # noqa E402


if is_tokenizers_available():
						from test_module.custom_tokenization_fast import CustomTokenizerFast




class   UpperCAmelCase_					(		unittest.TestCase			):






						'''simple docstring'''






						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			0




						@slow
						def  _lowercase     ( self				):

												"""simple docstring"""



												for model_name in (x for x in BERT_PRETRAINED_CONFIG_ARCHIVE_MAP.keys() if "japanese" not in x):
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase				)
																		self.assertIsNotNone(_lowercase				)
																		self.assertIsInstance(_lowercase   ,       (BertTokenizer, BertTokenizerFast)				)
																		self.assertGreater(len(_lowercase				)   ,       0				)

												for model_name in GPT2_PRETRAINED_CONFIG_ARCHIVE_MAP.keys():
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase				)
																		self.assertIsNotNone(_lowercase				)
																		self.assertIsInstance(_lowercase   ,       (GPTaTokenizer, GPTaTokenizerFast)				)
																		self.assertGreater(len(_lowercase				)   ,       0				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase				)
												self.assertIsInstance(_lowercase   ,       (BertTokenizer, BertTokenizerFast)				)
												self.assertEqual(tokenizer.vocab_size   ,       12				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase				)
												self.assertIsInstance(_lowercase   ,       (RobertaTokenizer, RobertaTokenizerFast)				)
												self.assertEqual(tokenizer.vocab_size   ,       20				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			AutoConfig.from_pretrained(_lowercase				)
												self.assertIsInstance(_lowercase   ,       _lowercase				)
												# Check that tokenizer_type ≠ model_type
												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase   ,       config=_lowercase				)
												self.assertIsInstance(_lowercase   ,       (BertTokenizer, BertTokenizerFast)				)
												self.assertEqual(tokenizer.vocab_size   ,       12				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												with tempfile.TemporaryDirectory() as tmp_dir:
																		shutil.copy("""./tests/fixtures/vocab.txt"""   ,       os.path.join(_lowercase   ,       """vocab.txt"""				)				)

																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase   ,       tokenizer_type="""bert"""   ,       use_fast=_lowercase				)
																		self.assertIsInstance(_lowercase   ,       _lowercase				)

												with tempfile.TemporaryDirectory() as tmp_dir:
																		shutil.copy("""./tests/fixtures/vocab.json"""   ,       os.path.join(_lowercase   ,       """vocab.json"""				)				)
																		shutil.copy("""./tests/fixtures/merges.txt"""   ,       os.path.join(_lowercase   ,       """merges.txt"""				)				)

																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase   ,       tokenizer_type="""gpt2"""   ,       use_fast=_lowercase				)
																		self.assertIsInstance(_lowercase   ,       _lowercase				)




						@require_tokenizers
						def  _lowercase     ( self				):

												"""simple docstring"""



												with tempfile.TemporaryDirectory() as tmp_dir:
																		shutil.copy("""./tests/fixtures/vocab.txt"""   ,       os.path.join(_lowercase   ,       """vocab.txt"""				)				)

																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase   ,       tokenizer_type="""bert"""				)
																		self.assertIsInstance(_lowercase   ,       _lowercase				)

												with tempfile.TemporaryDirectory() as tmp_dir:
																		shutil.copy("""./tests/fixtures/vocab.json"""   ,       os.path.join(_lowercase   ,       """vocab.json"""				)				)
																		shutil.copy("""./tests/fixtures/merges.txt"""   ,       os.path.join(_lowercase   ,       """merges.txt"""				)				)

																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase   ,       tokenizer_type="""gpt2"""				)
																		self.assertIsInstance(_lowercase   ,       _lowercase				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												with pytest.raises(_lowercase				):
																		AutoTokenizer.from_pretrained("""./"""   ,       tokenizer_type="""xxx"""				)




						@require_tokenizers
						def  _lowercase     ( self				):

												"""simple docstring"""



												for tokenizer_class in [BertTokenizer, BertTokenizerFast, AutoTokenizer]:
																		_lowerCAmelCase  						=			tokenizer_class.from_pretrained("""wietsedv/bert-base-dutch-cased"""				)
																		self.assertIsInstance(_lowercase   ,       (BertTokenizer, BertTokenizerFast)				)

																		if isinstance(_lowercase   ,       _lowercase				):
																								self.assertEqual(tokenizer.basic_tokenizer.do_lower_case   ,       _lowercase				)
																		else:
																								self.assertEqual(tokenizer.do_lower_case   ,       _lowercase				)

																		self.assertEqual(tokenizer.model_max_length   ,       512				)




						@require_tokenizers
						def  _lowercase     ( self				):

												"""simple docstring"""



												for tokenizer_class in [BertTokenizer, BertTokenizerFast, AutoTokenizer]:
																		with self.assertRaisesRegex(
																		    _lowercase   ,       """julien-c/herlolip-not-exists is not a local folder and is not a valid model identifier"""   ,       ):
																								_lowerCAmelCase  						=			tokenizer_class.from_pretrained("""julien-c/herlolip-not-exists"""				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			TOKENIZER_MAPPING.values()
												_lowerCAmelCase  						=			[]

												for slow_tok, fast_tok in tokenizers:
																		if slow_tok is not None:
																								tokenizer_names.append(slow_tok.__name__				)

																		if fast_tok is not None:
																								tokenizer_names.append(fast_tok.__name__				)

												for tokenizer_name in tokenizer_names:
																		# must find the right class
																		tokenizer_class_from_name(_lowercase				)




						@require_tokenizers
						def  _lowercase     ( self				):

												"""simple docstring"""



												self.assertIsInstance(AutoTokenizer.from_pretrained("""bert-base-cased"""   ,       use_fast=_lowercase				)   ,       _lowercase				)
												self.assertIsInstance(AutoTokenizer.from_pretrained("""bert-base-cased"""				)   ,       _lowercase				)




						@require_tokenizers
						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""distilbert-base-uncased"""   ,       do_lower_case=_lowercase				)
												_lowerCAmelCase  						=			"""Hello, world. How are you?"""
												_lowerCAmelCase  						=			tokenizer.tokenize(_lowercase				)
												self.assertEqual("""[UNK]"""   ,       tokens[0]				)

												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""microsoft/mpnet-base"""   ,       do_lower_case=_lowercase				)
												_lowerCAmelCase  						=			tokenizer.tokenize(_lowercase				)
												self.assertEqual("""[UNK]"""   ,       tokens[0]				)




						@require_tokenizers
						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""robot-test/dummy-tokenizer-fast-with-model-config"""				)
												self.assertEqual(type(_lowercase				)   ,       _lowercase				)
												self.assertEqual(tokenizer.model_max_length   ,       512				)
												self.assertEqual(tokenizer.vocab_size   ,       30_000				)
												self.assertEqual(tokenizer.unk_token   ,       """[UNK]"""				)
												self.assertEqual(tokenizer.padding_side   ,       """right"""				)
												self.assertEqual(tokenizer.truncation_side   ,       """right"""				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase				)
												self.assertIsInstance(_lowercase   ,       (BertTokenizer, BertTokenizerFast)				)
												with tempfile.TemporaryDirectory() as tmp_dir:
																		tokenizer.save_pretrained(_lowercase				)
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase				)

												self.assertIsInstance(_lowercase   ,       tokenizer.__class__				)
												self.assertEqual(tokenizera.vocab_size   ,       12				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""ctrl"""				)
												# There is no fast CTRL so this always gives us a slow tokenizer.
												self.assertIsInstance(_lowercase   ,       _lowercase				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			get_tokenizer_config("""bert-base-cased"""				)
												_lowerCAmelCase  						=			config.pop("""_commit_hash"""   ,       _lowercase				)
												# If we ever update bert-base-cased tokenizer config, this dict here will need to be updated.
												self.assertEqual(_lowercase   ,       {"""do_lower_case""": False}				)

												# This model does not have a tokenizer_config so we get back an empty dict.
												_lowerCAmelCase  						=			get_tokenizer_config(_lowercase				)
												self.assertDictEqual(_lowercase   ,       {}				)

												# A tokenizer saved with `save_pretrained` always creates a tokenizer config.
												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase				)
												with tempfile.TemporaryDirectory() as tmp_dir:
																		tokenizer.save_pretrained(_lowercase				)
																		_lowerCAmelCase  						=			get_tokenizer_config(_lowercase				)

												# Check the class of the tokenizer was properly saved (note that it always saves the slow class).
												self.assertEqual(config["""tokenizer_class"""]   ,       """BertTokenizer"""				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												try:
																		AutoConfig.register("""custom"""   ,       _lowercase				)

																		AutoTokenizer.register(_lowercase   ,       slow_tokenizer_class=_lowercase				)
																		# Trying to register something existing in the Transformers library will raise an error
																		with self.assertRaises(_lowercase				):
																								AutoTokenizer.register(_lowercase   ,       slow_tokenizer_class=_lowercase				)

																		_lowerCAmelCase  						=			CustomTokenizer.from_pretrained(_lowercase				)
																		with tempfile.TemporaryDirectory() as tmp_dir:
																								tokenizer.save_pretrained(_lowercase				)

																								_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase				)
																								self.assertIsInstance(_lowercase   ,       _lowercase				)

												finally:
																		if "custom" in CONFIG_MAPPING._extra_content:
																								del CONFIG_MAPPING._extra_content["custom"]
																		if CustomConfig in TOKENIZER_MAPPING._extra_content:
																								del TOKENIZER_MAPPING._extra_content[CustomConfig]




						@require_tokenizers
						def  _lowercase     ( self				):

												"""simple docstring"""



												try:
																		AutoConfig.register("""custom"""   ,       _lowercase				)

																		# Can register in two steps
																		AutoTokenizer.register(_lowercase   ,       slow_tokenizer_class=_lowercase				)
																		self.assertEqual(TOKENIZER_MAPPING[CustomConfig]   ,       (CustomTokenizer, None)				)
																		AutoTokenizer.register(_lowercase   ,       fast_tokenizer_class=_lowercase				)
																		self.assertEqual(TOKENIZER_MAPPING[CustomConfig]   ,       (CustomTokenizer, CustomTokenizerFast)				)

																		del TOKENIZER_MAPPING._extra_content[CustomConfig]
																		# Can register in one step
																		AutoTokenizer.register(
																		    _lowercase   ,       slow_tokenizer_class=_lowercase   ,       fast_tokenizer_class=_lowercase				)
																		self.assertEqual(TOKENIZER_MAPPING[CustomConfig]   ,       (CustomTokenizer, CustomTokenizerFast)				)

																		# Trying to register something existing in the Transformers library will raise an error
																		with self.assertRaises(_lowercase				):
																								AutoTokenizer.register(_lowercase   ,       fast_tokenizer_class=_lowercase				)

																		# We pass through a bert tokenizer fast cause there is no converter slow to fast for our new toknizer
																		# and that model does not have a tokenizer.json
																		with tempfile.TemporaryDirectory() as tmp_dir:
																								_lowerCAmelCase  						=			BertTokenizerFast.from_pretrained(_lowercase				)
																								bert_tokenizer.save_pretrained(_lowercase				)
																								_lowerCAmelCase  						=			CustomTokenizerFast.from_pretrained(_lowercase				)

																		with tempfile.TemporaryDirectory() as tmp_dir:
																								tokenizer.save_pretrained(_lowercase				)

																								_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase				)
																								self.assertIsInstance(_lowercase   ,       _lowercase				)

																								_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase   ,       use_fast=_lowercase				)
																								self.assertIsInstance(_lowercase   ,       _lowercase				)

												finally:
																		if "custom" in CONFIG_MAPPING._extra_content:
																								del CONFIG_MAPPING._extra_content["custom"]
																		if CustomConfig in TOKENIZER_MAPPING._extra_content:
																								del TOKENIZER_MAPPING._extra_content[CustomConfig]




						def  _lowercase     ( self				):

												"""simple docstring"""



												with self.assertRaises(_lowercase				):
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""hf-internal-testing/test_dynamic_tokenizer"""				)
												# If remote code is disabled, we can't load this config.
												with self.assertRaises(_lowercase				):
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(
																		    """hf-internal-testing/test_dynamic_tokenizer"""   ,       trust_remote_code=_lowercase				)

												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""hf-internal-testing/test_dynamic_tokenizer"""   ,       trust_remote_code=_lowercase				)
												self.assertTrue(tokenizer.special_attribute_present				)
												# Test tokenizer can be reloaded.
												with tempfile.TemporaryDirectory() as tmp_dir:
																		tokenizer.save_pretrained(_lowercase				)
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase   ,       trust_remote_code=_lowercase				)
												self.assertTrue(reloaded_tokenizer.special_attribute_present				)

												if is_tokenizers_available():
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizerFast"""				)
																		self.assertEqual(reloaded_tokenizer.__class__.__name__   ,       """NewTokenizerFast"""				)

																		# Test we can also load the slow version
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(
																		    """hf-internal-testing/test_dynamic_tokenizer"""   ,       trust_remote_code=_lowercase   ,       use_fast=_lowercase				)
																		self.assertTrue(tokenizer.special_attribute_present				)
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizer"""				)
																		# Test tokenizer can be reloaded.
																		with tempfile.TemporaryDirectory() as tmp_dir:
																								tokenizer.save_pretrained(_lowercase				)
																								_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase   ,       trust_remote_code=_lowercase   ,       use_fast=_lowercase				)
																		self.assertEqual(reloaded_tokenizer.__class__.__name__   ,       """NewTokenizer"""				)
																		self.assertTrue(reloaded_tokenizer.special_attribute_present				)
												else:
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizer"""				)
																		self.assertEqual(reloaded_tokenizer.__class__.__name__   ,       """NewTokenizer"""				)




						@require_tokenizers
						def  _lowercase     ( self				):

												"""simple docstring"""



												class   UpperCAmelCase_					(		_SCREAMING_SNAKE_CASE			):






																		'''simple docstring'''






																		_lowercase		:				Optional[int]									=       False






												class   UpperCAmelCase_					(		_SCREAMING_SNAKE_CASE			):






																		'''simple docstring'''






																		_lowercase		:				Dict									=       NewTokenizer
																		_lowercase		:				int									=       False

												try:
																		AutoConfig.register("""custom"""   ,       _lowercase				)
																		AutoTokenizer.register(_lowercase   ,       slow_tokenizer_class=_lowercase				)
																		AutoTokenizer.register(_lowercase   ,       fast_tokenizer_class=_lowercase				)
																		# If remote code is not set, the default is to use local
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""hf-internal-testing/test_dynamic_tokenizer"""				)
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizerFast"""				)
																		self.assertFalse(tokenizer.special_attribute_present				)
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""hf-internal-testing/test_dynamic_tokenizer"""   ,       use_fast=_lowercase				)
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizer"""				)
																		self.assertFalse(tokenizer.special_attribute_present				)

																		# If remote code is disabled, we load the local one.
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(
																		    """hf-internal-testing/test_dynamic_tokenizer"""   ,       trust_remote_code=_lowercase				)
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizerFast"""				)
																		self.assertFalse(tokenizer.special_attribute_present				)
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(
																		    """hf-internal-testing/test_dynamic_tokenizer"""   ,       trust_remote_code=_lowercase   ,       use_fast=_lowercase				)
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizer"""				)
																		self.assertFalse(tokenizer.special_attribute_present				)

																		# If remote is enabled, we load from the Hub
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(
																		    """hf-internal-testing/test_dynamic_tokenizer"""   ,       trust_remote_code=_lowercase				)
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizerFast"""				)
																		self.assertTrue(tokenizer.special_attribute_present				)
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(
																		    """hf-internal-testing/test_dynamic_tokenizer"""   ,       trust_remote_code=_lowercase   ,       use_fast=_lowercase				)
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizer"""				)
																		self.assertTrue(tokenizer.special_attribute_present				)

												finally:
																		if "custom" in CONFIG_MAPPING._extra_content:
																								del CONFIG_MAPPING._extra_content["custom"]
																		if CustomConfig in TOKENIZER_MAPPING._extra_content:
																								del TOKENIZER_MAPPING._extra_content[CustomConfig]




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(
												    """hf-internal-testing/test_dynamic_tokenizer_legacy"""   ,       trust_remote_code=_lowercase				)
												self.assertTrue(tokenizer.special_attribute_present				)
												if is_tokenizers_available():
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizerFast"""				)

																		# Test we can also load the slow version
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(
																		    """hf-internal-testing/test_dynamic_tokenizer_legacy"""   ,       trust_remote_code=_lowercase   ,       use_fast=_lowercase				)
																		self.assertTrue(tokenizer.special_attribute_present				)
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizer"""				)
												else:
																		self.assertEqual(tokenizer.__class__.__name__   ,       """NewTokenizer"""				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												with self.assertRaisesRegex(
												    _lowercase   ,       """bert-base is not a local folder and is not a valid model identifier"""				):
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""bert-base"""				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												with self.assertRaisesRegex(
												    _lowercase   ,       R"""aaaaaa is not a valid git identifier \(branch name, tag name or commit id\)"""				):
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained(_lowercase   ,       revision="""aaaaaa"""				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""hf-internal-testing/tiny-random-bert"""				)
												with RequestCounter() as counter:
																		_lowerCAmelCase  						=			AutoTokenizer.from_pretrained("""hf-internal-testing/tiny-random-bert"""				)
																		self.assertEqual(counter.get_request_count   ,       0				)
																		self.assertEqual(counter.head_request_count   ,       1				)
																		self.assertEqual(counter.other_request_count   ,       0				)


'''simple docstring'''



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




class   UpperCAmelCase_					:






						'''simple docstring'''






						def __init__( self   ,       _lowercase				):

												"""simple docstring"""



												_lowerCAmelCase  						=			str(id_				)
												_lowerCAmelCase  						=			None
												_lowerCAmelCase  						=			None
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			{}  # {vertex:distance}




						def __lt__( self   ,       _lowercase				):

												"""simple docstring"""



												return self.key < other.key




						def __repr__( self				):

												"""simple docstring"""



												return self.id




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												self.neighbors.append(_lowercase				)




						def  _lowercase     ( self   ,       _lowercase   ,       _lowercase				):

												"""simple docstring"""



												_lowerCAmelCase  						=			weight






def A				(__lowerCamelCase				:List[Any]			,     __lowerCamelCase				:Union[str, Any]			,     __lowerCamelCase				:Dict			,     __lowerCamelCase				: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]			,     __lowerCamelCase		)
						graph[b - 1].add_edge(graph[a - 1]			,     __lowerCamelCase		)


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


def A				(__lowerCamelCase				:list			,     __lowerCamelCase				:Vertex		):
						for u in graph:
												_lowerCAmelCase  						=			math.inf
												_lowerCAmelCase  						=			None
						_lowerCAmelCase  						=			0

						_lowerCAmelCase  						=			list(__lowerCamelCase		)
						hq.heapify(__lowerCamelCase		)

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

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


def A				():
						pass


if __name__ == "__main__":
						import doctest

						doctest.testmod()
