


"""simple docstring"""






from __future__ import annotations

from queue import Queue


def __lowercase  (   lowerCamelCase_	:   Optional[Any]    ,       lowerCamelCase_	:   Tuple	):
				a ^= b
				b ^= a
				a ^= b
				return a, b


def __lowercase  (   lowerCamelCase_	:   Union[str, Any]    ,       lowerCamelCase_	:   List[str]	):
				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 __lowercase  (   lowerCamelCase_	:   Optional[int]    ,       lowerCamelCase_	:   Union[str, Any]    ,       lowerCamelCase_	:   List[str]    ,       lowerCamelCase_	:   Optional[Any]	):
				# 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 __lowercase  (   lowerCamelCase_	:   Optional[int]    ,       lowerCamelCase_	:   List[Any]    ,       lowerCamelCase_	:   str    ,       lowerCamelCase_	:   str    ,       lowerCamelCase_	:   List[str] = 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 __lowercase  (   ):
				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 itertools import compress, repeat
from math import ceil, sqrt




def 			lowerCAmelCase_			(				UpperCamelCase_	)  ->		list[int]:

       if num <= 2:
              return []
       if num == 3:
              return [2]

       # Odd sieve for numbers in range [3, num - 1]
       UpperCamelCase_ 							=	bytearray(b"\x01"	) * ((num >> 1) - 1)

       for i in range(3       ,		int(sqrt(UpperCamelCase_	)	) + 1       ,		2	):
              if sieve[(i >> 1) - 1]:
                     UpperCamelCase_ 							=	i**2
                     UpperCamelCase_ 							=	repeat(
                         0       ,		ceil((num - i_squared) / (i << 1)	)	)

       return [2] + list(compress(range(3       ,		UpperCamelCase_       ,		2	)       ,		UpperCamelCase_	)	)


if __name__ == "__main__":
     import doctest

     doctest.testmod()

