




"""simple docstring"""

from __future__ import annotations

from queue import Queue



def 					UpperCamelCase__       (						lowercase__					:       int    ,       lowercase__					:       int				):
		a ^= b
		b ^= a
		a ^= b
		return a, b



def 					UpperCamelCase__       (						lowercase__					:       int    ,       lowercase__					:       list[list[int]]				):
		snake_case						:  str        =			1
		while (1 << j) < max_node:
				for i in range(1    ,       max_node + 1				):
						snake_case						:  Any        =			parent[j - 1][parent[j - 1][i]]
				j += 1
		return parent



def 					UpperCamelCase__       (						lowercase__					:       int    ,       lowercase__					:       int    ,       lowercase__					:       list[int]    ,       lowercase__					:       list[list[int]]				):
		# u must be deeper in the tree than v
		if level[u] < level[v]:
				snake_case     ,			snake_case						:  str        =			swap(lowercase__    ,       lowercase__				)
		# making depth of u same as depth of v
		for i in range(18    ,       -1    ,       -1				):
				if level[u] - (1 << i) >= level[v]:
						snake_case						:  List[Any]        =			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]]:
						snake_case     ,			snake_case						:  List[Any]        =			parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
		return parent[0][u]



def 					UpperCamelCase__       (						lowercase__					:       list[int]    ,       lowercase__					:       list[list[int]]    ,       lowercase__					:       int    ,       lowercase__					:       dict[int, list[int]]    ,       lowercase__					:       int = 1    ,       ):
		snake_case						:  int        =			0
		snake_case						:  Queue[int]        =			Queue(maxsize=lowercase__				)
		q.put(lowercase__				)
		while q.qsize() != 0:
				snake_case						:  Any        =			q.get()
				for v in graph[u]:
						if level[v] == -1:
								snake_case						:  str        =			level[u] + 1
								q.put(lowercase__				)
								snake_case						:  Any        =			u
		return level, parent



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


if __name__ == "__main__":
							main()







"""simple docstring"""

from typing import TYPE_CHECKING

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


__A							=     {
    "configuration_flava": [
        "FLAVA_PRETRAINED_CONFIG_ARCHIVE_MAP",
        "FlavaConfig",
        "FlavaImageCodebookConfig",
        "FlavaImageConfig",
        "FlavaMultimodalConfig",
        "FlavaTextConfig",
    ],
}

try:
							if not is_vision_available():
														raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
							pass
else:
							__A							=     ["FlavaFeatureExtractor"]
							__A							=     ["FlavaImageProcessor"]
							__A							=     ["FlavaProcessor"]

try:
							if not is_torch_available():
														raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
							pass
else:
							__A							=     [
							    "FLAVA_PRETRAINED_MODEL_ARCHIVE_LIST",
							    "FlavaForPreTraining",
							    "FlavaImageCodebook",
							    "FlavaImageModel",
							    "FlavaModel",
							    "FlavaMultimodalModel",
							    "FlavaPreTrainedModel",
							    "FlavaTextModel",
							]

if TYPE_CHECKING:
							from .configuration_flava import (
							    FLAVA_PRETRAINED_CONFIG_ARCHIVE_MAP,
							    FlavaConfig,
							    FlavaImageCodebookConfig,
							    FlavaImageConfig,
							    FlavaMultimodalConfig,
							    FlavaTextConfig,
							)

							try:
														if not is_vision_available():
																					raise OptionalDependencyNotAvailable()
							except OptionalDependencyNotAvailable:
														pass
							else:
														from .feature_extraction_flava import FlavaFeatureExtractor
														from .image_processing_flava import FlavaImageProcessor
														from .processing_flava import FlavaProcessor

							try:
														if not is_torch_available():
																					raise OptionalDependencyNotAvailable()
							except OptionalDependencyNotAvailable:
														pass
							else:
														from .modeling_flava import (
														    FLAVA_PRETRAINED_MODEL_ARCHIVE_LIST,
														    FlavaForPreTraining,
														    FlavaImageCodebook,
														    FlavaImageModel,
														    FlavaModel,
														    FlavaMultimodalModel,
														    FlavaPreTrainedModel,
														    FlavaTextModel,
														)

else:
							import sys

							__A							=     _LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)

