





'''simple docstring'''

import json
import os
import shutil
import tempfile
import unittest

import numpy as np
import pytest

from transformers import CLIPTokenizer, CLIPTokenizerFast
from transformers.models.clip.tokenization_clip import VOCAB_FILES_NAMES
from transformers.testing_utils import require_vision
from transformers.utils import IMAGE_PROCESSOR_NAME, is_vision_available


if is_vision_available():
    from PIL import Image

    from transformers import OwlViTImageProcessor, OwlViTProcessor







@require_vision
class __a (   unittest.TestCase			):





   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       tempfile.mkdtemp()

      # fmt: off
      __SCREAMING_SNAKE_CASE      							=       ["""""", """l""", """o""", """w""", """e""", """r""", """s""", """t""", """i""", """d""", """n""", """lo""", """l</w>""", """w</w>""", """r</w>""", """t</w>""", """low</w>""", """er</w>""", """lowest</w>""", """newer</w>""", """wider""", """<unk>""", """<|startoftext|>""", """<|endoftext|>"""]
      # fmt: on
      __SCREAMING_SNAKE_CASE      							=       dict(zip(lowerCamelCase				,range(len(lowerCamelCase    )    )    )    )
      __SCREAMING_SNAKE_CASE      							=       ["""#version: 0.2""", """l o""", """lo w</w>""", """e r</w>""", """"""]
      __SCREAMING_SNAKE_CASE      							=       {"""unk_token""": """<unk>"""}

      __SCREAMING_SNAKE_CASE      							=       os.path.join(self.tmpdirname				,VOCAB_FILES_NAMES["""vocab_file"""]    )
      __SCREAMING_SNAKE_CASE      							=       os.path.join(self.tmpdirname				,VOCAB_FILES_NAMES["""merges_file"""]    )
      with open(self.vocab_file				,"""w"""				,encoding="""utf-8"""    ) as fp:
         fp.write(json.dumps(lowerCamelCase    ) + """\n"""    )
      with open(self.merges_file				,"""w"""				,encoding="""utf-8"""    ) as fp:
         fp.write("""\n""".join(lowerCamelCase    )    )

      __SCREAMING_SNAKE_CASE      							=       {
          """do_resize""": True,
          """size""": 20,
          """do_center_crop""": True,
          """crop_size""": 18,
          """do_normalize""": True,
          """image_mean""": [0.48_145_466, 0.4_578_275, 0.40_821_073],
          """image_std""": [0.26_862_954, 0.26_130_258, 0.27_577_711],
      }
      __SCREAMING_SNAKE_CASE      							=       os.path.join(self.tmpdirname				,lowerCamelCase    )
      with open(self.image_processor_file				,"""w"""				,encoding="""utf-8"""    ) as fp:
         json.dump(lowerCamelCase				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			int				,**lowerCamelCase				:			List[str]    ):

      '''simple docstring'''

      return CLIPTokenizer.from_pretrained(self.tmpdirname				,pad_token="""!"""				,**lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			int				,**lowerCamelCase				:			List[str]    ):

      '''simple docstring'''

      return CLIPTokenizerFast.from_pretrained(self.tmpdirname				,pad_token="""!"""				,**lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			List[str]				,**lowerCamelCase				:			Tuple    ):

      '''simple docstring'''

      return OwlViTImageProcessor.from_pretrained(self.tmpdirname				,**lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      shutil.rmtree(self.tmpdirname    )





   def      UpperCAmelCase__     (					self				:			int    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       [np.random.randint(255				,size=(3, 30, 400)				,dtype=np.uinta    )]

      __SCREAMING_SNAKE_CASE      							=       [Image.fromarray(np.moveaxis(lowerCamelCase				,0				,-1    )    ) for x in image_inputs]

      return image_inputs





   def      UpperCAmelCase__     (					self				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.get_tokenizer()
      __SCREAMING_SNAKE_CASE      							=       self.get_rust_tokenizer()
      __SCREAMING_SNAKE_CASE      							=       self.get_image_processor()

      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor(tokenizer=lowerCamelCase				,image_processor=lowerCamelCase    )
      processor_slow.save_pretrained(self.tmpdirname    )
      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor.from_pretrained(self.tmpdirname				,use_fast=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor(tokenizer=lowerCamelCase				,image_processor=lowerCamelCase    )
      processor_fast.save_pretrained(self.tmpdirname    )
      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor.from_pretrained(self.tmpdirname    )

      self.assertEqual(processor_slow.tokenizer.get_vocab()				,tokenizer_slow.get_vocab()    )
      self.assertEqual(processor_fast.tokenizer.get_vocab()				,tokenizer_fast.get_vocab()    )
      self.assertEqual(tokenizer_slow.get_vocab()				,tokenizer_fast.get_vocab()    )
      self.assertIsInstance(processor_slow.tokenizer				,lowerCamelCase    )
      self.assertIsInstance(processor_fast.tokenizer				,lowerCamelCase    )

      self.assertEqual(processor_slow.image_processor.to_json_string()				,image_processor.to_json_string()    )
      self.assertEqual(processor_fast.image_processor.to_json_string()				,image_processor.to_json_string()    )
      self.assertIsInstance(processor_slow.image_processor				,lowerCamelCase    )
      self.assertIsInstance(processor_fast.image_processor				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor(tokenizer=self.get_tokenizer()				,image_processor=self.get_image_processor()    )
      processor.save_pretrained(self.tmpdirname    )

      __SCREAMING_SNAKE_CASE      							=       self.get_tokenizer(bos_token="""(BOS)"""				,eos_token="""(EOS)"""    )
      __SCREAMING_SNAKE_CASE      							=       self.get_image_processor(do_normalize=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor.from_pretrained(
          self.tmpdirname				,bos_token="""(BOS)"""				,eos_token="""(EOS)"""				,do_normalize=lowerCamelCase    )

      self.assertEqual(processor.tokenizer.get_vocab()				,tokenizer_add_kwargs.get_vocab()    )
      self.assertIsInstance(processor.tokenizer				,lowerCamelCase    )

      self.assertEqual(processor.image_processor.to_json_string()				,image_processor_add_kwargs.to_json_string()    )
      self.assertIsInstance(processor.image_processor				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.get_image_processor()
      __SCREAMING_SNAKE_CASE      							=       self.get_tokenizer()

      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor(tokenizer=lowerCamelCase				,image_processor=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       self.prepare_image_inputs()

      __SCREAMING_SNAKE_CASE      							=       image_processor(lowerCamelCase				,return_tensors="""np"""    )
      __SCREAMING_SNAKE_CASE      							=       processor(images=lowerCamelCase				,return_tensors="""np"""    )

      for key in input_image_proc.keys():
         self.assertAlmostEqual(input_image_proc[key].sum()				,input_processor[key].sum()				,delta=1E-2    )





   def      UpperCAmelCase__     (					self				:			str    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.get_image_processor()
      __SCREAMING_SNAKE_CASE      							=       self.get_tokenizer()

      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor(tokenizer=lowerCamelCase				,image_processor=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       """lower newer"""

      __SCREAMING_SNAKE_CASE      							=       processor(text=lowerCamelCase				,return_tensors="""np"""    )

      __SCREAMING_SNAKE_CASE      							=       tokenizer(lowerCamelCase				,return_tensors="""np"""    )

      for key in encoded_tok.keys():
         self.assertListEqual(encoded_tok[key][0].tolist()				,encoded_processor[key][0].tolist()    )





   def      UpperCAmelCase__     (					self				:			Optional[int]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.get_image_processor()
      __SCREAMING_SNAKE_CASE      							=       self.get_tokenizer()

      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor(tokenizer=lowerCamelCase				,image_processor=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       """lower newer"""
      __SCREAMING_SNAKE_CASE      							=       self.prepare_image_inputs()

      __SCREAMING_SNAKE_CASE      							=       processor(text=lowerCamelCase				,images=lowerCamelCase    )

      self.assertListEqual(list(inputs.keys()    )				,["""input_ids""", """attention_mask""", """pixel_values"""]    )

      # test if it raises when no input is passed
      with pytest.raises(lowerCamelCase    ):
         processor()





   def      UpperCAmelCase__     (					self				:			Union[str, Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       """google/owlvit-base-patch32"""
      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor.from_pretrained(lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       ["""cat""", """nasa badge"""]
      __SCREAMING_SNAKE_CASE      							=       processor(text=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       16
      self.assertListEqual(list(inputs.keys()    )				,["""input_ids""", """attention_mask"""]    )
      self.assertEqual(inputs["""input_ids"""].shape				,(2, seq_length)    )

      # test if it raises when no input is passed
      with pytest.raises(lowerCamelCase    ):
         processor()





   def      UpperCAmelCase__     (					self				:			Optional[int]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       """google/owlvit-base-patch32"""
      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor.from_pretrained(lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       [["""cat""", """nasa badge"""], ["""person"""]]
      __SCREAMING_SNAKE_CASE      							=       processor(text=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       16
      __SCREAMING_SNAKE_CASE      							=       len(lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       max([len(lowerCamelCase    ) for texts in input_texts]    )

      self.assertListEqual(list(inputs.keys()    )				,["""input_ids""", """attention_mask"""]    )
      self.assertEqual(inputs["""input_ids"""].shape				,(batch_size * num_max_text_queries, seq_length)    )

      # test if it raises when no input is passed
      with pytest.raises(lowerCamelCase    ):
         processor()





   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       """google/owlvit-base-patch32"""
      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor.from_pretrained(lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       ["""cat""", """nasa badge"""]
      __SCREAMING_SNAKE_CASE      							=       processor(text=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       16
      __SCREAMING_SNAKE_CASE      							=       inputs["""input_ids"""]
      __SCREAMING_SNAKE_CASE      							=       [
          [4_9406, 2368, 4_9407, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
          [4_9406, 6841, 1_1301, 4_9407, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
      ]

      self.assertListEqual(list(inputs.keys()    )				,["""input_ids""", """attention_mask"""]    )
      self.assertEqual(inputs["""input_ids"""].shape				,(2, seq_length)    )
      self.assertListEqual(list(input_ids[0]    )				,predicted_ids[0]    )
      self.assertListEqual(list(input_ids[1]    )				,predicted_ids[1]    )





   def      UpperCAmelCase__     (					self				:			Optional[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.get_image_processor()
      __SCREAMING_SNAKE_CASE      							=       self.get_tokenizer()

      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor(tokenizer=lowerCamelCase				,image_processor=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       self.prepare_image_inputs()
      __SCREAMING_SNAKE_CASE      							=       self.prepare_image_inputs()

      __SCREAMING_SNAKE_CASE      							=       processor(images=lowerCamelCase				,query_images=lowerCamelCase    )

      self.assertListEqual(list(inputs.keys()    )				,["""query_pixel_values""", """pixel_values"""]    )

      # test if it raises when no input is passed
      with pytest.raises(lowerCamelCase    ):
         processor()





   def      UpperCAmelCase__     (					self				:			Optional[int]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.get_image_processor()
      __SCREAMING_SNAKE_CASE      							=       self.get_tokenizer()

      __SCREAMING_SNAKE_CASE      							=       OwlViTProcessor(tokenizer=lowerCamelCase				,image_processor=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       [[1, 4, 5, 8, 1, 0, 8], [3, 4, 3, 1, 1, 8, 9]]

      __SCREAMING_SNAKE_CASE      							=       processor.batch_decode(lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       tokenizer.batch_decode(lowerCamelCase    )

      self.assertListEqual(lowerCamelCase				,lowerCamelCase    )












'''simple docstring'''

import sys
from collections import defaultdict







class __a :





   def __init__(					self				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       []





   def      UpperCAmelCase__     (					self				:			List[Any]				,lowerCamelCase				:			List[Any]    ):

      '''simple docstring'''

      return self.node_position[vertex]





   def      UpperCAmelCase__     (					self				:			List[Any]				,lowerCamelCase				:			str				,lowerCamelCase				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       pos





   def      UpperCAmelCase__     (					self				:			List[Any]				,lowerCamelCase				:			Optional[int]				,lowerCamelCase				:			Union[str, Any]				,lowerCamelCase				:			List[Any]				,lowerCamelCase				:			Any    ):

      '''simple docstring'''

      if start > size // 2 - 1:
         return
      else:
         if 2 * start + 2 >= size:
            __SCREAMING_SNAKE_CASE      							=       2 * start + 1
         else:
            if heap[2 * start + 1] < heap[2 * start + 2]:
               __SCREAMING_SNAKE_CASE      							=       2 * start + 1
            else:
               __SCREAMING_SNAKE_CASE      							=       2 * start + 2
         if heap[smallest_child] < heap[start]:
            __SCREAMING_SNAKE_CASE							,     __SCREAMING_SNAKE_CASE      							=       heap[smallest_child], positions[smallest_child]
            __SCREAMING_SNAKE_CASE							,     __SCREAMING_SNAKE_CASE      							=       (
                heap[start],
                positions[start],
            )
            __SCREAMING_SNAKE_CASE							,     __SCREAMING_SNAKE_CASE      							=       temp, tempa

            __SCREAMING_SNAKE_CASE      							=       self.get_position(positions[smallest_child]    )
            self.set_position(
                positions[smallest_child]				,self.get_position(positions[start]    )    )
            self.set_position(positions[start]				,lowerCamelCase    )

            self.top_to_bottom(lowerCamelCase				,lowerCamelCase				,lowerCamelCase				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			Any				,lowerCamelCase				:			int				,lowerCamelCase				:			List[str]				,lowerCamelCase				:			Optional[Any]				,lowerCamelCase				:			Tuple    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       position[index]

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

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





   def      UpperCAmelCase__     (					self				:			Tuple				,lowerCamelCase				:			List[Any]				,lowerCamelCase				:			List[str]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       len(lowerCamelCase    ) // 2 - 1
      for i in range(lowerCamelCase				,-1				,-1    ):
         self.top_to_bottom(lowerCamelCase				,lowerCamelCase				,len(lowerCamelCase    )				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			int				,lowerCamelCase				:			Optional[int]				,lowerCamelCase				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       positions[0]
      __SCREAMING_SNAKE_CASE      							=       sys.maxsize
      self.top_to_bottom(lowerCamelCase				,0				,len(lowerCamelCase    )				,lowerCamelCase    )
      return temp





def 						__magic_name__       (							__UpperCAmelCase      )						->					Optional[Any]:

   '''simple docstring'''







   __SCREAMING_SNAKE_CASE      							=       Heap()

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

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

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

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


if __name__ == "__main__":  # pragma: no cover
    # < --------- Prims Algorithm --------- >
    a        =						int(input("Enter number of edges: ").strip())
    a        =						defaultdict(list)
    for _ in range(edges_number):
        a        =						[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))





