



from __future__ import annotations

from queue import Queue





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					a ^= b
					b ^= a
					a ^= b
					return a, b





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					lowercase						   =       1
					while (1 << j) < max_node:
										for i in range(1       ,			max_node + 1				):
															lowercase						   =       parent[j - 1][parent[j - 1][i]]
										j += 1
					return parent





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					if level[u] < level[v]:
										lowercase   ,      lowercase						   =       swap(_UpperCAmelCase       ,			_UpperCAmelCase				)
					# making depth of u same as depth of v
					for i in range(18       ,			-1       ,			-1				):
										if level[u] - (1 << i) >= level[v]:
															lowercase						   =       parent[i][u]
    # at the same depth if u==v that mean lca is found
					if u == v:
										return u
					# moving both nodes upwards till lca in found
					for i in range(18       ,			-1       ,			-1				):
										if parent[i][u] not in [0, parent[i][v]]:
															lowercase   ,      lowercase						   =       parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
					return parent[0][u]





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase = 1       ,			):
					"""simple docstring"""






					lowercase						   =       0
					lowercase						   =       Queue(maxsize=_UpperCAmelCase				)
					q.put(_UpperCAmelCase				)
					while q.qsize() != 0:
										lowercase						   =       q.get()
										for v in graph[u]:
															if level[v] == -1:
																				lowercase						   =       level[u] + 1
																				q.put(_UpperCAmelCase				)
																				lowercase						   =       u
					return level, parent





def 		__snake_case						(    ):
					"""simple docstring"""






					lowercase						   =       13
					# initializing with 0
					lowercase						   =       [[0 for _ in range(max_node + 10				)] for _ in range(20				)]
					# initializing with -1 which means every node is unvisited
					lowercase						   =       [-1 for _ in range(max_node + 10				)]
					lowercase						   =       {
					    1: [2, 3, 4],
					    2: [5],
					    3: [6, 7],
					    4: [8],
					    5: [9, 10],
					    6: [11],
					    7: [],
					    8: [12, 13],
					    9: [],
					    10: [],
					    11: [],
					    12: [],
					    13: [],
					}
					lowercase   ,      lowercase						   =       breadth_first_search(_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase       ,			1				)
					lowercase						   =       create_sparse(_UpperCAmelCase       ,			_UpperCAmelCase				)
					print('LCA of node 1 and 3 is: '       ,			lowest_common_ancestor(1       ,			3       ,			_UpperCAmelCase       ,			_UpperCAmelCase				)				)
					print('LCA of node 5 and 6 is: '       ,			lowest_common_ancestor(5       ,			6       ,			_UpperCAmelCase       ,			_UpperCAmelCase				)				)
					print('LCA of node 7 and 11 is: '       ,			lowest_common_ancestor(7       ,			11       ,			_UpperCAmelCase       ,			_UpperCAmelCase				)				)
					print('LCA of node 6 and 7 is: '       ,			lowest_common_ancestor(6       ,			7       ,			_UpperCAmelCase       ,			_UpperCAmelCase				)				)
					print('LCA of node 4 and 12 is: '       ,			lowest_common_ancestor(4       ,			12       ,			_UpperCAmelCase       ,			_UpperCAmelCase				)				)
					print('LCA of node 8 and 8 is: '       ,			lowest_common_ancestor(8       ,			8       ,			_UpperCAmelCase       ,			_UpperCAmelCase				)				)


if __name__ == "__main__":
		main()











from __future__ import annotations

# Define the Gravitational Constant G and the function
__magic_name__       =     6.6743E-11  # unit of G : m^3 * kg^-1 * s^-2





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					lowercase						   =       mass_a * mass_a

					if (force, mass_a, mass_a, distance).count(0				) != 1:
										raise ValueError('One and only one argument must be 0'				)
					if force < 0:
										raise ValueError('Gravitational force can not be negative'				)
					if distance < 0:
										raise ValueError('Distance can not be negative'				)
					if mass_a < 0 or mass_a < 0:
										raise ValueError('Mass can not be negative'				)
					if force == 0:
										lowercase						   =       GRAVITATIONAL_CONSTANT * product_of_mass / (distance**2)
										return {"force": force}
					elif mass_a == 0:
										lowercase						   =       (force) * (distance**2) / (GRAVITATIONAL_CONSTANT * mass_a)
										return {"mass_1": mass_a}
					elif mass_a == 0:
										lowercase						   =       (force) * (distance**2) / (GRAVITATIONAL_CONSTANT * mass_a)
										return {"mass_2": mass_a}
					elif distance == 0:
										lowercase						   =       (GRAVITATIONAL_CONSTANT * product_of_mass / (force)) ** 0.5
										return {"distance": distance}
					raise ValueError('One and only one argument must be 0'				)


# Run doctest
if __name__ == "__main__":
		import doctest

		doctest.testmod()






