


import sys
from collections import defaultdict




class A    :






      def __init__(   self		:	Union[str, Any]					)   ->		List[str]:
             """simple docstring"""




             _lowerCamelCase			:						int            =[]






      def 			lowerCamelCase			(   self		:	List[Any]     ,  lowercase_		:	int					)   ->		str:
             """simple docstring"""




             return self.node_position[vertex]






      def 			lowerCamelCase			(   self		:	str     ,  lowercase_		:	List[str]     ,  lowercase_		:	List[str]					)   ->		Union[str, Any]:
             """simple docstring"""




             _lowerCamelCase			:						Tuple            =pos






      def 			lowerCamelCase			(   self		:	str     ,  lowercase_		:	str     ,  lowercase_		:	Union[str, Any]     ,  lowercase_		:	Any     ,  lowercase_		:	str					)   ->		Union[str, Any]:
             """simple docstring"""




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

                           _lowerCamelCase			:						Optional[int]            =self.get_position(positions[smallest_child]					)
                           self.set_position(
                               positions[smallest_child]     ,  self.get_position(positions[start]					)					)
                           self.set_position(positions[start]     ,  lowercase_					)

                           self.top_to_bottom(lowercase_     ,  lowercase_     ,  lowercase_     ,  lowercase_					)






      def 			lowerCamelCase			(   self		:	List[str]     ,  lowercase_		:	Dict     ,  lowercase_		:	List[Any]     ,  lowercase_		:	int     ,  lowercase_		:	int					)   ->		Optional[int]:
             """simple docstring"""




             _lowerCamelCase			:						List[Any]            =position[index]

             while index != 0:
                    _lowerCamelCase			:						List[Any]            =int((index - 2) / 2					) if index % 2 == 0 else int((index - 1) / 2					)

                    if val < heap[parent]:
                           _lowerCamelCase			:						Optional[int]            =heap[parent]
                           _lowerCamelCase			:						Tuple            =position[parent]
                           self.set_position(position[parent]     ,  lowercase_					)
                    else:
                           _lowerCamelCase			:						int            =val
                           _lowerCamelCase			:						Tuple            =temp
                           self.set_position(lowercase_     ,  lowercase_					)
                           break
                    _lowerCamelCase			:						str            =parent
             else:
                    _lowerCamelCase			:						List[Any]            =val
                    _lowerCamelCase			:						Union[str, Any]            =temp
                    self.set_position(lowercase_     ,  0					)






      def 			lowerCamelCase			(   self		:	List[Any]     ,  lowercase_		:	List[str]     ,  lowercase_		:	str					)   ->		List[Any]:
             """simple docstring"""




             _lowerCamelCase			:						str            =len(lowercase_					) // 2 - 1
             for i in range(lowercase_     ,  -1     ,  -1					):
                    self.top_to_bottom(lowercase_     ,  lowercase_     ,  len(lowercase_					)     ,  lowercase_					)






      def 			lowerCamelCase			(   self		:	List[Any]     ,  lowercase_		:	Optional[Any]     ,  lowercase_		:	Tuple					)   ->		str:
             """simple docstring"""




             _lowerCamelCase			:						Optional[Any]            =positions[0]
             _lowerCamelCase			:						Optional[Any]            =sys.maxsize
             self.top_to_bottom(lowercase_     ,  0     ,  len(lowercase_					)     ,  lowercase_					)
             return temp




def       a_ (       SCREAMING_SNAKE_CASE__   : Any	):
       '''simple docstring'''





       _lowerCamelCase			:						Union[str, Any]            =Heap()

       _lowerCamelCase			:						List[str]            =[0] * len(SCREAMING_SNAKE_CASE__	)
       _lowerCamelCase			:						Tuple            =[-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
       _lowerCamelCase			:						Any            =[]  # Heap of Distance of vertices from their neighboring vertex
       _lowerCamelCase			:						Union[str, Any]            =[]

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

       _lowerCamelCase			:						List[str]            =[]
       _lowerCamelCase			:						Optional[int]            =1
       _lowerCamelCase			:						int            =sys.maxsize
       for neighbor, distance in adjacency_list[0]:
              _lowerCamelCase			:						List[Any]            =0
              _lowerCamelCase			:						int            =distance
       heap.heapify(SCREAMING_SNAKE_CASE__						,     SCREAMING_SNAKE_CASE__	)

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


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






from timeit import timeit

lowerCamelCase		   =			{
    'MALAYALAM': True,
    'String': False,
    'rotor': True,
    'level': True,
    'A': True,
    'BB': True,
    'ABC': False,
    'amanaplanacanalpanama': True,  # "a man a plan a canal panama"
}
# Ensure our test data is valid
assert all((key == key[::-1]) is value for key, value in test_data.items())




def       a_ (       SCREAMING_SNAKE_CASE__   : str	):
       '''simple docstring'''





       _lowerCamelCase			:						Optional[int]            =0
       _lowerCamelCase			:						Union[str, Any]            =len(SCREAMING_SNAKE_CASE__	) - 1
       while start_i < end_i:
              if s[start_i] == s[end_i]:
                     start_i += 1
                     end_i -= 1
              else:
                     return False
       return True




def       a_ (       SCREAMING_SNAKE_CASE__   : str	):
       '''simple docstring'''





       _lowerCamelCase			:						List[str]            =len(SCREAMING_SNAKE_CASE__	) // 2
       _lowerCamelCase			:						Optional[Any]            =len(SCREAMING_SNAKE_CASE__	)

       # We need to traverse till half of the length of string
       # as we can get access of the i'th last element from
       # i'th index.
       # eg: [0,1,2,3,4,5] => 4th index can be accessed
       # with the help of 1st index (i==n-i-1)
       # where n is length of string
       return all(s[i] == s[n - i - 1] for i in range(SCREAMING_SNAKE_CASE__	)	)




def       a_ (       SCREAMING_SNAKE_CASE__   : str	):
       '''simple docstring'''





       if len(SCREAMING_SNAKE_CASE__	) <= 2:
              return True
       if s[0] == s[len(SCREAMING_SNAKE_CASE__	) - 1]:
              return is_palindrome_recursive(s[1:-1]	)
       else:
              return False




def       a_ (       SCREAMING_SNAKE_CASE__   : str	):
       '''simple docstring'''





       return s == s[::-1]




def       a_ (       SCREAMING_SNAKE_CASE__   : str	):
       '''simple docstring'''





       _lowerCamelCase			:						Optional[int]            =F'''all({name}(key) is value for key, value in test_data.items())'''
       _lowerCamelCase			:						List[Any]            =F'''from __main__ import test_data, {name}'''
       _lowerCamelCase			:						Any            =500_000
       _lowerCamelCase			:						Dict            =timeit(stmt=SCREAMING_SNAKE_CASE__						,     setup=SCREAMING_SNAKE_CASE__						,     number=SCREAMING_SNAKE_CASE__	)
       print(F'''{name:<35} finished {number:,} runs in {result:.5f} seconds'''	)


if __name__ == "__main__":
 for key, value in test_data.items():
  assert is_palindrome(key) is is_palindrome_recursive(key)
  assert is_palindrome(key) is is_palindrome_slice(key)
  print(F"""{key:21} {value}""")
 print('a man a plan a canal panama')

 # finished 500,000 runs in 0.46793 seconds
 benchmark_function('is_palindrome_slice')
 # finished 500,000 runs in 0.85234 seconds
 benchmark_function('is_palindrome')
 # finished 500,000 runs in 1.32028 seconds
 benchmark_function('is_palindrome_recursive')
 # finished 500,000 runs in 2.08679 seconds
 benchmark_function('is_palindrome_traversal')


