






"""simple docstring"""





import copy
import unittest

from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
  import torch

  from transformers import (
      MODEL_FOR_MULTIPLE_CHOICE_MAPPING,
      MODEL_FOR_QUESTION_ANSWERING_MAPPING,
      MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
      MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING,
      LayoutLMvaConfig,
      LayoutLMvaForQuestionAnswering,
      LayoutLMvaForSequenceClassification,
      LayoutLMvaForTokenClassification,
      LayoutLMvaModel,
  )
  from transformers.models.layoutlmva.modeling_layoutlmva import LAYOUTLMV3_PRETRAINED_MODEL_ARCHIVE_LIST

if is_vision_available():
  from PIL import Image

  from transformers import LayoutLMvaImageProcessor
class    __lowerCamelCase    :

   def __init__(					self ,				snake_case_ ,				snake_case_=2 ,				snake_case_=3 ,				snake_case_=4 ,				snake_case_=2 ,				snake_case_=7 ,				snake_case_=True ,				snake_case_=True ,				snake_case_=True ,				snake_case_=True ,				snake_case_=99 ,				snake_case_=36 ,				snake_case_=3 ,				snake_case_=4 ,				snake_case_=37 ,				snake_case_="gelu" ,				snake_case_=0.1 ,				snake_case_=0.1 ,				snake_case_=512 ,				snake_case_=16 ,				snake_case_=2 ,				snake_case_=0.02 ,				snake_case_=6 ,				snake_case_=6 ,				snake_case_=3 ,				snake_case_=4 ,				snake_case_=None ,				snake_case_=1000 ,				)		->       Dict:
       UpperCamelCase__         =    parent
       UpperCamelCase__         =    batch_size
       UpperCamelCase__         =    num_channels
       UpperCamelCase__         =    image_size
       UpperCamelCase__         =    patch_size
       UpperCamelCase__         =    text_seq_length
       UpperCamelCase__         =    is_training
       UpperCamelCase__         =    use_input_mask
       UpperCamelCase__         =    use_token_type_ids
       UpperCamelCase__         =    use_labels
       UpperCamelCase__         =    vocab_size
       UpperCamelCase__         =    hidden_size
       UpperCamelCase__         =    num_hidden_layers
       UpperCamelCase__         =    num_attention_heads
       UpperCamelCase__         =    intermediate_size
       UpperCamelCase__         =    hidden_act
       UpperCamelCase__         =    hidden_dropout_prob
       UpperCamelCase__         =    attention_probs_dropout_prob
       UpperCamelCase__         =    max_position_embeddings
       UpperCamelCase__         =    type_vocab_size
       UpperCamelCase__         =    type_sequence_label_size
       UpperCamelCase__         =    initializer_range
       UpperCamelCase__         =    coordinate_size
       UpperCamelCase__         =    shape_size
       UpperCamelCase__         =    num_labels
       UpperCamelCase__         =    num_choices
       UpperCamelCase__         =    scope
       UpperCamelCase__         =    range_bbox

       # LayoutLMv3's sequence length equals the number of text tokens + number of patches + 1 (we add 1 for the CLS token)
       UpperCamelCase__         =    text_seq_length
       UpperCamelCase__         =    (image_size // patch_size) ** 2 + 1
       UpperCamelCase__         =    self.text_seq_length + self.image_seq_length

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       UpperCamelCase__         =    ids_tensor([self.batch_size, self.text_seq_length] ,				self.vocab_size      )

       UpperCamelCase__         =    ids_tensor([self.batch_size, self.text_seq_length, 4] ,				self.range_bbox      )
       # Ensure that bbox is legal
       for i in range(bbox.shape[0]      ):
           for j in range(bbox.shape[1]      ):
               if bbox[i, j, 3] < bbox[i, j, 1]:
                   UpperCamelCase__         =    bbox[i, j, 3]
                   UpperCamelCase__         =    bbox[i, j, 1]
                   UpperCamelCase__         =    t
               if bbox[i, j, 2] < bbox[i, j, 0]:
                   UpperCamelCase__         =    bbox[i, j, 2]
                   UpperCamelCase__         =    bbox[i, j, 0]
                   UpperCamelCase__         =    t

       UpperCamelCase__         =    floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]      )

       UpperCamelCase__         =    None
       if self.use_input_mask:
           UpperCamelCase__         =    random_attention_mask([self.batch_size, self.text_seq_length]      )

       UpperCamelCase__         =    None
       if self.use_token_type_ids:
           UpperCamelCase__         =    ids_tensor([self.batch_size, self.text_seq_length] ,				self.type_vocab_size      )

       UpperCamelCase__         =    None
       UpperCamelCase__         =    None
       if self.use_labels:
           UpperCamelCase__         =    ids_tensor([self.batch_size] ,				self.type_sequence_label_size      )
           UpperCamelCase__         =    ids_tensor([self.batch_size, self.text_seq_length] ,				self.num_labels      )

       UpperCamelCase__         =    LayoutLMvaConfig(
           vocab_size=self.vocab_size ,				hidden_size=self.hidden_size ,				num_hidden_layers=self.num_hidden_layers ,				num_attention_heads=self.num_attention_heads ,				intermediate_size=self.intermediate_size ,				hidden_act=self.hidden_act ,				hidden_dropout_prob=self.hidden_dropout_prob ,				attention_probs_dropout_prob=self.attention_probs_dropout_prob ,				max_position_embeddings=self.max_position_embeddings ,				type_vocab_size=self.type_vocab_size ,				initializer_range=self.initializer_range ,				coordinate_size=self.coordinate_size ,				shape_size=self.shape_size ,				input_size=self.image_size ,				patch_size=self.patch_size ,				)

       return config, input_ids, bbox, pixel_values, token_type_ids, input_mask, sequence_labels, token_labels

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       Union[str, Any]:
       UpperCamelCase__         =    LayoutLMvaModel(config=snake_case_      )
       model.to(snake_case_      )
       model.eval()

       # text + image
       UpperCamelCase__         =    model(snake_case_ ,				pixel_values=snake_case_      )
       UpperCamelCase__         =    model(
           snake_case_ ,				bbox=snake_case_ ,				pixel_values=snake_case_ ,				attention_mask=snake_case_ ,				token_type_ids=snake_case_      )
       UpperCamelCase__         =    model(snake_case_ ,				bbox=snake_case_ ,				pixel_values=snake_case_ ,				token_type_ids=snake_case_      )
       UpperCamelCase__         =    model(snake_case_ ,				bbox=snake_case_ ,				pixel_values=snake_case_      )

       self.parent.assertEqual(result.last_hidden_state.shape ,				(self.batch_size, self.seq_length, self.hidden_size)      )

       # text only
       UpperCamelCase__         =    model(snake_case_      )
       self.parent.assertEqual(
           result.last_hidden_state.shape ,				(self.batch_size, self.text_seq_length, self.hidden_size)      )

       # image only
       UpperCamelCase__         =    model(pixel_values=snake_case_      )
       self.parent.assertEqual(
           result.last_hidden_state.shape ,				(self.batch_size, self.image_seq_length, self.hidden_size)      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       Union[str, Any]:
       UpperCamelCase__         =    self.num_labels
       UpperCamelCase__         =    LayoutLMvaForSequenceClassification(snake_case_      )
       model.to(snake_case_      )
       model.eval()
       UpperCamelCase__         =    model(
           snake_case_ ,				bbox=snake_case_ ,				pixel_values=snake_case_ ,				attention_mask=snake_case_ ,				token_type_ids=snake_case_ ,				labels=snake_case_ ,				)
       self.parent.assertEqual(result.logits.shape ,				(self.batch_size, self.num_labels)      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       Dict:
       UpperCamelCase__         =    self.num_labels
       UpperCamelCase__         =    LayoutLMvaForTokenClassification(config=snake_case_      )
       model.to(snake_case_      )
       model.eval()
       UpperCamelCase__         =    model(
           snake_case_ ,				bbox=snake_case_ ,				pixel_values=snake_case_ ,				attention_mask=snake_case_ ,				token_type_ids=snake_case_ ,				labels=snake_case_ ,				)
       self.parent.assertEqual(result.logits.shape ,				(self.batch_size, self.text_seq_length, self.num_labels)      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       Optional[int]:
       UpperCamelCase__         =    LayoutLMvaForQuestionAnswering(config=snake_case_      )
       model.to(snake_case_      )
       model.eval()
       UpperCamelCase__         =    model(
           snake_case_ ,				bbox=snake_case_ ,				pixel_values=snake_case_ ,				attention_mask=snake_case_ ,				token_type_ids=snake_case_ ,				start_positions=snake_case_ ,				end_positions=snake_case_ ,				)
       self.parent.assertEqual(result.start_logits.shape ,				(self.batch_size, self.seq_length)      )
       self.parent.assertEqual(result.end_logits.shape ,				(self.batch_size, self.seq_length)      )







   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[int]:
       UpperCamelCase__         =    self.prepare_config_and_inputs()
       (
           (
           UpperCamelCase__
       )       ,						(
           UpperCamelCase__
       )       ,						(
           UpperCamelCase__
       )       ,						(
           UpperCamelCase__
       )       ,						(
           UpperCamelCase__
       )       ,						(
           UpperCamelCase__
       )       ,						(
           UpperCamelCase__
       )       ,						(
           UpperCamelCase__
       )       ,						
       )         =    config_and_inputs
       UpperCamelCase__         =    {
           'input_ids': input_ids,
           'bbox': bbox,
           'pixel_values': pixel_values,
           'token_type_ids': token_type_ids,
           'attention_mask': input_mask,
       }
       return config, inputs_dict







@require_torch
class    __lowerCamelCase    (  _a							,	_a							,	unittest.TestCase  ):
   a      :				List[str] 						=False
   a      :				Optional[int] 						=False
   a      :				int 						=False

   a      :				Any 						=(
       (
           LayoutLMvaModel,
           LayoutLMvaForSequenceClassification,
           LayoutLMvaForTokenClassification,
           LayoutLMvaForQuestionAnswering,
       )
       if is_torch_available()
       else ()
   )
   a      :				Any 						=(
       {"""document-question-answering""": LayoutLMvaForQuestionAnswering, """feature-extraction""": LayoutLMvaModel}
       if is_torch_available()
       else {}
   )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       Union[str, Any]:
       # `DocumentQuestionAnsweringPipeline` is expected to work with this model, but it combines the text and visual
       # embedding along the sequence dimension (dim 1), which causes an error during post-processing as `p_mask` has
       # the sequence dimension of the text embedding only.
       # (see the line `embedding_output = torch.cat([embedding_output, visual_embeddings], dim=1)`)
       return True

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Union[str, Any]:
       UpperCamelCase__         =    LayoutLMvaModelTester(self      )
       UpperCamelCase__         =    ConfigTester(self ,				config_class=snake_case_ ,				hidden_size=37      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_=False      )		->       Optional[Any]:
       UpperCamelCase__         =    copy.deepcopy(snake_case_      )
       if model_class in get_values(snake_case_      ):
           UpperCamelCase__         =    {
               k: v.unsqueeze(1      ).expand(-1 ,				self.model_tester.num_choices ,				-1      ).contiguous()
               if isinstance(snake_case_ ,				torch.Tensor      ) and v.ndim > 1
               else v
               for k, v in inputs_dict.items()
           }
       if return_labels:
           if model_class in get_values(snake_case_      ):
               UpperCamelCase__         =    torch.ones(self.model_tester.batch_size ,				dtype=torch.long ,				device=snake_case_      )
           elif model_class in get_values(snake_case_      ):
               UpperCamelCase__         =    torch.zeros(
                   self.model_tester.batch_size ,				dtype=torch.long ,				device=snake_case_      )
               UpperCamelCase__         =    torch.zeros(
                   self.model_tester.batch_size ,				dtype=torch.long ,				device=snake_case_      )
           elif model_class in [
               *get_values(snake_case_      ),
           ]:
               UpperCamelCase__         =    torch.zeros(
                   self.model_tester.batch_size ,				dtype=torch.long ,				device=snake_case_      )
           elif model_class in [
               *get_values(snake_case_      ),
           ]:
               UpperCamelCase__         =    torch.zeros(
                   (self.model_tester.batch_size, self.model_tester.text_seq_length) ,				dtype=torch.long ,				device=snake_case_ ,				)

       return inputs_dict

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[Any]:
       self.config_tester.run_common_tests()

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_model(*snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       str:
       UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs()
       for type in ["absolute", "relative_key", "relative_key_query"]:
           UpperCamelCase__         =    type
           self.model_tester.create_and_check_model(*snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_for_sequence_classification(*snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[Any]:
       UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_for_token_classification(*snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_for_question_answering(*snake_case_      )







   @slow
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Union[str, Any]:
       for model_name in LAYOUTLMV3_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
           UpperCamelCase__         =    LayoutLMvaModel.from_pretrained(snake_case_      )
           self.assertIsNotNone(snake_case_      )







def   lowerCAmelCase_( )					->	Dict:
    """simple docstring"""

    UpperCamelCase__         =    Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'					)
    return image





@require_torch
class    __lowerCamelCase    (  unittest.TestCase  ):

   @cached_property
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Union[str, Any]:
       return LayoutLMvaImageProcessor(apply_ocr=snake_case_      ) if is_vision_available() else None







   @slow
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       UpperCamelCase__         =    LayoutLMvaModel.from_pretrained('microsoft/layoutlmv3-base'      ).to(snake_case_      )

       UpperCamelCase__         =    self.default_image_processor
       UpperCamelCase__         =    prepare_img()
       UpperCamelCase__         =    image_processor(images=snake_case_ ,				return_tensors='pt'      ).pixel_values.to(snake_case_      )

       UpperCamelCase__         =    torch.tensor([[1, 2]]      )
       UpperCamelCase__         =    torch.tensor([[1, 2, 3, 4], [5, 6, 7, 8]]      ).unsqueeze(0      )

       # forward pass
       UpperCamelCase__         =    model(
           input_ids=input_ids.to(snake_case_      ) ,				bbox=bbox.to(snake_case_      ) ,				pixel_values=pixel_values.to(snake_case_      ) ,				)

       # verify the logits
       UpperCamelCase__         =    torch.Size((1, 199, 768)      )
       self.assertEqual(outputs.last_hidden_state.shape ,				snake_case_      )

       UpperCamelCase__         =    torch.tensor(
           [[-0.0_529, 0.3_618, 0.1_632], [-0.1_587, -0.1_667, -0.0_400], [-0.1_557, -0.1_671, -0.0_505]]      ).to(snake_case_      )

       self.assertTrue(torch.allclose(outputs.last_hidden_state[0, :3, :3] ,				snake_case_ ,				atol=1E-4      )      )












"""simple docstring"""





import sys
from collections import defaultdict
class    __lowerCamelCase    :

   def __init__(					self      )		->       Tuple:
       UpperCamelCase__         =    []

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       List[str]:
       return self.node_position[vertex]

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       Optional[int]:
       UpperCamelCase__         =    pos

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       List[Any]:
       if start > size // 2 - 1:
           return
       else:
           if 2 * start + 2 >= size:
               UpperCamelCase__         =    2 * start + 1
           else:
               if heap[2 * start + 1] < heap[2 * start + 2]:
                   UpperCamelCase__         =    2 * start + 1
               else:
                   UpperCamelCase__         =    2 * start + 2
           if heap[smallest_child] < heap[start]:
               UpperCamelCase__       ,						UpperCamelCase__         =    heap[smallest_child], positions[smallest_child]
               UpperCamelCase__       ,						UpperCamelCase__         =    (
                   heap[start],
                   positions[start],
               )
               UpperCamelCase__       ,						UpperCamelCase__         =    temp, tempa

               UpperCamelCase__         =    self.get_position(positions[smallest_child]      )
               self.set_position(
                   positions[smallest_child] ,				self.get_position(positions[start]      )      )
               self.set_position(positions[start] ,				snake_case_      )

               self.top_to_bottom(snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       Any:
       UpperCamelCase__         =    position[index]

       while index != 0:
           UpperCamelCase__         =    int((index - 2) / 2      ) if index % 2 == 0 else int((index - 1) / 2      )

           if val < heap[parent]:
               UpperCamelCase__         =    heap[parent]
               UpperCamelCase__         =    position[parent]
               self.set_position(position[parent] ,				snake_case_      )
           else:
               UpperCamelCase__         =    val
               UpperCamelCase__         =    temp
               self.set_position(snake_case_ ,				snake_case_      )
               break
           UpperCamelCase__         =    parent
       else:
           UpperCamelCase__         =    val
           UpperCamelCase__         =    temp
           self.set_position(snake_case_ ,				0      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       Any:
       UpperCamelCase__         =    len(snake_case_      ) // 2 - 1
       for i in range(snake_case_ ,				-1 ,				-1      ):
           self.top_to_bottom(snake_case_ ,				snake_case_ ,				len(snake_case_      ) ,				snake_case_      )







   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       List[Any]:
       UpperCamelCase__         =    positions[0]
       UpperCamelCase__         =    sys.maxsize
       self.top_to_bottom(snake_case_ ,				0 ,				len(snake_case_      ) ,				snake_case_      )
       return temp







def   lowerCAmelCase_( SCREAMING_SNAKE_CASE					)					->	Tuple:
    """simple docstring"""

    UpperCamelCase__         =    Heap()

    UpperCamelCase__         =    [0] * len(SCREAMING_SNAKE_CASE					)
    UpperCamelCase__         =    [-1] * len(SCREAMING_SNAKE_CASE					)  # Neighboring Tree Vertex of selected vertex
    # Minimum Distance of explored vertex with neighboring vertex of partial tree
    # formed in graph
    UpperCamelCase__         =    []  # Heap of Distance of vertices from their neighboring vertex
    UpperCamelCase__         =    []

    for vertex in range(len(SCREAMING_SNAKE_CASE					)					):
        distance_tv.append(sys.maxsize					)
        positions.append(SCREAMING_SNAKE_CASE					)
        heap.node_position.append(SCREAMING_SNAKE_CASE					)

    UpperCamelCase__         =    []
    UpperCamelCase__         =    1
    UpperCamelCase__         =    sys.maxsize
    for neighbor, distance in adjacency_list[0]:
        UpperCamelCase__         =    0
        UpperCamelCase__         =    distance
    heap.heapify(SCREAMING_SNAKE_CASE ,	SCREAMING_SNAKE_CASE					)

    for _ in range(1 ,	len(SCREAMING_SNAKE_CASE					)					):
        UpperCamelCase__         =    heap.delete_minimum(SCREAMING_SNAKE_CASE ,	SCREAMING_SNAKE_CASE					)
        if visited[vertex] == 0:
            tree_edges.append((nbr_tv[vertex], vertex)					)
            UpperCamelCase__         =    1
            for neighbor, distance in adjacency_list[vertex]:
                if (
                    visited[neighbor] == 0
                    and distance < distance_tv[heap.get_position(SCREAMING_SNAKE_CASE					)]
                ):
                    UpperCamelCase__         =    distance
                    heap.bottom_to_top(
                        SCREAMING_SNAKE_CASE ,	heap.get_position(SCREAMING_SNAKE_CASE					) ,	SCREAMING_SNAKE_CASE ,	SCREAMING_SNAKE_CASE					)
                    UpperCamelCase__         =    vertex
    return tree_edges


if __name__ == "__main__":  # pragma: no cover
  # < --------- Prims Algorithm --------- >
  A__					: Dict=	int(input("""Enter number of edges: """).strip())
  A__					: Dict=	defaultdict(list)
  for _ in range(edges_number):
    A__					: Dict=	[int(x) for x in input().strip().split()]
    adjacency_list[edge[0]].append([edge[1], edge[2]])
    adjacency_list[edge[1]].append([edge[0], edge[2]])
  print(prisms_algorithm(adjacency_list))




