



"""simple docstring"""
import sys
from collections import defaultdict



class    SCREAMING_SNAKE_CASE__						:

   def __init__(     self		)						->   str:





    '''simple docstring'''




    UpperCAmelCase			:      Optional[int]			=			[]

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE		)						->   Dict:





    '''simple docstring'''




    return self.node_position[vertex]

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)						->   int:





    '''simple docstring'''




    UpperCAmelCase			:      Tuple			=			pos

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)						->   Dict:





    '''simple docstring'''




    if start > size // 2 - 1:
     return
    else:
     if 2 * start + 2 >= size:
      UpperCAmelCase			:      Any			=			2 * start + 1
     else:
      if heap[2 * start + 1] < heap[2 * start + 2]:
       UpperCAmelCase			:      int			=			2 * start + 1
      else:
       UpperCAmelCase			:      Tuple			=			2 * start + 2
     if heap[smallest_child] < heap[start]:
      UpperCAmelCase			,	UpperCAmelCase			:      List[Any]			=			heap[smallest_child], positions[smallest_child]
      UpperCAmelCase			,	UpperCAmelCase			:      int			=			(
          heap[start],
          positions[start],
      )
      UpperCAmelCase			,	UpperCAmelCase			:      Dict			=			temp, tempa

      UpperCAmelCase			:      List[Any]			=			self.get_position(positions[smallest_child]		)
      self.set_position(
          positions[smallest_child]   ,  self.get_position(positions[start]		)		)
      self.set_position(positions[start]   ,  _SCREAMING_SNAKE_CASE		)

      self.top_to_bottom(_SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)						->   Optional[int]:





    '''simple docstring'''




    UpperCAmelCase			:      List[Any]			=			position[index]

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

     if val < heap[parent]:
      UpperCAmelCase			:      Tuple			=			heap[parent]
      UpperCAmelCase			:      Tuple			=			position[parent]
      self.set_position(position[parent]   ,  _SCREAMING_SNAKE_CASE		)
     else:
      UpperCAmelCase			:      List[str]			=			val
      UpperCAmelCase			:      Tuple			=			temp
      self.set_position(_SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)
      break
     UpperCAmelCase			:      Any			=			parent
    else:
     UpperCAmelCase			:      str			=			val
     UpperCAmelCase			:      List[Any]			=			temp
     self.set_position(_SCREAMING_SNAKE_CASE   ,  0		)

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)						->   Dict:





    '''simple docstring'''




    UpperCAmelCase			:      Tuple			=			len(_SCREAMING_SNAKE_CASE		) // 2 - 1
    for i in range(_SCREAMING_SNAKE_CASE   ,  -1   ,  -1		):
     self.top_to_bottom(_SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  len(_SCREAMING_SNAKE_CASE		)   ,  _SCREAMING_SNAKE_CASE		)




   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)						->   int:





    '''simple docstring'''




    UpperCAmelCase			:      Dict			=			positions[0]
    UpperCAmelCase			:      List[Any]			=			sys.maxsize
    self.top_to_bottom(_SCREAMING_SNAKE_CASE   ,  0   ,  len(_SCREAMING_SNAKE_CASE		)   ,  _SCREAMING_SNAKE_CASE		)
    return temp

def    _snake_case		(		UpperCamelCase		:	Tuple		):
 UpperCAmelCase			:      List[str]			=			Heap()

 UpperCAmelCase			:      List[str]			=			[0] * len(UpperCamelCase		)
 UpperCAmelCase			:      int			=			[-1] * len(UpperCamelCase		)  # Neighboring Tree Vertex of selected vertex
 # Minimum Distance of explored vertex with neighboring vertex of partial tree
 # formed in graph
 UpperCAmelCase			:      List[str]			=			[]  # Heap of Distance of vertices from their neighboring vertex
 UpperCAmelCase			:      Union[str, Any]			=			[]

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

 UpperCAmelCase			:      Optional[int]			=			[]
 UpperCAmelCase			:      Optional[int]			=			1
 UpperCAmelCase			:      Dict			=			sys.maxsize
 for neighbor, distance in adjacency_list[0]:
  UpperCAmelCase			:      Any			=			0
  UpperCAmelCase			:      List[Any]			=			distance
 heap.heapify(UpperCamelCase    ,	UpperCamelCase		)

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


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





"""simple docstring"""
import os
import tempfile
import unittest
from pathlib import Path

from transformers import AutoConfig, is_torch_available
from transformers.testing_utils import require_torch, torch_device


if is_torch_available():
      from transformers import PyTorchBenchmark, PyTorchBenchmarkArguments



@require_torch
class    SCREAMING_SNAKE_CASE__						(      unittest.TestCase				):

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE		)						->   List[Any]:





    '''simple docstring'''




    for model_result in results.values():
     for batch_size, sequence_length in zip(model_result["""bs"""]   ,  model_result["""ss"""]		):
      UpperCAmelCase			:      List[str]			=			model_result["""result"""][batch_size][sequence_length]
      self.assertIsNotNone(_SCREAMING_SNAKE_CASE		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Optional[int]:





    '''simple docstring'''




    UpperCAmelCase			:      Union[str, Any]			=			"""sshleifer/tiny-gpt2"""
    UpperCAmelCase			:      Any			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      Tuple			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      Tuple			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_inference_result		)
    self.check_results_dict_not_empty(results.memory_inference_result		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Dict:





    '''simple docstring'''




    UpperCAmelCase			:      Any			=			"""sgugger/tiny-distilbert-classification"""
    UpperCAmelCase			:      Any			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  only_pretrain_model=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      List[str]			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      List[Any]			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_inference_result		)
    self.check_results_dict_not_empty(results.memory_inference_result		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   List[Any]:





    '''simple docstring'''




    UpperCAmelCase			:      Any			=			"""sshleifer/tiny-gpt2"""
    UpperCAmelCase			:      Optional[Any]			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  torchscript=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      Dict			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      List[str]			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_inference_result		)
    self.check_results_dict_not_empty(results.memory_inference_result		)

   @unittest.skipIf(torch_device == """cpu"""   ,  """Cant do half precision"""		)
   def 			SCREAMING_SNAKE_CASE  (     self		)						->   List[str]:





    '''simple docstring'''




    UpperCAmelCase			:      List[str]			=			"""sshleifer/tiny-gpt2"""
    UpperCAmelCase			:      Optional[int]			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  fpaa=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      Any			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      int			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_inference_result		)
    self.check_results_dict_not_empty(results.memory_inference_result		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Optional[Any]:





    '''simple docstring'''




    UpperCAmelCase			:      List[str]			=			"""sshleifer/tiny-gpt2"""
    UpperCAmelCase			:      str			=			AutoConfig.from_pretrained(_SCREAMING_SNAKE_CASE		)
    # set architectures equal to `None`
    UpperCAmelCase			:      str			=			None
    UpperCAmelCase			:      Tuple			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      Any			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE   ,  configs=[config]		)
    UpperCAmelCase			:      Dict			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_inference_result		)
    self.check_results_dict_not_empty(results.memory_inference_result		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Tuple:





    '''simple docstring'''




    UpperCAmelCase			:      Tuple			=			"""sshleifer/tiny-gpt2"""
    UpperCAmelCase			:      Union[str, Any]			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      Dict			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      Union[str, Any]			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_train_result		)
    self.check_results_dict_not_empty(results.memory_train_result		)

   @unittest.skipIf(torch_device == """cpu"""   ,  """Can't do half precision"""		)
   def 			SCREAMING_SNAKE_CASE  (     self		)						->   int:





    '''simple docstring'''




    UpperCAmelCase			:      Optional[int]			=			"""sshleifer/tiny-gpt2"""
    UpperCAmelCase			:      int			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  fpaa=_SCREAMING_SNAKE_CASE   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      str			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      Optional[Any]			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_train_result		)
    self.check_results_dict_not_empty(results.memory_train_result		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Dict:





    '''simple docstring'''




    UpperCAmelCase			:      Union[str, Any]			=			"""sshleifer/tiny-gpt2"""
    UpperCAmelCase			:      str			=			AutoConfig.from_pretrained(_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      Dict			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      Union[str, Any]			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE   ,  configs=[config]		)
    UpperCAmelCase			:      int			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_inference_result		)
    self.check_results_dict_not_empty(results.memory_inference_result		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   str:





    '''simple docstring'''




    UpperCAmelCase			:      Union[str, Any]			=			"""sshleifer/tinier_bart"""
    UpperCAmelCase			:      Tuple			=			AutoConfig.from_pretrained(_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      int			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      str			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE   ,  configs=[config]		)
    UpperCAmelCase			:      str			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_inference_result		)
    self.check_results_dict_not_empty(results.memory_inference_result		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Union[str, Any]:





    '''simple docstring'''




    UpperCAmelCase			:      Any			=			"""sshleifer/tiny-gpt2"""
    UpperCAmelCase			:      List[str]			=			AutoConfig.from_pretrained(_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      List[str]			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      Any			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE   ,  configs=[config]		)
    UpperCAmelCase			:      Optional[int]			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_train_result		)
    self.check_results_dict_not_empty(results.memory_train_result		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Union[str, Any]:





    '''simple docstring'''




    UpperCAmelCase			:      List[Any]			=			"""sshleifer/tinier_bart"""
    UpperCAmelCase			:      Optional[Any]			=			AutoConfig.from_pretrained(_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      Any			=			PyTorchBenchmarkArguments(
        models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
    UpperCAmelCase			:      int			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE   ,  configs=[config]		)
    UpperCAmelCase			:      str			=			benchmark.run()
    self.check_results_dict_not_empty(results.time_train_result		)
    self.check_results_dict_not_empty(results.memory_train_result		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Union[str, Any]:





    '''simple docstring'''




    UpperCAmelCase			:      str			=			"""sshleifer/tiny-gpt2"""
    with tempfile.TemporaryDirectory() as tmp_dir:
     UpperCAmelCase			:      Any			=			PyTorchBenchmarkArguments(
         models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  save_to_csv=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  inference_time_csv_file=os.path.join(_SCREAMING_SNAKE_CASE   ,  """inf_time.csv"""		)   ,  train_memory_csv_file=os.path.join(_SCREAMING_SNAKE_CASE   ,  """train_mem.csv"""		)   ,  inference_memory_csv_file=os.path.join(_SCREAMING_SNAKE_CASE   ,  """inf_mem.csv"""		)   ,  train_time_csv_file=os.path.join(_SCREAMING_SNAKE_CASE   ,  """train_time.csv"""		)   ,  env_info_csv_file=os.path.join(_SCREAMING_SNAKE_CASE   ,  """env.csv"""		)   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
     UpperCAmelCase			:      Union[str, Any]			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE		)
     benchmark.run()
     self.assertTrue(Path(os.path.join(_SCREAMING_SNAKE_CASE   ,  """inf_time.csv"""		)		).exists()		)
     self.assertTrue(Path(os.path.join(_SCREAMING_SNAKE_CASE   ,  """train_time.csv"""		)		).exists()		)
     self.assertTrue(Path(os.path.join(_SCREAMING_SNAKE_CASE   ,  """inf_mem.csv"""		)		).exists()		)
     self.assertTrue(Path(os.path.join(_SCREAMING_SNAKE_CASE   ,  """train_mem.csv"""		)		).exists()		)
     self.assertTrue(Path(os.path.join(_SCREAMING_SNAKE_CASE   ,  """env.csv"""		)		).exists()		)




   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Union[str, Any]:





    '''simple docstring'''




    UpperCAmelCase			:      Tuple			=			"""sshleifer/tiny-gpt2"""

    def _check_summary_is_not_empty(_SCREAMING_SNAKE_CASE		):
     self.assertTrue(hasattr(_SCREAMING_SNAKE_CASE   ,  """sequential"""		)		)
     self.assertTrue(hasattr(_SCREAMING_SNAKE_CASE   ,  """cumulative"""		)		)
     self.assertTrue(hasattr(_SCREAMING_SNAKE_CASE   ,  """current"""		)		)
     self.assertTrue(hasattr(_SCREAMING_SNAKE_CASE   ,  """total"""		)		)

    with tempfile.TemporaryDirectory() as tmp_dir:
     UpperCAmelCase			:      List[str]			=			PyTorchBenchmarkArguments(
         models=[MODEL_ID]   ,  training=_SCREAMING_SNAKE_CASE   ,  inference=_SCREAMING_SNAKE_CASE   ,  sequence_lengths=[8]   ,  batch_sizes=[1]   ,  log_filename=os.path.join(_SCREAMING_SNAKE_CASE   ,  """log.txt"""		)   ,  log_print=_SCREAMING_SNAKE_CASE   ,  trace_memory_line_by_line=_SCREAMING_SNAKE_CASE   ,  multi_process=_SCREAMING_SNAKE_CASE   ,  )
     UpperCAmelCase			:      Any			=			PyTorchBenchmark(_SCREAMING_SNAKE_CASE		)
     UpperCAmelCase			:      List[Any]			=			benchmark.run()
     _check_summary_is_not_empty(result.inference_summary		)
     _check_summary_is_not_empty(result.train_summary		)
     self.assertTrue(Path(os.path.join(_SCREAMING_SNAKE_CASE   ,  """log.txt"""		)		).exists()		)
