






'''simple docstring'''





import heapq as hq
import math
from collections.abc import Iterator
class  lowerCAmelCase_       :




							def __init__(   self     :   str ,							SCREAMING_SNAKE_CASE_     :   List[str]	):
											lowerCAmelCase__      			=						str(id_	)
											lowerCAmelCase__      			=						None
											lowerCAmelCase__      			=						None
											lowerCAmelCase__      			=						[]
											lowerCAmelCase__      			=						{}  # {vertex:distance}




							def __lt__(   self     :   int ,							SCREAMING_SNAKE_CASE_     :   List[Any]	):
											return self.key < other.key




							def __repr__(   self     :   Optional[Any]	):
											return self.id




							def 						__snake_case					(   self     :   Tuple ,							SCREAMING_SNAKE_CASE_     :   Optional[int]	):
											self.neighbors.append(SCREAMING_SNAKE_CASE_	)




							def 						__snake_case					(   self     :   Tuple ,							SCREAMING_SNAKE_CASE_     :   str ,							SCREAMING_SNAKE_CASE_     :   List[Any]	):
											lowerCAmelCase__      			=						weight





def 	lowerCAmelCase_		(lowercase__						:       Any     ,					lowercase__						:       Optional[int]     ,					lowercase__						:       Any     ,					lowercase__						:       List[str]       )		->    List[Any]:


				'''simple docstring'''




				graph[a - 1].add_neighbor(graph[b - 1]       )
				graph[b - 1].add_neighbor(graph[a - 1]       )
				# add the edges:
				graph[a - 1].add_edge(graph[b - 1]     ,					lowercase__       )
				graph[b - 1].add_edge(graph[a - 1]     ,					lowercase__       )





def 	lowerCAmelCase_		(lowercase__						:       list     ,					lowercase__						:       Vertex       )		->    list:


				'''simple docstring'''




				lowerCAmelCase__      			=						[]
				for u in graph:
								lowerCAmelCase__      			=						math.inf
								lowerCAmelCase__      			=						None
				lowerCAmelCase__      			=						0
				lowerCAmelCase__      			=						graph[:]
				while q:
								lowerCAmelCase__      			=						min(lowercase__       )
								q.remove(lowercase__       )
								for v in u.neighbors:
												if (v in q) and (u.edges[v.id] < v.key):
																lowerCAmelCase__      			=						u
																lowerCAmelCase__      			=						u.edges[v.id]
				for i in range(1     ,					len(lowercase__       )       ):
								a.append((int(graph[i].id       ) + 1, int(graph[i].pi.id       ) + 1)       )
				return a





def 	lowerCAmelCase_		(lowercase__						:       list     ,					lowercase__						:       Vertex       )		->    Iterator[tuple]:


				'''simple docstring'''




				for u in graph:
								lowerCAmelCase__      			=						math.inf
								lowerCAmelCase__      			=						None
				lowerCAmelCase__      			=						0

				lowerCAmelCase__      			=						list(lowercase__       )
				hq.heapify(lowercase__       )

				while h:
								lowerCAmelCase__      			=						hq.heappop(lowercase__       )
								for v in u.neighbors:
												if (v in h) and (u.edges[v.id] < v.key):
																lowerCAmelCase__      			=						u
																lowerCAmelCase__      			=						u.edges[v.id]
																hq.heapify(lowercase__       )

				for i in range(1     ,					len(lowercase__       )       ):
								yield (int(graph[i].id       ) + 1, int(graph[i].pi.id       ) + 1)





def 	lowerCAmelCase_		()		->    None:


				'''simple docstring'''










if __name__ == "__main__":
			import doctest

			doctest.testmod()













from math import isclose, sqrt





def 	lowerCAmelCase_		(lowercase__						:       float     ,					lowercase__						:       float     ,					lowercase__						:       float       )		->    tuple[float, float, float]:


				'''simple docstring'''




				lowerCAmelCase__      			=						point_y / 4 / point_x
				lowerCAmelCase__      			=						2 * normal_gradient / (1 + normal_gradient * normal_gradient)
				lowerCAmelCase__      			=						(1 - normal_gradient * normal_gradient) / (
				    1 + normal_gradient * normal_gradient
				)
				lowerCAmelCase__      			=						(sa - ca * incoming_gradient) / (ca + sa * incoming_gradient)

				# to find the next point, solve the simultaeneous equations:
				# y^2 + 4x^2 = 100
				# y - b = m * (x - a)
				# ==> A x^2 + B x + C = 0
				lowerCAmelCase__      			=						outgoing_gradient**2 + 4
				lowerCAmelCase__      			=						2 * outgoing_gradient * (point_y - outgoing_gradient * point_x)
				lowerCAmelCase__      			=						(point_y - outgoing_gradient * point_x) ** 2 - 1_00

				lowerCAmelCase__      			=						(
				    -linear_term - sqrt(linear_term**2 - 4 * quadratic_term * constant_term       )
				) / (2 * quadratic_term)
				lowerCAmelCase__      			=						(
				    -linear_term + sqrt(linear_term**2 - 4 * quadratic_term * constant_term       )
				) / (2 * quadratic_term)

				# two solutions, one of which is our input point
				lowerCAmelCase__      			=						x_minus if isclose(lowercase__     ,					lowercase__       ) else x_plus
				lowerCAmelCase__      			=						point_y + outgoing_gradient * (next_x - point_x)

				return next_x, next_y, outgoing_gradient





def 	lowerCAmelCase_		(lowercase__						:       float = 1.4     ,					lowercase__						:       float = -9.6       )		->    int:


				'''simple docstring'''




				lowerCAmelCase__      			=						0
				lowerCAmelCase__      			=						first_x_coord
				lowerCAmelCase__      			=						first_y_coord
				lowerCAmelCase__      			=						(10.1 - point_y) / (0.0 - point_x)

				while not (-0.01 <= point_x <= 0.01 and point_y > 0):
								lowerCAmelCase__			,		lowerCAmelCase__			,		lowerCAmelCase__      			=						next_point(lowercase__     ,					lowercase__     ,					lowercase__       )
								num_reflections += 1

				return num_reflections


if __name__ == "__main__":
			print(F'''{solution() = }''')





