





from __future__ import annotations

from queue import Queue






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							int    ,      UpperCamelCase__:							int			):
		a ^= b
		b ^= a
		a ^= b
		return a, b






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							int    ,      UpperCamelCase__:							list[list[int]]			):
		SCREAMING_SNAKE_CASE__								=					1
		while (1 << j) < max_node:
				for i in range(1    ,      max_node + 1			):
						SCREAMING_SNAKE_CASE__								=					parent[j - 1][parent[j - 1][i]]
				j += 1
		return parent






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							int    ,      UpperCamelCase__:							int    ,      UpperCamelCase__:							list[int]    ,      UpperCamelCase__:							list[list[int]]			):
		# u must be deeper in the tree than v
		if level[u] < level[v]:
				SCREAMING_SNAKE_CASE__		,  SCREAMING_SNAKE_CASE__								=					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]:
						SCREAMING_SNAKE_CASE__								=					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]]:
						SCREAMING_SNAKE_CASE__		,  SCREAMING_SNAKE_CASE__								=					parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
		return parent[0][u]






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							list[int]    ,      UpperCamelCase__:							list[list[int]]    ,      UpperCamelCase__:							int    ,      UpperCamelCase__:							dict[int, list[int]]    ,      UpperCamelCase__:							int = 1    ,      ):
		SCREAMING_SNAKE_CASE__								=					0
		SCREAMING_SNAKE_CASE__								=					Queue(maxsize=UpperCamelCase__			)
		q.put(UpperCamelCase__			)
		while q.qsize() != 0:
				SCREAMING_SNAKE_CASE__								=					q.get()
				for v in graph[u]:
						if level[v] == -1:
								SCREAMING_SNAKE_CASE__								=					level[u] + 1
								q.put(UpperCamelCase__			)
								SCREAMING_SNAKE_CASE__								=					u
		return level, parent






def  SCREAMING_SNAKE_CASE__							(				):
		SCREAMING_SNAKE_CASE__								=					13
		# initializing with 0
		SCREAMING_SNAKE_CASE__								=					[[0 for _ in range(max_node + 10			)] for _ in range(20			)]
		# initializing with -1 which means every node is unvisited
		SCREAMING_SNAKE_CASE__								=					[-1 for _ in range(max_node + 10			)]
		SCREAMING_SNAKE_CASE__								=					{
		    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: [],
		}
		SCREAMING_SNAKE_CASE__		,  SCREAMING_SNAKE_CASE__								=					breadth_first_search(UpperCamelCase__    ,      UpperCamelCase__    ,      UpperCamelCase__    ,      UpperCamelCase__    ,      1			)
		SCREAMING_SNAKE_CASE__								=					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

import math
import random






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							int    ,      UpperCamelCase__:							int    ,      UpperCamelCase__:							int			):
		SCREAMING_SNAKE_CASE__								=					d * e - 1
		SCREAMING_SNAKE_CASE__								=					0
		SCREAMING_SNAKE_CASE__								=					0
		while p == 0:
				SCREAMING_SNAKE_CASE__								=					random.randint(2    ,      n - 1			)
				SCREAMING_SNAKE_CASE__								=					k
				while True:
						if t % 2 == 0:
								SCREAMING_SNAKE_CASE__								=					t // 2
								SCREAMING_SNAKE_CASE__								=					(g**t) % n
								SCREAMING_SNAKE_CASE__								=					math.gcd(x - 1    ,      UpperCamelCase__			)
								if x > 1 and y > 1:
										SCREAMING_SNAKE_CASE__								=					y
										SCREAMING_SNAKE_CASE__								=					n // y
										break  # find the correct factors
						else:
								break  # t is not divisible by 2, break and choose another g
		return sorted([p, q]			)


if __name__ == "__main__":
	import doctest

	doctest.testmod()