






from __future__ import annotations

from queue import Queue



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__	):


		'''simple docstring'''

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



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__	):


		'''simple docstring'''

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



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__	):


		'''simple docstring'''

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



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__ = 1					,     ):


		'''simple docstring'''

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



def      UpperCAmelCase						( ):


		'''simple docstring'''

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


if __name__ == "__main__":
					main()









from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_flax_available,
    is_tf_available,
    is_torch_available,
)


snake_case_   :	Union[str, Any]							      ={'''configuration_gptj''': ['''GPTJ_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''GPTJConfig''', '''GPTJOnnxConfig''']}

try:
					if not is_torch_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					snake_case_   :	int							      =[
					    '''GPTJ_PRETRAINED_MODEL_ARCHIVE_LIST''',
					    '''GPTJForCausalLM''',
					    '''GPTJForQuestionAnswering''',
					    '''GPTJForSequenceClassification''',
					    '''GPTJModel''',
					    '''GPTJPreTrainedModel''',
					]

try:
					if not is_tf_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					snake_case_   :	str							      =[
					    '''TFGPTJForCausalLM''',
					    '''TFGPTJForQuestionAnswering''',
					    '''TFGPTJForSequenceClassification''',
					    '''TFGPTJModel''',
					    '''TFGPTJPreTrainedModel''',
					]

try:
					if not is_flax_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					snake_case_   :	List[Any]							      =[
					    '''FlaxGPTJForCausalLM''',
					    '''FlaxGPTJModel''',
					    '''FlaxGPTJPreTrainedModel''',
					]


if TYPE_CHECKING:
					from .configuration_gptj import GPTJ_PRETRAINED_CONFIG_ARCHIVE_MAP, GPTJConfig, GPTJOnnxConfig

					try:
										if not is_torch_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_gptj import (
										    GPTJ_PRETRAINED_MODEL_ARCHIVE_LIST,
										    GPTJForCausalLM,
										    GPTJForQuestionAnswering,
										    GPTJForSequenceClassification,
										    GPTJModel,
										    GPTJPreTrainedModel,
										)

					try:
										if not is_tf_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_tf_gptj import (
										    TFGPTJForCausalLM,
										    TFGPTJForQuestionAnswering,
										    TFGPTJForSequenceClassification,
										    TFGPTJModel,
										    TFGPTJPreTrainedModel,
										)

					try:
										if not is_flax_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_flax_gptj import FlaxGPTJForCausalLM, FlaxGPTJModel, FlaxGPTJPreTrainedModel

else:
					import sys

					snake_case_   :	List[str]							      =_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)

