






'''simple docstring'''


from __future__ import annotations

from queue import Queue







def 						__magic_name__(			_A    ,   _A       ):
						'''simple docstring'''





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







def 						__magic_name__(			_A    ,   _A       ):
						'''simple docstring'''





						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 						__magic_name__(			_A    ,   _A    ,   _A    ,   _A       ):
						'''simple docstring'''





						if level[u] < level[v]:
												UpperCamelCase__     , UpperCamelCase__       =			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]:
																		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(18    ,   -1    ,   -1       ):
												if parent[i][u] not in [0, parent[i][v]]:
																		UpperCamelCase__     , UpperCamelCase__       =			parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
						return parent[0][u]







def 						__magic_name__(			_A    ,   _A    ,   _A    ,   _A    ,   _A = 1    ,   ):
						'''simple docstring'''





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







def 						__magic_name__(			):
						'''simple docstring'''





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








'''simple docstring'''


from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tf_available, is_torch_available


lowerCamelCase_					:			str     						=				{'''configuration_hubert''': ['''HUBERT_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''HubertConfig''']}

try:
					if not is_torch_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					lowerCamelCase_					:			Union[str, Any]     						=				[
					    '''HUBERT_PRETRAINED_MODEL_ARCHIVE_LIST''',
					    '''HubertForCTC''',
					    '''HubertForSequenceClassification''',
					    '''HubertModel''',
					    '''HubertPreTrainedModel''',
					]


try:
					if not is_tf_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					lowerCamelCase_					:			Optional[Any]     						=				[
					    '''TF_HUBERT_PRETRAINED_MODEL_ARCHIVE_LIST''',
					    '''TFHubertForCTC''',
					    '''TFHubertModel''',
					    '''TFHubertPreTrainedModel''',
					]

if TYPE_CHECKING:
					from .configuration_hubert import HUBERT_PRETRAINED_CONFIG_ARCHIVE_MAP, HubertConfig

					try:
										if not is_torch_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_hubert import (
										    HUBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
										    HubertForCTC,
										    HubertForSequenceClassification,
										    HubertModel,
										    HubertPreTrainedModel,
										)

					try:
										if not is_tf_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_tf_hubert import (
										    TF_HUBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
										    TFHubertForCTC,
										    TFHubertModel,
										    TFHubertPreTrainedModel,
										)


else:
					import sys

					lowerCamelCase_					:			Dict     						=				_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)
