






"""simple docstring"""



from __future__ import annotations

from queue import Queue




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->tuple[int, int]:
 a ^= b
 b ^= a
 a ^= b
 return a, b




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->list[list[int]]:
 UpperCAmelCase__ 						=				1
 while (1 << j) < max_node:
  for i in range(1       ,	max_node + 1			):
   UpperCAmelCase__ 						=				parent[j - 1][parent[j - 1][i]]
  j += 1
 return parent




def       snake_case__		(   _SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)    ->int:
 # u must be deeper in the tree than v
 if level[u] < level[v]:
  UpperCAmelCase__ 						=				swap(_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)
 # making depth of u same as depth of v
 for i in range(1_8       ,	-1       ,	-1			):
  if level[u] - (1 << i) >= level[v]:
   UpperCAmelCase__ 						=				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(1_8       ,	-1       ,	-1			):
  if parent[i][u] not in [0, parent[i][v]]:
   UpperCAmelCase__ 						=				parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
 return parent[0][u]




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




def       snake_case__		(   )    ->None:
 UpperCAmelCase__ 						=				1_3
 # initializing with 0
 UpperCAmelCase__ 						=				[[0 for _ in range(max_node + 1_0			)] for _ in range(2_0			)]
 # initializing with -1 which means every node is unvisited
 UpperCAmelCase__ 						=				[-1 for _ in range(max_node + 1_0			)]
 UpperCAmelCase__ 						=				{
     1: [2, 3, 4],
     2: [5],
     3: [6, 7],
     4: [8],
     5: [9, 1_0],
     6: [1_1],
     7: [],
     8: [1_2, 1_3],
     9: [],
     1_0: [],
     1_1: [],
     1_2: [],
     1_3: [],
 }
 UpperCAmelCase__ 						=				breadth_first_search(_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE       ,	1			)
 UpperCAmelCase__ 						=				create_sparse(_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)
 print("""LCA of node 1 and 3 is: """       ,	lowest_common_ancestor(1       ,	3       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)			)
 print("""LCA of node 5 and 6 is: """       ,	lowest_common_ancestor(5       ,	6       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)			)
 print("""LCA of node 7 and 11 is: """       ,	lowest_common_ancestor(7       ,	1_1       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)			)
 print("""LCA of node 6 and 7 is: """       ,	lowest_common_ancestor(6       ,	7       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)			)
 print("""LCA of node 4 and 12 is: """       ,	lowest_common_ancestor(4       ,	1_2       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)			)
 print("""LCA of node 8 and 8 is: """       ,	lowest_common_ancestor(8       ,	8       ,	_SCREAMING_SNAKE_CASE       ,	_SCREAMING_SNAKE_CASE			)			)


if __name__ == "__main__":
 main()






'''simple docstring'''


from __future__ import annotations







def     SCREAMING_SNAKE_CASE(	UpperCamelCase ,UpperCamelCase ,UpperCamelCase ,UpperCamelCase	)     ->     int:

	# Base Case
	if counter == 0 or capacity == 0:
		return 0

	# If weight of the nth item is more than Knapsack of capacity,
	#   then this item cannot be included in the optimal solution,
	# else return the maximum of two cases:
	#   (1) nth item included
	#   (2) not included
	if weights[counter - 1] > capacity:
		return knapsack(UpperCamelCase ,UpperCamelCase ,UpperCamelCase ,counter - 1	)
	else:
		UpperCAmelCase_		:   int													=       capacity - weights[counter - 1]
		UpperCAmelCase_		:   Optional[int]													=       values[counter - 1] + knapsack(
		    UpperCamelCase ,UpperCamelCase ,UpperCamelCase ,counter - 1	)
		UpperCAmelCase_		:   Any													=       knapsack(UpperCamelCase ,UpperCamelCase ,UpperCamelCase ,counter - 1	)
		return max(UpperCamelCase ,UpperCamelCase	)


if __name__ == "__main__":
						import doctest

						doctest.testmod()






