






"""simple docstring"""





import unittest

from transformers import (
    MODEL_FOR_OBJECT_DETECTION_MAPPING,
    AutoFeatureExtractor,
    AutoModelForObjectDetection,
    ObjectDetectionPipeline,
    is_vision_available,
    pipeline,
)
from transformers.testing_utils import (
    is_pipeline_test,
    nested_simplify,
    require_pytesseract,
    require_tf,
    require_timm,
    require_torch,
    require_vision,
    slow,
)

from .test_pipelines_common import ANY


if is_vision_available():
  from PIL import Image
else:
  class    __lowerCamelCase    :

     @staticmethod
     def 						SCREAMING_SNAKE_CASE__ (					*snake_case_ ,				**snake_case_      )		->       List[Any]:
         pass
@is_pipeline_test
@require_vision
@require_timm
@require_torch
class    __lowerCamelCase    (  unittest.TestCase  ):
   a      :				List[Any] 						=MODEL_FOR_OBJECT_DETECTION_MAPPING

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       Dict:
       UpperCamelCase__         =    ObjectDetectionPipeline(model=snake_case_ ,				image_processor=snake_case_      )
       return object_detector, ["./tests/fixtures/tests_samples/COCO/000000039769.png"]

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       Optional[int]:
       UpperCamelCase__         =    object_detector('./tests/fixtures/tests_samples/COCO/000000039769.png' ,				threshold=0.0      )

       self.assertGreater(len(snake_case_      ) ,				0      )
       for detected_object in outputs:
           self.assertEqual(
               snake_case_ ,				{
                   'score': ANY(snake_case_      ),
                   'label': ANY(snake_case_      ),
                   'box': {'xmin': ANY(snake_case_      ), 'ymin': ANY(snake_case_      ), 'xmax': ANY(snake_case_      ), 'ymax': ANY(snake_case_      )},
               } ,				)

       import datasets

       UpperCamelCase__         =    datasets.load_dataset('hf-internal-testing/fixtures_image_utils' ,				'image' ,				split='test'      )

       UpperCamelCase__         =    [
           Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'      ),
           'http://images.cocodataset.org/val2017/000000039769.jpg',
           # RGBA
           dataset[0]['file'],
           # LA
           dataset[1]['file'],
           # L
           dataset[2]['file'],
       ]
       UpperCamelCase__         =    object_detector(snake_case_ ,				threshold=0.0      )

       self.assertEqual(len(snake_case_      ) ,				len(snake_case_      )      )
       for outputs in batch_outputs:
           self.assertGreater(len(snake_case_      ) ,				0      )
           for detected_object in outputs:
               self.assertEqual(
                   snake_case_ ,				{
                       'score': ANY(snake_case_      ),
                       'label': ANY(snake_case_      ),
                       'box': {'xmin': ANY(snake_case_      ), 'ymin': ANY(snake_case_      ), 'xmax': ANY(snake_case_      ), 'ymax': ANY(snake_case_      )},
                   } ,				)

   @require_tf
   @unittest.skip('Object detection not implemented in TF'      )
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[Any]:
       pass

   @require_torch
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Dict:
       UpperCamelCase__         =    'hf-internal-testing/tiny-detr-mobilenetsv3'

       UpperCamelCase__         =    AutoModelForObjectDetection.from_pretrained(snake_case_      )
       UpperCamelCase__         =    AutoFeatureExtractor.from_pretrained(snake_case_      )
       UpperCamelCase__         =    ObjectDetectionPipeline(model=snake_case_ ,				feature_extractor=snake_case_      )

       UpperCamelCase__         =    object_detector('http://images.cocodataset.org/val2017/000000039769.jpg' ,				threshold=0.0      )

       self.assertEqual(
           nested_simplify(snake_case_ ,				decimals=4      ) ,				[
               {'score': 0.3_376, 'label': 'LABEL_0', 'box': {'xmin': 159, 'ymin': 120, 'xmax': 480, 'ymax': 359}},
               {'score': 0.3_376, 'label': 'LABEL_0', 'box': {'xmin': 159, 'ymin': 120, 'xmax': 480, 'ymax': 359}},
           ] ,				)

       UpperCamelCase__         =    object_detector(
           [
               'http://images.cocodataset.org/val2017/000000039769.jpg',
               'http://images.cocodataset.org/val2017/000000039769.jpg',
           ] ,				threshold=0.0 ,				)

       self.assertEqual(
           nested_simplify(snake_case_ ,				decimals=4      ) ,				[
               [
                   {'score': 0.3_376, 'label': 'LABEL_0', 'box': {'xmin': 159, 'ymin': 120, 'xmax': 480, 'ymax': 359}},
                   {'score': 0.3_376, 'label': 'LABEL_0', 'box': {'xmin': 159, 'ymin': 120, 'xmax': 480, 'ymax': 359}},
               ],
               [
                   {'score': 0.3_376, 'label': 'LABEL_0', 'box': {'xmin': 159, 'ymin': 120, 'xmax': 480, 'ymax': 359}},
                   {'score': 0.3_376, 'label': 'LABEL_0', 'box': {'xmin': 159, 'ymin': 120, 'xmax': 480, 'ymax': 359}},
               ],
           ] ,				)

   @require_torch
   @slow
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       str:
       UpperCamelCase__         =    'facebook/detr-resnet-50'

       UpperCamelCase__         =    AutoModelForObjectDetection.from_pretrained(snake_case_      )
       UpperCamelCase__         =    AutoFeatureExtractor.from_pretrained(snake_case_      )
       UpperCamelCase__         =    ObjectDetectionPipeline(model=snake_case_ ,				feature_extractor=snake_case_      )

       UpperCamelCase__         =    object_detector('http://images.cocodataset.org/val2017/000000039769.jpg'      )
       self.assertEqual(
           nested_simplify(snake_case_ ,				decimals=4      ) ,				[
               {'score': 0.9_982, 'label': 'remote', 'box': {'xmin': 40, 'ymin': 70, 'xmax': 175, 'ymax': 117}},
               {'score': 0.9_960, 'label': 'remote', 'box': {'xmin': 333, 'ymin': 72, 'xmax': 368, 'ymax': 187}},
               {'score': 0.9_955, 'label': 'couch', 'box': {'xmin': 0, 'ymin': 1, 'xmax': 639, 'ymax': 473}},
               {'score': 0.9_988, 'label': 'cat', 'box': {'xmin': 13, 'ymin': 52, 'xmax': 314, 'ymax': 470}},
               {'score': 0.9_987, 'label': 'cat', 'box': {'xmin': 345, 'ymin': 23, 'xmax': 640, 'ymax': 368}},
           ] ,				)

       UpperCamelCase__         =    object_detector(
           [
               'http://images.cocodataset.org/val2017/000000039769.jpg',
               'http://images.cocodataset.org/val2017/000000039769.jpg',
           ]      )
       self.assertEqual(
           nested_simplify(snake_case_ ,				decimals=4      ) ,				[
               [
                   {'score': 0.9_982, 'label': 'remote', 'box': {'xmin': 40, 'ymin': 70, 'xmax': 175, 'ymax': 117}},
                   {'score': 0.9_960, 'label': 'remote', 'box': {'xmin': 333, 'ymin': 72, 'xmax': 368, 'ymax': 187}},
                   {'score': 0.9_955, 'label': 'couch', 'box': {'xmin': 0, 'ymin': 1, 'xmax': 639, 'ymax': 473}},
                   {'score': 0.9_988, 'label': 'cat', 'box': {'xmin': 13, 'ymin': 52, 'xmax': 314, 'ymax': 470}},
                   {'score': 0.9_987, 'label': 'cat', 'box': {'xmin': 345, 'ymin': 23, 'xmax': 640, 'ymax': 368}},
               ],
               [
                   {'score': 0.9_982, 'label': 'remote', 'box': {'xmin': 40, 'ymin': 70, 'xmax': 175, 'ymax': 117}},
                   {'score': 0.9_960, 'label': 'remote', 'box': {'xmin': 333, 'ymin': 72, 'xmax': 368, 'ymax': 187}},
                   {'score': 0.9_955, 'label': 'couch', 'box': {'xmin': 0, 'ymin': 1, 'xmax': 639, 'ymax': 473}},
                   {'score': 0.9_988, 'label': 'cat', 'box': {'xmin': 13, 'ymin': 52, 'xmax': 314, 'ymax': 470}},
                   {'score': 0.9_987, 'label': 'cat', 'box': {'xmin': 345, 'ymin': 23, 'xmax': 640, 'ymax': 368}},
               ],
           ] ,				)

   @require_torch
   @slow
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[int]:
       UpperCamelCase__         =    'facebook/detr-resnet-50'

       UpperCamelCase__         =    pipeline('object-detection' ,				model=snake_case_      )

       UpperCamelCase__         =    object_detector('http://images.cocodataset.org/val2017/000000039769.jpg'      )
       self.assertEqual(
           nested_simplify(snake_case_ ,				decimals=4      ) ,				[
               {'score': 0.9_982, 'label': 'remote', 'box': {'xmin': 40, 'ymin': 70, 'xmax': 175, 'ymax': 117}},
               {'score': 0.9_960, 'label': 'remote', 'box': {'xmin': 333, 'ymin': 72, 'xmax': 368, 'ymax': 187}},
               {'score': 0.9_955, 'label': 'couch', 'box': {'xmin': 0, 'ymin': 1, 'xmax': 639, 'ymax': 473}},
               {'score': 0.9_988, 'label': 'cat', 'box': {'xmin': 13, 'ymin': 52, 'xmax': 314, 'ymax': 470}},
               {'score': 0.9_987, 'label': 'cat', 'box': {'xmin': 345, 'ymin': 23, 'xmax': 640, 'ymax': 368}},
           ] ,				)

       UpperCamelCase__         =    object_detector(
           [
               'http://images.cocodataset.org/val2017/000000039769.jpg',
               'http://images.cocodataset.org/val2017/000000039769.jpg',
           ]      )
       self.assertEqual(
           nested_simplify(snake_case_ ,				decimals=4      ) ,				[
               [
                   {'score': 0.9_982, 'label': 'remote', 'box': {'xmin': 40, 'ymin': 70, 'xmax': 175, 'ymax': 117}},
                   {'score': 0.9_960, 'label': 'remote', 'box': {'xmin': 333, 'ymin': 72, 'xmax': 368, 'ymax': 187}},
                   {'score': 0.9_955, 'label': 'couch', 'box': {'xmin': 0, 'ymin': 1, 'xmax': 639, 'ymax': 473}},
                   {'score': 0.9_988, 'label': 'cat', 'box': {'xmin': 13, 'ymin': 52, 'xmax': 314, 'ymax': 470}},
                   {'score': 0.9_987, 'label': 'cat', 'box': {'xmin': 345, 'ymin': 23, 'xmax': 640, 'ymax': 368}},
               ],
               [
                   {'score': 0.9_982, 'label': 'remote', 'box': {'xmin': 40, 'ymin': 70, 'xmax': 175, 'ymax': 117}},
                   {'score': 0.9_960, 'label': 'remote', 'box': {'xmin': 333, 'ymin': 72, 'xmax': 368, 'ymax': 187}},
                   {'score': 0.9_955, 'label': 'couch', 'box': {'xmin': 0, 'ymin': 1, 'xmax': 639, 'ymax': 473}},
                   {'score': 0.9_988, 'label': 'cat', 'box': {'xmin': 13, 'ymin': 52, 'xmax': 314, 'ymax': 470}},
                   {'score': 0.9_987, 'label': 'cat', 'box': {'xmin': 345, 'ymin': 23, 'xmax': 640, 'ymax': 368}},
               ],
           ] ,				)

   @require_torch
   @slow
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Tuple:
       UpperCamelCase__         =    0.9_985
       UpperCamelCase__         =    'facebook/detr-resnet-50'

       UpperCamelCase__         =    pipeline('object-detection' ,				model=snake_case_      )

       UpperCamelCase__         =    object_detector('http://images.cocodataset.org/val2017/000000039769.jpg' ,				threshold=snake_case_      )
       self.assertEqual(
           nested_simplify(snake_case_ ,				decimals=4      ) ,				[
               {'score': 0.9_988, 'label': 'cat', 'box': {'xmin': 13, 'ymin': 52, 'xmax': 314, 'ymax': 470}},
               {'score': 0.9_987, 'label': 'cat', 'box': {'xmin': 345, 'ymin': 23, 'xmax': 640, 'ymax': 368}},
           ] ,				)







   @require_torch
   @require_pytesseract
   @slow
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Dict:
       UpperCamelCase__         =    'Narsil/layoutlmv3-finetuned-funsd'
       UpperCamelCase__         =    0.9_993

       UpperCamelCase__         =    pipeline('object-detection' ,				model=snake_case_ ,				threshold=snake_case_      )

       UpperCamelCase__         =    object_detector(
           'https://huggingface.co/spaces/impira/docquery/resolve/2359223c1837a7587402bda0f2643382a6eefeab/invoice.png'      )
       self.assertEqual(
           nested_simplify(snake_case_ ,				decimals=4      ) ,				[
               {'score': 0.9_993, 'label': 'I-ANSWER', 'box': {'xmin': 294, 'ymin': 254, 'xmax': 343, 'ymax': 264}},
               {'score': 0.9_993, 'label': 'I-ANSWER', 'box': {'xmin': 294, 'ymin': 254, 'xmax': 343, 'ymax': 264}},
           ] ,				)












"""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))




