


from __future__ import annotations

from queue import Queue






def 	lowerCamelCase_       (			_a      ,  _a			):




		"""simple docstring"""






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






def 	lowerCamelCase_       (			_a      ,  _a			):




		"""simple docstring"""






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






def 	lowerCamelCase_       (			_a      ,  _a      ,  _a      ,  _a			):




		"""simple docstring"""






		if level[u] < level[v]:
				lowerCAmelCase__	,      lowerCAmelCase__  :     Any       	=   swap(_a      ,  _a			)
		# making depth of u same as depth of v
		for i in range(18      ,  -1      ,  -1			):
				if level[u] - (1 << i) >= level[v]:
						lowerCAmelCase__  :     Dict       	=   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]]:
						lowerCAmelCase__	,      lowerCAmelCase__  :     Optional[int]       	=   parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
		return parent[0][u]






def 	lowerCamelCase_       (			_a      ,  _a      ,  _a      ,  _a      ,  _a = 1      ,  ):




		"""simple docstring"""






		lowerCAmelCase__  :     str       	=   0
		lowerCAmelCase__  :     Queue[int]       	=   Queue(maxsize=_a			)
		q.put(_a			)
		while q.qsize() != 0:
				lowerCAmelCase__  :     Optional[int]       	=   q.get()
				for v in graph[u]:
						if level[v] == -1:
								lowerCAmelCase__  :     Any       	=   level[u] + 1
								q.put(_a			)
								lowerCAmelCase__  :     List[Any]       	=   u
		return level, parent






def 	lowerCamelCase_       (			):




		"""simple docstring"""






		lowerCAmelCase__  :     Dict       	=   13
		# initializing with 0
		lowerCAmelCase__  :     Optional[int]       	=   [[0 for _ in range(max_node + 10			)] for _ in range(20			)]
		# initializing with -1 which means every node is unvisited
		lowerCAmelCase__  :     Optional[int]       	=   [-1 for _ in range(max_node + 10			)]
		lowerCAmelCase__  :     dict[int, list[int]]       	=   {
		    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: [],
		}
		lowerCAmelCase__	,      lowerCAmelCase__  :     Tuple       	=   breadth_first_search(_a      ,  _a      ,  _a      ,  _a      ,  1			)
		lowerCAmelCase__  :     str       	=   create_sparse(_a      ,  _a			)
		print('''LCA of node 1 and 3 is: '''      ,  lowest_common_ancestor(1      ,  3      ,  _a      ,  _a			)			)
		print('''LCA of node 5 and 6 is: '''      ,  lowest_common_ancestor(5      ,  6      ,  _a      ,  _a			)			)
		print('''LCA of node 7 and 11 is: '''      ,  lowest_common_ancestor(7      ,  11      ,  _a      ,  _a			)			)
		print('''LCA of node 6 and 7 is: '''      ,  lowest_common_ancestor(6      ,  7      ,  _a      ,  _a			)			)
		print('''LCA of node 4 and 12 is: '''      ,  lowest_common_ancestor(4      ,  12      ,  _a      ,  _a			)			)
		print('''LCA of node 8 and 8 is: '''      ,  lowest_common_ancestor(8      ,  8      ,  _a      ,  _a			)			)


if __name__ == "__main__":
		main()








from typing import TYPE_CHECKING

from ...utils import _LazyModule


lowerCamelCase		=						{'''tokenization_phobert''': ['''PhobertTokenizer''']}


if TYPE_CHECKING:
		from .tokenization_phobert import PhobertTokenizer

else:
		import sys

		lowerCamelCase		=						_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)




