




import sys
from collections import defaultdict
class        __snake_case  :



				def __init__(      self      :		str      )  ->    Optional[Any]:





								'''simple docstring'''




								_lowerCAmelCase    :    str										=      []



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





								'''simple docstring'''




								return self.node_position[vertex]



				def       SCREAMING_SNAKE_CASE       (      self      :		Optional[Any]		,	_UpperCAmelCase      :		List[str]		,	_UpperCAmelCase      :		Optional[Any]      )  ->    List[Any]:





								'''simple docstring'''




								_lowerCAmelCase    :    List[str]										=      pos



				def       SCREAMING_SNAKE_CASE       (      self      :		Any		,	_UpperCAmelCase      :		Union[str, Any]		,	_UpperCAmelCase      :		Optional[int]		,	_UpperCAmelCase      :		Tuple		,	_UpperCAmelCase      :		Any      )  ->    Any:





								'''simple docstring'''




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

																_lowerCAmelCase    :    Any										=      self.get_position(positions[smallest_child]      )
																self.set_position(
																    positions[smallest_child]		,	self.get_position(positions[start]      )      )
																self.set_position(positions[start]		,	_UpperCAmelCase      )

																self.top_to_bottom(_UpperCAmelCase		,	_UpperCAmelCase		,	_UpperCAmelCase		,	_UpperCAmelCase      )



				def       SCREAMING_SNAKE_CASE       (      self      :		Optional[int]		,	_UpperCAmelCase      :		Tuple		,	_UpperCAmelCase      :		Optional[Any]		,	_UpperCAmelCase      :		Tuple		,	_UpperCAmelCase      :		Union[str, Any]      )  ->    List[str]:





								'''simple docstring'''




								_lowerCAmelCase    :    Optional[Any]										=      position[index]

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

												if val < heap[parent]:
																_lowerCAmelCase    :    Any										=      heap[parent]
																_lowerCAmelCase    :    str										=      position[parent]
																self.set_position(position[parent]		,	_UpperCAmelCase      )
												else:
																_lowerCAmelCase    :    int										=      val
																_lowerCAmelCase    :    Optional[Any]										=      temp
																self.set_position(_UpperCAmelCase		,	_UpperCAmelCase      )
																break
												_lowerCAmelCase    :    int										=      parent
								else:
												_lowerCAmelCase    :    int										=      val
												_lowerCAmelCase    :    Any										=      temp
												self.set_position(_UpperCAmelCase		,	0      )



				def       SCREAMING_SNAKE_CASE       (      self      :		List[Any]		,	_UpperCAmelCase      :		Optional[Any]		,	_UpperCAmelCase      :		List[str]      )  ->    Tuple:





								'''simple docstring'''




								_lowerCAmelCase    :    Dict										=      len(_UpperCAmelCase      ) // 2 - 1
								for i in range(_UpperCAmelCase		,	-1		,	-1      ):
												self.top_to_bottom(_UpperCAmelCase		,	_UpperCAmelCase		,	len(_UpperCAmelCase      )		,	_UpperCAmelCase      )



				def       SCREAMING_SNAKE_CASE       (      self      :		int		,	_UpperCAmelCase      :		Optional[int]		,	_UpperCAmelCase      :		List[Any]      )  ->    Dict:





								'''simple docstring'''




								_lowerCAmelCase    :    Any										=      positions[0]
								_lowerCAmelCase    :    Optional[int]										=      sys.maxsize
								self.top_to_bottom(_UpperCAmelCase		,	0		,	len(_UpperCAmelCase      )		,	_UpperCAmelCase      )
								return temp






def 							_UpperCAmelCase  (UpperCamelCase_ : Optional[int]       ):
				'''simple docstring'''
				_lowerCAmelCase    :    Optional[int]										=      Heap()

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

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

				_lowerCAmelCase    :    Tuple										=      []
				_lowerCAmelCase    :    Dict										=      1
				_lowerCAmelCase    :    Optional[Any]										=      sys.maxsize
				for neighbor, distance in adjacency_list[0]:
								_lowerCAmelCase    :    str										=      0
								_lowerCAmelCase    :    int										=      distance
				heap.heapify(UpperCamelCase_      ,    UpperCamelCase_       )

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


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







def 							_UpperCAmelCase  (UpperCamelCase_ : int       ):
				'''simple docstring'''
				_lowerCAmelCase    :    int										=      n ** (1 / 3)
				return (val * val * val) == n


if __name__ == "__main__":
	print(perfect_cube(2_7))
	print(perfect_cube(4))

